Abstract: 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.

Key words: flow shop, due date, order acceptance and scheduling, multi-thread parallel iterated greedy, binary search algorlthm

摘要： 针对流水车间实际生产过程中交货期短和生产能力不足的困难,研究了流水车间订单接受与调度问题,并以企业生产总净利润最大化为目标建立了数学优化模型。鉴于传统迭代贪婪算法求解流水车间调度问题的优势与不足之处,提出了一种多线程并行迭代贪婪算法(MPIG)。在算法的初始化阶段以及破坏重构阶段分别设计基于NEH(Nawaz-Enscore-Ham)的初始解产生方法以及融合不同破坏优先级的破坏方式。为提高算法搜索效率,提出了一种多线程并行搜索策略。首先利用二分查找算法快速找到订单在待插入序列中的拒绝点,随后通过多个线程同时搜索订单在序列中的局部最优位置,并最终找到订单最佳插入位置。实验结果表明,与解决类似生产调度问题的相关智能优化算法相比,所提出的MPIG具有更好的求解质量以及求解稳定性。同时,与实际生产过程中常用的启发式调度方法相比,所提出的算法在目标值上表现出不低于11%的改进率,可以有效增加企业生产总净利润,减小拖期成本。

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