考虑工时分段恶化的生产过程调度理论与群集优化策略研究

As a significant procedure in the production and operation management, scheduling has a direct impact on the benefit and competitiveness of a company. How to obtain the effective and efficient schedule for the complex production system is always the important scientific problem, and highly focused by the academia and engineering. However, there exist many stepwise deteriorating jobs in the practical production, which are hard to be solved by the existing scheduling theory. Therefore, the efficient optimization strategy and scheduling theory are urgently required to solve the production scheduling problems with stepwise deteriorating jobs. This project takes the operation conditions described with the stepwise function and piecewise linear function as the starting point, then researches on the scheduling problems in which the processing times of all jobs are depicted by the two functions under the single machine, parallel machines and flow shop environment. The effect of the type of deterioration on the scheduling problem is considered from three aspects as theoretical analyses, computer simulations and practical engineering applications. The computational complexity of these scheduling problems are determined, and the corresponding optimization scheduling theories and strategies are mainly discussed in the project, which aims to make some breakthrough on problem modeling, related optimization rules, polynomial time solvable condition, heuristic algorithm, the frame of swarm optimization algorithm and searching operation designing. The motivation of the project is to enrich and improve the production scheduling theory system and get some applications in the typical practical problems, such as container loading/discharging operation and perishable food production process.

调度作为生产与运作管理中的重要环节，直接影响企业的效益和竞争力。如何对复杂生产系统进行合理有效的调度一直是学术界和工程界高度关注的科学问题。然而现实生产中存在大量工时分段恶化的加工情况，现有调度理论难以直接对其进行求解，因此迫切需要考虑给出有效的优化方法及调度理论来解决此类问题。本项目以工时由阶梯函数和分段线性函数描述的作业情况为出发点，围绕单机、并行机和流水车间三类加工环境分别对这两类函数刻画的工时恶化情况的调度问题加以研究；从理论分析、计算机仿真和实际工程应用三个方面探索此类恶化效应对调度问题的作用机制，重点围绕生产系统的诸多复杂性研究其优化调度理论与策略，旨在问题建模、计算复杂性、与问题相关优化规则、多项式可解情况、启发式算法、群优化算法框架与搜索操作设计等方面取得突破以丰富和完善生产调度理论体系，并在集装箱装卸作业、易腐食品加工等具有代表性的实际问题中加以应用。

如何对复杂生产过程进行合理有效的调度一直是学术界和工程界高度关注的科学问题。然而现实生产过程中存在大量工时分段恶化的加工情况，现存理论难以直接对其进行求解，因此迫切需要考虑给出有效的优化方法及调度理论来解决此类问题。项目以工时由阶梯函数和分段线性函数描述的作业过程为研究对象，从问题建模、计算复杂性、与问题相关优化规则、启发式算法以及群集优化求解策略等方面出发，对相关调度理论和求解手段进行了深入系统的研究，旨在为具有类似生产特点的作业过程选取和评价调度策略提供理论依据。围绕上述目标，同时结合课题组前期调研所得，取得了以下研究成果：.1)工时分段恶化作用下单机调度理论及优化算法研究。.以总延误及总加权延误时间最小化等目标为出发点，给出了直接证明总加权延误时间最小化的NP-hard证明，利用标准求解器验算了不同建模方式的求解效率，数值计算发现基于线性排序的建模方式整体表现最佳。依据问题的特性提出了7种分派式规则以获得近似最优解，并生成了大量公开的问题测试算例集，对分派规则及启发式求解算法进行性能分析。.2)并行机调度优化策略及群集优化策略研究。.针对工时阶梯恶化的并行机调度问题，分析了不同建模方式对求解效果的影响。研究了调整时间和工时恶化共同作用下的并行机调度优化策略，提出了基于布谷鸟搜索的混合离散优化框架。同时针对群集优化过程中适应度评估耗时过长的问题，提出采用极值学习机预测部分个体适应度值，构建了基于适应度函数近似评估的混合进化搜索框架。基于该算法开发了相应的优化系统，并在设施选址上进行了应用。.3)应用研究。.基于已有的研究成果，将其分别运用到铁路集装箱转运作业调度、多技能资源约束下的项目调度、医疗检查调度和能耗约束下的并行机调度问题中。研究建立其数学模型，设计求解算法，并采用基于实际数据的方式产生算例对算法的效果进行分析。基于该成果的研究已开始用于相关行业，有效提升了企业的生产效率。