作业车间调度问题的多工序联动邻域结构研究

发布时间：2024-03-10 15:31

　　针对作业车间调度问题(Job shop scheduling problem,JSP),以优化最大完工时间为目标,提出一种有效的多工序联动邻域结构。邻域结构真正将JSP求解算法的盲目搜索变得更加科学有效,同时移动多个工序是进一步提升邻域结构性能的关键。针对交换两个工序邻域结构,从理论上剖析了如何进行多工序联动能够优化最大完工时间。对已有多工序联动邻域结构存在的不足进行了分析,提出了科学有效的最多同时交换3对工序的多工序联动邻域结构。在交换关键工序块边缘工序的同时,根据最早开完工时间查找前移工序的工件前序工序,对其进行前移交换操作,根据最晚开完工时间查找后移工序的工件后序工序,对其进行后移交换操作。提出了更为宽泛的针对2个工序交换操作的可行解保障条件,在此基础上,扩展了同时交换2对工序和3对工序的可行解保障条件。对JSP基准算例进行测试,验证了所提邻域结构具有良好的性能,对于设计更为高效的JSP求解算法具有重要意义。

【文章页数】：15 页

【部分图文】：

图1ft06算例的一个调度解(Cmax=82)

图1所示为ft06算例的一个调度解(Cmax=82)，为了便于分析研究，给出了最早开完工时间甘特图(便于查看工序头长度)和最晚开完工时间甘特图(便于查看工序尾长度)，分别如图1a和1b所示，每台机器上工序的加工顺序，以及对应的最大完工时间Cmax完全相同。矩形框中的数字(4,2,....

图2ft06算例CET邻域结构的一个邻域解(交换工序7-26得到，Cmax=84)

在图2所示的CET邻域结构操作交换工序7-26基础上，再交换工序1-25和8-21，得到CET+2MT邻域结构操作邻域解如图3所示。可见，与CET邻域结构Cmax=84相比，CET+2MT邻域结构Cmax=83，在CET邻域结构的基础上，能够减小最大完工时间。但是，CET+2MT....

图3ft06算例CET+2MT邻域结构的一个邻域解(交换工序1-25,7-26,8-21得到，Cmax=83)

(7)如果JS[u"]=Φ，结束；否则，设置u"=JS[u"]，转至步骤(6)。图4ICET+2MT多工序联动邻域结构示意图

图4ICET+2MT多工序联动邻域结构示意图

图3ft06算例CET+2MT邻域结构的一个邻域解(交换工序1-25,7-26,8-21得到，Cmax=83)在图2所示的CET邻域结构操作交换工序7-26基础上，再交换工序1-25和10-15，得到ICET+2MT邻域结构操作邻域解如图5所示。可见，与CET邻域结构Cmax=....

本文编号：3925010