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

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.

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

本项目以装备制造企业普遍采用的，具有配合加工的单元式流水车间生产布局方式作为研究背景，对这类生产车间常用的规则类启发式调度算法进行系统深入的理论分析，旨在为装备制造企业，以及具有类似生产特点的制造企业的车间选取和评价调度算法，提供理论依据。围绕上述目标的实现，并结合课题组前期对企业的调研，对以下内容展开了研究：. 1.具有工装约束的单元流水车间调度问题启发式算法的构建与分析。针对一类考虑后成组约束的、工件批量到达的两阶段柔性流水车间调度问题，并且在每阶段都是由非同等并行机构成。提出了与之相适应的优化目标、调度算法，并对算法的时间复杂度和最坏情形界进行了分析。基于该成果开发的排产系统预期将能极大帮助装配制造车间提升其自动化管理水平以及科学决策能力，并最终提高此类车间的准时交货率。. 2.具有配合约束单元流水车间调度问题启发式算法的构建与分析。针对一类考虑中成组约束的、工件批量到达的三阶段柔性流水车间调度问题，并且在每阶段都是由非同等并行机构成。提出了与之相适应的优化目标、调度算法，并对算法的时间复杂度和最坏情形界进行了分析。基于该成果开发的排产系统预期将能极大帮助装配制造车间提升其自动化管理水平以及科学决策能力，并最终缩短此类车间的生产周期。. 3.考虑能耗目标的算法构建方法。分别针对以最少化拖期成本和能耗成本的非同等并行机能效优化调度问题和以能耗成本为目标具有两类与顺序相关的调整时间的柔性流水车间能效优化调度问题，研究建立其数学模型，构建算法框架，并多算法的时间复杂度进行分析，初步对算法的平均效果进行了分析。基于该成果开放的能源管理系统提高企业的效率，节省企业生产能耗，提升企业竞争力。