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

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.

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

高效的生产调度优化技术对于提高制造系统生产率和设备资源利用率，缩短产品制造周期具有十分重要的意义。本项目针对典型的柔性作业车间调度问题（简称FJSP），对其邻域结构和求解算法展开研究，在研究过程中，首先对作业车间调度问题（简称JSP）基础理论方法进行研究，然后针对FJSP问题进一步扩展研究。①针对JSP问题，提出了新型邻域结构，科学指导关键工序的移动，根据关键工序的类型定义相应的移动操作。针对FJSP问题的特点，设计了两级邻域搜索方式，第一级邻域搜索为跨机器移动工序，第二级邻域搜索为同机器移动工序，该过程结合JSP问题的新型邻域结构进行实现。②剖析研究了邻域结构本质，针对JSP问题，提出一种有效的移动两个工序邻域结构。基于扩大空闲时间查找区间的思想，科学查找并移动第1个工序，然后，再对关键工序进行移动。在此基础上，提出一种有效的针对FJSP问题移动两个工序邻域结构。针对柔性机器选择问题，提出一种基于加工时间等级的柔性作业车间调度机器选择方法。针对不可行解问题，提出一种基于矩阵的作业车间调度死锁检测与修复方法。③提出一种基于虚拟零部件级别分区编码的调度算法，求解加工与装配并行的FJSP扩展问题，进一步研究，提出一种基于工序约束链编码的遗传算法。④研究了两种不同尺度邻域结构的协同搜索技术，编程开发实现了基于不同尺度邻域结构的FJSP问题混合智能算法系统，并进行了测试验证。本研究对于构造新的FJSP问题求解算法，提高我国制造系统生产效率，具有重要的基础理论意义和工程应用价值。.本项目圆满完成了预期研究目标，取得了一系列基础理论和应用方法研究成果。发表学术论文5篇，其中，EI论文3篇；授权软件著作权3项；申请发明专利3项；培养硕士研究生4名，其中已毕业2名，有2名获得研究生国家奖学金。