基于地貌分析的复杂零空闲流水车间超启发式调度方法研究

No-idle flow-shop scheduling problem has been proved to be NP-hard, and has a wide industrial application background since it is quite usual in the process of flow industries such as textile, chemical, metallurgical, etc. Research on intelligent optimization scheduling theory has been focused by academia and industry. Based on realistic production process, a complex no-idle flow-shop scheduling problem with the constraints of mixed no-idle operations and parallel machines is investigated in this project. Firstly, by establishing the constraint optimization mathematical model for the problem, the calculation models and methods with different scheduling objectives are proposed. Secondly, under the hyper-heuristic algorithm scheme, the impact of landscape characteristic on the algorithm performance is studied in heuristic domain by using the theories and methods of landscape analysis, and a dynamic and multi-strategy evolutionary algorithm is presented based on different types of landscape characteristics. Finally, a landscape analysis-based hyper-heuristic scheduling optimization model is constructed and further verified on problem instances. This project not only provides new ideas and technologies for production scheduling optimization problem, but also enriches and deepens the optimization scheduling theory, and will also help enterprises to reduce production costs and improve production efficiency. Therefore, this project has great theoretical significance and application value.

零空闲流水车间调度问题有很强的工业应用背景，普遍存在于纺织、化工、冶金等流程工业的生产过程中，本质上属于NP难解问题，有关智能优化调度理论的研究一直是学术界和工业界的研究热点。本项目从实际生产过程出发，针对一类具有工序混合零空闲约束和并行机特征的复杂零空闲流水车间调度问题，通过建立其约束优化数学模型，提出不同调度指标下的计算模型及方法，在超启发式算法框架下，结合地貌分析的理论与方法，在启发式域层面探寻地貌特征对算法性能的影响机理，提出基于地貌特征的动态多策略演化算法，进而构建基于地貌分析的超启发式调度优化模型，并结合复杂零空闲流水车间调度问题实例进行方法有效性验证。本项目研究为生产调度优化问题的解决提供新的思路与方法，进一步丰富和深化已有的优化调度理论，有助于企业降低生产成本、提高生产效率，具有重要的理论意义和应用价值。

在生产制造领域，随着市场竞争的日趋激烈，企业在满足生产设备和工艺要求的前提下，为提高生产效率，需对生产过程进行调度优化。合理的调度方案不仅可以缩短产品制造周期，而且可以有效地提高设备利用率、减少能源和物质损耗，从而达到节能减排、降低成本和提高经济效益的目的。零空闲流水车间调度问题有很强的工业应用背景，普遍存在于纺织、化工、冶金等流程工业的生产过程中，本质上属于NP难解问题，有关智能优化调度理论的研究一直是学术界和工业界的研究热点。本项目从实际生产过程出发，针对一类具有工序混合零空闲约束和并行机特征的复杂零空闲流水车间调度问题，通过建立其约束优化数学模型，研究提出不同调度指标下的计算模型及方法，在超启发式算法框架下，结合地貌分析的理论与方法，在启发式域层面探寻问题特征对算法性能的影响机理，提出基于问题特征的动态多策略演化算法，进而构建超启发式调度优化模型，并结合复杂零空闲流水车间调度问题实例进行方法有效性验证。本项目针对上述研究内容进行了深入研究，取得如下主要成果：（1）以最小完工时间为目标，提出了复杂零空闲流水车间调度问题的数学建模及计算方法；（2）针对不同复杂优化问题，深入分析了不同全局和领域搜索策略的性能，提出了一系列群智能优化算法模型；（3）结合调度问题特征，给出了个体编解码策略，并在超启发式算法框架下构建了基于交换、插入、翻转等领域搜索规则的低层次启发式集合；（4）将群智能优化模型作为高层次启发式策略，提出了一种基于反向搜索算法的高效超启发式方法，并有效地应用于求解复杂流水车间调度问题。综合上述相关研究成果，本项目发表SCI国际期刊论文10篇和EI会议论文1篇，申请发明专利2项。项目组与国外同行进行了深入的国际学术交流与合作。