【作者】 余建军；

【导师】 孙树栋；

【作者基本信息】 西北工业大学 ， 机械电子工程， 2007， 博士

【摘要】 Job Shop调度是一类复杂的组合优化难题，有着深刻的实际背景和广阔的应用前景。目前的调度理论研究对实际调度问题进行了简化处理，忽略了许多必要的实际因素，离实际应用还存在较大差距。因此，考虑柔性、多目标、多约束、分布式，研究接近生产实际的Job Shop调度具有重要的理论意义和工程价值。本文以Job Shop调度为研究对象，以接近生产实际为中心线索，以免疫优化理论为技术支撑，对Job Shop调度的建模、求解、优化和仿真等关键问题进行了系统深入的研究和探索。本文的主要研究成果和结论如下：1．提出了适合于Job Shop调度的建模方法，按照从简单到复杂、逐渐接近生产实际的主线，依次建立了标准Job Shop调度模型、柔性Job Shop调度模型、多目标柔性Job Shop调度模型、多约束多目标柔性Job Shop调度模型和分布式多目标Job Shop调度模型。在剖析实际生产调度的基础上，按照普遍通用的原则进行抽象提取，采用目标函数、约束条件等数学方法对实际调度的物理形式和逻辑意义进行描述，采用Petri网图论理论和面向对象结构化方式对实际调度的静态特性和动态特性进行刻画。2．提出了多种有效的Job Shop调度算法，针对不同调度问题的特点和差异，基于调度模型，依次提出了基于动态评价的免疫遗传算法、免疫模拟退火算法、多种群双倍体自适应免疫算法、免疫蚁群算法以及基于调度网格的分布式调度算法。这些免疫调度算法以调度模型为应用背景，以高效调度为原则，以免疫优化理论为依托，模拟实现了多种免疫机制：包括免疫识别、免疫学习、免疫记忆在内的免疫应答机制：基于抗体期望繁殖率的免疫选择机制；保证抗体多样性的免疫调节机制：提高算法收敛速度和防止群体退化的免疫疫苗机制。实例求解证实这些算法能够快速收敛，具有较强的调度优化能力，适用于相应的调度问题。3．根据具体问题具体分析的哲理，提出了灰色关联层次分析等多种多目标处理策略，分别应用于不同调度问题的求解。依据柔性调度包含设备分配和工序调度两个子问题的本质，采用了分解策略和综合策略两种柔性处理策略。本着简单有效的原则，探索了将约束条件转化为目标函数和用约束条件对进化解进行过滤的两层约束处理策略。4．提出了调度网格的概念，基于调度网格提出了分布式调度方法；提出了单元问调度和单元内调度两级调度策略，确立了分布式Job Shop调度体系框架；搭建了任务调度系统，构造了调度器；提出了任务调度管理逻辑结构，确立了任务调度管理过程；提出了基于免疫原理的招投标机制和基于匹配层次图的谈判策略，搭建了多目标评价体系；实现了局部凋度和全局调度协同优化，验证了分布式Job Shop调度方法的有效性。5．确定了Job Shop调度求解方法，设计了求解要素；针对单目标Job Shop调度、多目标Job Shop调度、分布式多目标Job Shop调度，采用本文所提相应调度算法分别进行了求解与仿真；分别以国际标准Job Shop调度算例和企业实际Job Shop调度案例进行验证与对比，证明模型和算法的有效性。6．基于本文调度理论，采用先进软件技术，设计开发了Job Shop调度原型系统，并成功应用于企业生产实践。更多还原

【Abstract】 Job shop scheduling is one of most complicated combinatorial optimizationproblems and has profound practice background and wide application foreground.Because of ignoring many actual constraints to simplify computation complexity, atpresent scheduling theory research doesn’t satisfy the practical application demand.Therefore, it’s more significant in theory and valuable in engineering to study the jobshop scheduling close to the production practice, which involves with flexibility,multi-objective, multi-constraint and distributing.In the Dissertation, job shop scheduling is regarded as the research objective, andthe central clue is to close to the production practice, and the technology support is theimmune optimization theory. Several kinds of key technology of job shop schedulinghave been deeply studied, which are modeling, solution, optimization and simulation,et al. The main result and contribution of the dissertation are as follows.1. The modeling methods are put forward. According to the primary clue ofapproaching to the production practice, several kinds of different job shop schedulingmodels are set up, which are the classical job shop scheduling model, the flexible jobshop scheduling model, the multi-objective flexible job shop scheduling model, themulti-constraint nmlti-objective flexible job shop scheduling model and thedistributing multi-objective job shop scheduling model. After analyzing theproduction practice, the dissertations picks up the essence according to the universalprinciple. The physical form and the logic meaning of job shop are depicted by theobjective function and the constraint, and the static characteristic and the dynamicalcharacteristic of job shop scheduling are expressed by the Petri net theory and theobject oriented structure.2. Several kinds of effectual scheduling algorithms are put forward based on themodel and the characteristic of each kind of job shop scheduling. They are dynamicevaluation based immune algorithm, immune simulated annealing algorithm,multi-colony diploid adaptive immune algorithm, immune ant colony algorithm anddistributing scheduling algorithm based on the scheduling grid. These algorithmssimulate many kinds of immune mechanism by using the scheduling model as the application background, the efficiently scheduling as the principle, the immuneoptimization theory as the base. The immune response mechanism includes theimmune detection, the immune learning, the immune remember, et al. The immuneselection mechanism is based on the antibody reproducibility ratio involved with theantibody affinity and the concentration. The immune self-adjusting mechanism isadopted to keep diversity. The vaccine mechanism is used to speed the convergenceand avoid the colony degradation. The instance simulation experiments indicate thatthese algorithms have powerful scheduling optimization capability and can convergequickly, and fit the corresponding job shop scheduling.3. Several kinds of effectual scheduling strategies are put forward. According tothe idea of specifically analyzing the given problem, several multi-objective disposalstrategies are put forward to solve the corresponding job shop scheduling, such asgray correlation analysis method oriented scheduling. The flexible job shopscheduling essentially includes two sub-problems, i. e. the equipment distribution andthe operation scheduling, accordingly the decomposition strategy and the integrationstrategy are used to treat with the flexibility problem. According to the principle ofsimplification and availability, two-level constraint disposal strategy is studied, whichtransforms the constraint into the objective function and filters the candidate solutionsby the constraint conditions.4. The concept of scheduling grid is initially put forward and accordingly thedistributing scheduling method is put forward based on it. The two level schedulingstrategy is put forward which involved with the scheduling among manufacturingcells and the scheduling within the manufacturing cell. The system frame of thedistributing job shop scheduling is established. The task scheduling system is set upand the scheduling implement is constructed. The logic structure of the taskscheduling management is put forward and the process of task schedulingmanagement is confirmed. The mechanism of the bidding and inviting public biddingbased on the immune principle is put forward and the negotiation strategy based onthe matching layer chart is put forward. The multi-objective evaluation system is setup and synchronously optimization is carried out by local scheduling and globalscheduling. The validity of the distributing scheduling method is ultimately proved.5. The solving method of job shop scheduling is established and the key steps aredesigned. The single objective job shop scheduling, the multi-objective job shopscheduling and the distributing multi-objective job shop scheduling are respectivelysimulated and solved with the algorithms put forward. The international classical job shop scheduling instances and the enterprise practice job shop cases are simulated andcontrasted, and the availability of the models and the algorithms are validated.6. Consequently the job shop scheduling system is achieved based on abovescheduling theory with the advanced soft technology, and applied to productionpractice.更多还原