柔性作业车间调度问题的两种不同尺度邻域结构及算法设计研究

柔性作业车间调度问题(Flexible Job Shop Scheduling Problem，FJSP)突破了机器唯一性约束，工序可能在多台机器上加工，更加符合生产实际。邻域结构是构造FJSP问题高效求解算法的一项共性关键技术，当移动1个工序不能改进当前解时，通过移动2个工序实现邻域搜索，是提高算法性能的有效途径。本项目以优化最大完工时间为目标，开展基于两种不同尺度邻域结构的FJSP问题求解算法研究。首先，研究更为强化的基于移动1个工序邻域结构，对其进行无效移动精简和有效移动扩展；然后，研究基于移动2个工序邻域结构，提出对2个工序分步移动的思想，研究其相关技术；最后，基于上述两种不同尺度邻域结构，综合考虑算法的全局搜索能力和局部搜索能力，设计求解FJSP问题的混合智能优化算法。本研究对于构造新的FJSP问题求解算法，提高我国制造系统生产效率，具有重要的理论意义和工程应用价值。

Flexible job shop scheduling problem (FJSP) is more in line with the actual production environment. It breaks through machine uniqueness constraint, and the operation may be processed by more than one machine. Neighborhood structure is a common key technology for constructing efficient algorithms of FJSP. When the current solution can’t be improved by moving one operation, to move two operations is an effective way. Taking the minimum makespan as objective, it studies solution algorithm for FJSP based on neighborhood structures of two different scales in this project. Firstly, a more reinforcement one-operation-based neighborhood structure is to be studied, to reduce its invalid move and extend the effective move. Then, it studies the two-operation-based neighborhood structure. Based on the idea of moving two operations step by step, it studies the related implementation technologies. Finally, considering global search ability and local search ability, to design efficient hybrid algorithms for solving FJSP based on the neighborhood structures mentioned above. This study has important theoretical significance and engineering application value, to construct new FJSP solution algorithms and improve production efficiency of our manufacturing systems.