多品种多批次混合Flow-shop车间的复合规则类调度算法及其理论分析

针对多品种多批次的混合流水车间生产特点，本项目对具有多种能源介质和多组决策变量耦合的混合flow-shop车间调度问题展开了研究。具体包括：建立具有多种能源介质多组决策变量耦合效应分解模型；基于分解模型，提出一种基于启发式规则的复合算法生成框架，通过在算法框架中的不同节点嵌入不同的启发式规则，可以产生大量不同的复合规则算法；通过对算法的时间复杂度分析、最坏情形界分析和平均效果分析，从算法理论角度评价了所生成复合规则类算法的优劣性；最后通过设计算法仿真实验对上述模型和算法进行验证。特色与创新之处体现在：构建了一种基于问题特征的分解模型，并提出一种基于启发式规则的复合算法框架；提出了一种构造性的数学分析方法，获得了复合规则类算法的最坏情形界；提出了一种概率方法，用于分析复合规则类算法的平均效果。研究成果将为大批量定制化高耗能企业制定生产计划时，提供了复合规则类算法的构建、选择与评价的理论基础。

Considering the characteristics of hybrid flow shop with multiple types and multiple batches, this project deals with the hybrid flow shop scheduling problem of energy optimization subjected to multiple kinds of energy-consumed media and coupling effect of multiple groups of decision variables. The content includes: building up decomposition mathematical models based on multiple kinds of energy-consumed media and coupling effect of multiple groups of decision variables; regarding to these models, a frame of generating algorithms based on the combination of heuristics. By embedding different heuristic rules in different nodes of the frame, lots of combinable algorithms are produced; from algorithm theories, the performances of these combinational rules are tested by analysis of their time complexities, worst-case rates and average rate; finally, simulated experiments are designed to test these mathematical models and combinational rules. Creativities of this project lie in the following: regarding of the characteristics of the problem, decomposition models and a frame of algorithms based on combinational heurists are proposed; a mathematics analysis method based on structure is proposed to obtain the worst-case rate of the combinational rules; a probabilistic method proposed to analyze the average rate of the combinational rules. The output of this project can provide the manufacturers which is order-driven, massive and high energy-consumed with theoretical basis to make the production plan.