求解流水车间订单接受与调度问题的多线程并行迭代贪婪算法
来源：计算机集成制造系统杂志2024年第11期北京时间：
作者：熊福力, 袁子阳
单位：西安建筑科技大学信息与控制工程学院
摘要：针对流水车间实际生产过程中交货期短和生产能力不足的困难,研究了流水车间订单接受与调度问题,并以企业生产总净利润最大化为目标建立了数学优化模型。鉴于传统迭代贪婪算法求解流水车间调度问题的优势与不足之处,提出了一种多线程并行迭代贪婪算法(MPIG)。在算法的初始化阶段以及破坏重构阶段分别设计基于NEH(Nawaz-Enscore-Ham)的初始解产生方法以及融合不同破坏优先级的破坏方式。为提高算法搜索效率,提出了一种多线程并行搜索策略。首先利用二分查找算法快速找到订单在待插入序列中的拒绝点,随后通过多个线程同时搜索订单在序列中的局部最优位置,并最终找到订单最佳插入位置。实验结果表明,与解决类似生产调度问题的相关智能优化算法相比,所提出的MPIG具有更好的求解质量以及求解稳定性。同时,与实际生产过程中常用的启发式调度方法相比,所提出的算法在目标值上表现出不低于11%的改进率,可以有效增加企业生产总净利润,减小拖期成本。
关键词：流水车间,交货期,订单接受与调度,多线程并行迭代贪婪算法,二分查找算法
基金资助：国家自然科学基金资助项目(61473216);陕西省自然科学基础研究计划资助项目(2023-JC-YB-582)。
