具有配合加工的单元式流水车间调度问题的启发式算法理论分析

针对定制型装备制造企业车间的生产特点，本项目对具有配合加工的单元式流水车间的调度问题展开了研究。其特色与创新之处在于：基于问题特征，提出了一种基于组合规则和改进型SB算法的两阶段求解算法框架，通过在算法框架中的不同位置嵌入不同的启发式规则，可以产生大量不同的复合规则算法；提出了一种构造性的数学分析方法，获得了所生成的复合规则类算法的最坏情形界；提出了一种概率方法，用于分析复合规则类算法的平均效果。通过时间复杂度分析、最坏情形界分析和平均效果分析，从算法理论的角度评价了所生成的复合规则类算法的优劣性。本项目的研究成果将为装备制造企业，以及具有类似生产特点的制造企业现行的车间作业调度应用，提供了复合规则类算法的构建、选择与评价的理论基础。

Considering the characteristics of the work shop of the industry of order-driven equipment manufacturing, this project deals with the cellular flow shop scheduling problem with operation relativity. Creativities of this project lie in the following: regarding of the characteristics of the problem, a two-phase frame of algorithm based on combination of rules and improved shifting bottleneck algorithm (R-SB), is proposed. By embedding different heuristic rules in different locations of the frame of R-SB algorithm, lots of scheduling algorithms are produced to deal with the scheduling problem proposed by this project; A mathematics analysis method based on structure is proposed to obtain the worst-case rate of the combinational rule algorithms; A probabilistic method is proposed to analyze the average rate of the combinational rule algorithms. From algorithm theories, the performances of these combinational rule algorithms are tested by analysis of their time complexities, worst-case rates and average rate. The output of this project can provide the equipment manufacturers and the companies like equipment manufacturers with theoretical basis to solve the uncoordinated issue between job shop scheduling and the scheduled execution.