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

项目名称： 柔性车间调度问题的算法设计与理论研究

项目编号： No.71201107

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 管理科学

项目作者： 白丹宇

作者单位： 沈阳化工大学

项目金额： 19万元

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

中文关键词： 调度；车间作业；启发式算法；算法性能分析；

英文摘要： 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 opt

英文关键词： Scheduling；Shop scheduling；Heuristic algorithm；Performance analysis of algorithm；