Rolling Horizon Approach for Dynamic Parallel Machine Scheduling Problem with Release Times
Rolling Horizon Approach for Dynamic Parallel Machine Scheduling Problem with Release Times
复制标题
DOI：
10.1021/ie900206m
复制
发表时间：
2010-01-06
影响因子：
4.2
通讯作者：
Liu, Jiyin
中科院分区：
文献类型：
--
作者：
Tang, Lixin;Jiang, Shujun;Liu, Jiyin
本文研究了一类带放行时间的动态平行机排序问题，其中工件的放行时间和加工时间在生产过程中由于不确定性而可能发生变化。该问题不同于确定性环境中的经典调度问题，在确定性环境中，工件的所有信息在调度期开始时是已知的，并且在整个调度期内的操作过程中不会发生变化。在实践中，经常有不可预测的事件导致作业发布时间和/或处理时间的动态变化。传统的优化方法虽然成功地解决了动态调度问题的静态版本，但不能直接解决动态调度问题。采用基于滚动时域的模型预测控制（MPC）策略，以最小化工件的加权总完工时间、工件等待所消耗的能量以及工件实际完工时间与原计划的总偏差为目标，研究了动态并行机调度问题.当MPC应用于问题时，滚动时域方法允许应用拉格朗日松弛（LR）算法以滚动方式求解调度问题的模型。通过计算实验，将该方法与人类驾驶员常采用的被动调整方法进行了比较。实验结果表明，该方法的效果明显优于传统方法，平均提高了11.72%。
In this paper, we Study a dynamic parallel machine scheduling problem with release times, where the release times and processing times of jobs may change during the production process due to uncertainties. The problem is different from classical scheduling problems in the deterministic environment where all information of jobs is known at the beginning of the scheduling horizon and will not change during the operations throughout the whole horizon. In practice, there are often unpredictable events causing dynamic changes in job release times and/or processing times. Traditional optimization methods cannot solve the dynamic scheduling problem directly even though they have been successful in solving the static version of the problem. A model predictive control (MPC) strategy based rolling horizon approach is applied to tackle the dynamic parallel machine scheduling problem with the objective of minimizing the total weighted completion times of jobs, the energy consumption due to job waiting, and the total deviation of actual job completion times front those in the original schedule. When the MPC is applied to the problem, the rolling horizon approach allows applying a Lagrangian relaxation (LR) algorithm to solve the model of the scheduling problem in a rolling fashion. Computational experiments are carried Out comparing the proposed method with the passive adjustment method often adopted by human schedulers. The result shows that the proposed method yields significantly better results, with 11.72% improvement on average.