A Heuristic for Inserting Randomly Arriving Jobs Into an Existing Hoist Schedule
A Heuristic for Inserting Randomly Arriving Jobs Into an Existing Hoist Schedule
复制标题
DOI：
10.1109/tase.2017.2749429
复制
发表时间：
2018-07
影响因子：
5.6
通讯作者：
Pengyu Yan;A. Che;E. Levner;Shi Qiang Liu
中科院分区：
文献类型：
--
作者：
Pengyu Yan;A. Che;E. Levner;Shi Qiang Liu
在静态环境下，对自动电镀生产线的提升机调度进行了广泛的研究。然而，实际的电镀生产线受到多样化的不可预见的中断，需要频繁的重新调度，以保持或优化系统性能。本文讨论了起重机调度问题，随机到达的工作需要插入到一个现有的时间表，而不改变顺序的起重机移动已经安排。目标是最小化现有计划中所有工件和新插入工件的总完工时间。我们开发了一个多项式时间的启发式，调整现有的起重机移动的开始时间在有限的程度上，但不会带来严重的干扰现有的起重机移动。我们比较我们的算法与两个现有的方法与不同的重新调度政策（即，现有时间表的部分和零调整）。我们实证分析的生产率和稳定性的时间表所产生的三种方法。计算结果表明，我们的算法可以产生更多的生产力和稳定的时间表比现有的两种方法。从业人员注意事项-在电子、半导体和许多其他制造业中，配备自动化物料搬运提升机的电镀和化学表面处理生产线是常见的。在不确定的环境下，提升机重新调度对于提高生产率和减少中断影响发挥着重要作用。本文提出了一种起重机调度算法，以处理动态工件到达，通过考虑的影响，重新调度引起的干扰。与现有的调度算法相比，该算法能够产生总完工时间更小、扰动更小的调度方案。该算法在多项式时间内运行，可用于实际电镀生产线的提升操作控制。比较分析为行业从业者提供了关于重组方法和政策实施的有用见解。
Hoist scheduling in automated electroplating lines has been extensively studied in a static environment. However, practical electroplating lines are subject to diversified unforeseen disruptions that require frequent rescheduling to maintain or optimize system performance. This paper addresses a hoist scheduling problem, where randomly arriving jobs need to be inserted into an existing schedule without changing the sequence of hoist moves already scheduled. The objective is to minimize the total completion time of all the jobs in the existing schedule and a newly inserted job. We develop a polynomial-time heuristic that adjusts the starting times of the existing hoist moves to a limited extent but does not bring about a severe disturbance of the existing hoist moves. We compare our algorithm with two existing approaches with different rescheduling policies (i.e., partial and zero adjustment of the existing schedule). We empirically analyze the productivity and the stability of the schedules generated by the three approaches. Computational results demonstrate that our algorithm can generate more productive and stable schedules than the two existing approaches. Note to Practitioners—Electroplating and chemical surface treatment lines with automated material handling hoists are commonplace in electronics, semiconductor, and many other manufacturing industries. In an uncertain environment, hoist rescheduling plays an important role in improving the productivity and reducing the impact of disruptions. This paper presents a hoist scheduling algorithm to deal with dynamic job arrivals by considering the impact of the disturbance incurred by rescheduling. Our algorithm can generate a better schedule with smaller total completion time and slighter disturbance than the existing algorithms. The proposed algorithm runs in polynomial time and can be used to control hoist operations in practical electroplating lines. A comparative analysis provides useful insights on the implementation of rescheduling approaches and policies to industry practitioners.