柔性车间调度问题的算法设计与理论研究

The scheduling problems of flexible shop play a vital role in many industrial fields such as ironmaking & Steelmaking, inspection & maintenance and mechanical treatment. Since the NP-hardness of the problems, it is very difficult to obtain the optimal solution for small size problems, and it is impossible to solve them in polynomial time for large scale problems. Therefore, the key research method in industry and academia is to gain their approximate solution with heuristics currently. And evaluating the performance of algorithms theoretically is a challenging research topic in the area of scheduling. Comparing to the classical method of worst-case performance analysis, the way of asymptotic performance analysis investigated in this project can show what degree the heuristic converges to the optimal schedule further in theory as the problem size increases to infinity. The following investigations will be implemented: (1) designing new heuristics for flexible shop scheduling problems, and proving their asymptotic optimality, i.e., heuristic can be treated as optimal schedule for sufficiently large size problems; (2) promoting the performance of these heuristics for moderate scale problems with the optimal methods such as local search; (3) building new lower bounds for the problems, analyzing their performance theoretically including worst performance analysis and asymptotic performance analysis, in order to provide reliable guarantee in theory for numerical simulations.

柔性车间调度问题广泛存在于钢铁冶炼、检测维修和机械加工等诸多工业领域。由于该问题一般都是NP难的，即使最优求解小规模问题都将非常困难，而计算较大规模问题的最优解更是无法完成，因此利用启发式进行近似求解已成为目前工业界和学术界的主要研究手段。如何从理论上分析和评价算法的性能更是排序与调度领域极具挑战性的研究课题。与传统的最坏性能分析手段相比，本项目所研究的渐近性能分析方法能更深入的从理论角度说明问题规模无限增大时，启发式与最优排序的收敛程度。将主要进行三方面的研究：（1）针对柔性车间调度问题，设计新的启发式，并证明这些算法的渐近最优性，即问题规模趋近于无穷大时，启发式等价于最优排序；（2）根据启发式的自身特点利用局域搜索等优化方法对其做进一步改进，提高处理中等规模问题时的性能；（3）构造所研究问题的新下界，并对其性能进行理论分析，包括渐近性能分析和最坏性能分析，为仿真实验提供可靠的理论依据。

本项目针对车间调度模型中的算法设计与性能分析问题展开深入研究。首先，在求解大规模问题时，利用理论分析方法证明所提出的启发式算法具有渐近最优性，同时也对某些启发式在极端情况下的最坏性能进行研究；其次，在求解中等规模问题时，设计智能优化算法进一步改进由启发式得到的初始解；最后，通过数值仿真验证启发式的收敛性以及智能优化算法性能。主要结论包括：(1) 针对流水车间极小化完工时间k次方和问题，在概率极限意义下证明一类基于SPT规则的启发式算法具有渐近最优性，并对其中的某些启发式进行最坏性能分析；提出非延迟剪支策略，设计分支定界算法最优求解小规模问题。(2) 针对带有学习效应的流水车间成组调度模型，研究极小化目标分别为最大完工时间、完工时间和、加权完工时间和以及最大延误的问题，提出基于SPT、WSPT以及EDD规则的启发式算法，证明最坏性能比紧界；设计基于工件分组的遗传算法和量子差分进化算法求解中等规模问题。(3) 针对开放车间极小化完工时间k次方和以及加权完工时间和问题，在概率极限意义下分别证明基于SPT以及WSPT规则的启发式算法具有渐近最优性；设计遗传算法、差分进化算法等求解中等规模问题。(4) 针对柔性开放车间极小化最大完工时间问题，在极限意义下证明一类基于广义稠密排序的近似算法具有渐近最优性；设计基于种群进化的差分进化算法求解中等规模问题。.围绕上述研究，已在国际期刊上发表和录用论文7篇，其中SCI检索5篇，EI检索3篇。本研究的所采用的渐近性能分析方法，能够有效避免利用最坏性能评价算法所带来的片面性，所取得的理论成果对大规模工业生产管理具有相当重要的指导意义。