机械工程学报

作者：赵诗奎, 黄林, 吕杰

单位：济南大学机械工程学院 济南 250022

关键词：作业车间调度问题,多工序联动,邻域结构,近似评价,最大完工时间；

基金：国家自然科学基金资助项目(51775240)。

针对作业车间调度问题(Job shop scheduling problem，JSP)，以优化最大完工时间为目标，提出一种强化搜索的多工序联动邻域结构与近似评价方法。分析交换工序块边缘两工序的空闲时间利用机理，对已有多工序联动邻域结构的空闲时间边界范围进行了有效扩展。在交换工序块边缘两工序的同时，基于扩展的空闲时间边界范围判定条件，根据最早开完工时间查找前移工序的工件某一前序工序，将其与紧密相邻机器前序工序进行交换操作。根据最晚开完工时间查找后移工序的工件某一后序工序，将其与紧密相邻机器后序工序进行交换操作。新的多工序联动邻域结构能够尽可能充分利用原有工序块相邻空闲时间和移动工序形成的空闲时间，具有更为强化的搜索能力。基于工序头尾长度理论研究了多工序联动邻域结构的近似评价方法。采用JSP基准算例进行测试，测试结果验证了强化多工序联动邻域结构的有效性，以及所提出的近似评价方法具有较高的准确性。邻域结构和近似评价作为JSP问题的基础研究，对于实现结合问题特征知识的JSP有效求解具有重要意义。

来源：2023年第4期

《机械工程学报》期刊编辑部

查看机械工程学报杂志2023年第4期