求解流水车间订单接受与调度问题的多线程并行迭代贪婪算法  

Multi-thread parallel iterated greedy for flow shop order acceptance and scheduling problem

作　　者：熊福力 袁子阳 XIONG Fuli;YUAN Ziyang(School of Information and Control Engineering,Xi’an University of Architecture and Technology,Xi’an 710055,China)

机构地区：[1]西安建筑科技大学信息与控制工程学院,陕西西安710055

出　　处：《计算机集成制造系统》2024年第11期3918-3928,共11页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(61473216);陕西省自然科学基础研究计划资助项目(2023-JC-YB-582)。

摘　　要：针对流水车间实际生产过程中交货期短和生产能力不足的困难,研究了流水车间订单接受与调度问题,并以企业生产总净利润最大化为目标建立了数学优化模型。鉴于传统迭代贪婪算法求解流水车间调度问题的优势与不足之处,提出了一种多线程并行迭代贪婪算法(MPIG)。在算法的初始化阶段以及破坏重构阶段分别设计基于NEH(Nawaz-Enscore-Ham)的初始解产生方法以及融合不同破坏优先级的破坏方式。为提高算法搜索效率,提出了一种多线程并行搜索策略。首先利用二分查找算法快速找到订单在待插入序列中的拒绝点,随后通过多个线程同时搜索订单在序列中的局部最优位置,并最终找到订单最佳插入位置。实验结果表明,与解决类似生产调度问题的相关智能优化算法相比,所提出的MPIG具有更好的求解质量以及求解稳定性。同时,与实际生产过程中常用的启发式调度方法相比,所提出的算法在目标值上表现出不低于11%的改进率,可以有效增加企业生产总净利润,减小拖期成本。Aiming at the difficulties of short due date and insufficient production capacity in the actual production process of flow shop,the order acceptance and scheduling problem of flow shop was studied,and a mathematical optimization model was established to maximize the total net profit of production.In view of the advantages and disadvantages of traditional iterated greedy algorithms in solving flow shop scheduling problems,a Multi-Thread Parallel Iterated Greedy algorithm(MPIG)was proposed.In the initialization phase and the destruction reconstruction phase of the algorithm,the initial solution generation method based on Nawaz-Enscore-Ham(NEH)and the destruction method combining different destruction priorities were designed respectively.To improve the search efficiency,a multi-thread parallel search strategy was proposed.The binary search algorithm was used to find the rejection position of the order in the sequence to be inserted.Then,multiple threads were used to search the local optimal position of the order in the sequence.Finally,the best insertion position of the order was found.Experimental results showed that the proposed MPIG had better solution quality and stability by comparing with other intelligent optimization algorithms for similar production scheduling problems.At the same time,compared with the heuristic scheduling method commonly used in the actual production process,the proposed algorithm showed an improvement rate of no less than 11%on the target value,which could effectively increase the total net profit and reduce the delay cost.

关 键 词：流水车间 交货期 订单接受与调度 多线程并行迭代贪婪算法 二分查找算法 

分 类 号：TH186[机械工程—机械制造及自动化] TP18[自动化与计算机技术—控制理论与控制工程]