考虑最小化最大完工时间间隔的三台平行机调度

郑斐峰, 隋杨, 徐寅峰

系统工程理论与实践 ›› 2021, Vol. 41 ›› Issue (4) : 1025-1036.

PDF(1013 KB)
PDF(1013 KB)
系统工程理论与实践 ›› 2021, Vol. 41 ›› Issue (4) : 1025-1036. DOI: 10.12011/SETP2019-1370
论文

考虑最小化最大完工时间间隔的三台平行机调度

    郑斐峰, 隋杨, 徐寅峰
作者信息 +

Three parallel machines scheduling with minimizing the maximum inter-completion time

    ZHENG Feifeng, SUI Yang, XU Yinfeng
Author information +
文章历史 +

摘要

针对平行机调度,研究了当无预知情况下应对紧急任务快速响应的一类加工方案.考虑三台平行机的加工环境,分析任意两个相邻的工件完工时间的间隔,以最小化最大间隔值为优化目标.首先给出机器完工时间的两个上界作为可行方案的充分条件,进而给出最优方案的基本性质;其次,基于最优解的性质证明了目标值的一个下界并设计了On2)时间的算法来求解该下界值;最后运用预留尽可能多的空闲时间(RMST)在一台机器上的思想,设计了改进的RMST算法(IRMST)来求解该问题.通过利用数值仿真实验与RMST算法,遗传算法等其它算法及下界进行对比,验证了该算法的有效性.

Abstract

This work studies the processing schedules of parallel machines with strong response abilities to unexpected and urgent jobs. We consider the job scheduling on three parallel machines, aiming to minimize the maximum difference between the completion times of any two consecutively completed jobs, in other words, to minimize the maximum inter-completion time. We first give two upper bounds of the workload of machines which is the sufficient condition of feasible solutions. Based on the sufficient condition, we first give several basic properties of the optimal solution. Secondly, we further prove a lower bound of the objective value and design an O(n2) time algorithm to calculate the lower bound. Finally, we develop an improved algorithm based on the RMST algorithm to solve the considered problem, in which the RMST algorithm considers the case that one may reserve as much spare time as possible on one of the machines. Through computational comparisons between the improved algorithm and RMST algorithm together with the genetic algorithm and the lower bound of objective value, it is shown that our algorithm outperforms the other two algorithms. Numerical experiments verify the effectiveness of the improved algorithm.

关键词

平行机调度 / 完工时间间隔 / 启发式算法

Key words

parallel machines scheduling / inter-completion time / heuristic algorithm

引用本文

导出引用
郑斐峰 , 隋杨 , 徐寅峰. 考虑最小化最大完工时间间隔的三台平行机调度. 系统工程理论与实践, 2021, 41(4): 1025-1036 https://doi.org/10.12011/SETP2019-1370
ZHENG Feifeng , SUI Yang , XU Yinfeng. Three parallel machines scheduling with minimizing the maximum inter-completion time. Systems Engineering - Theory & Practice, 2021, 41(4): 1025-1036 https://doi.org/10.12011/SETP2019-1370
中图分类号: TP301.6   

参考文献

[1] Zheng F F, Pinedo M L, Lee K, et al. Towards robustness of response times:Minimizing the maximum inter-completion time on parallel machines[J].International Journal of Production Research, 2019, 57(1):182-199.
[2] Su L H, Wang H M. Minimizing total absolute deviation of job completion times on a single machine with cleaning activities[J].Computers & Industrial Engineering, 2017, 103:242-249.
[3] 刘乐, 周泓. 急件到达干扰下开放式车间重调度方法[J]. 计算机集成制造系统, 2014, 20(7):1631-1642. Liu L, Zhou H. Open shop rescheduling approach under unexpected arrival of a rush job[J]. Computer Integrated Manufacturing Systems, 2014, 20(7):1631-1642.
[4] Arnaout J P, Rabadi G. Rescheduling of unrelated parallel machines under machine breakdowns[J]. International Journal of Applied Management Science, 2008, 1(1):75-89.
[5] Gurel S, Cincioglu D. Rescheduling with controllable processing times for number of disrupted jobs and manufacturing cost objectives[J]. International Journal of Production Research, 2015, 53(9):2751-2770.
[6] Long J, Zheng Z, Gao X. Dynamic scheduling in steelmaking-continuous casting production for continuous caster breakdown[J]. International Journal of Production Research, 2017, 55(11):3197-3216.
[7] 薄洪光, 张鑫, 潘裕韬. 考虑行为特征的复杂流水线干扰管理调度方法[J]. 系统管理学报, 2018, 27(2):309-318. Bo H G, Zhang X, Pan Y T. Disruption management approach to complex flow shop scheduling considering behavior features[J]. Journal of Systems & Management, 2018, 27(2):309-318.
[8] Levin A, Mosheiov G, Sarig A. Scheduling a maintenance activity on parallel identical machines[J]. Naval Research Logistics, 2010, 56(1):33-41.
[9] Yin Y Q, Cheng T C E, Wang D J. Rescheduling on identical parallel machines with machine disruptions to minimize total completion time[J]. European Journal of Operational Research, 2016, 252(3):737-749.
[10] Luo W C, Luo T B, Goebel R, et al. Rescheduling due to machine disruption to minimize the total weighted completion time[J]. Journal of Scheduling, 2018, 21(5):565-578.
[11] Mosheiov G. Minimizing total absolute deviation of job completion times:Extensions to position-dependent processing times and parallel identical machines[J]. Journal of the Operational Research Society, 2008, 59(10):1422-1424.
[12] Mor B, Mosheiov G. Total absolute deviation of job completion times on uniform and unrelated machines[J]. Computers & Operations Research, 2011, 38(3):660-665.
[13] Erel E, Ghosh J B. Minimizing weighted mean absolute deviation of job completion times from their weighted mean[J]. Applied Mathematics & Computation, 2011, 217(22):9340-9350.
[14] Hariri E. A note on minimizing total absolute deviation of job completion times on a two-machine no-wait proportionate flow shop[J]. International Journal of Production Research, 2014, 53(19):1-8.
[15] 朱雷, 黎建强, 汪明. 不确定条件下应急管理人力供应链多功能资源配置鲁棒优化问题[J]. 系统工程理论与实践, 2015, 35(3):736-742. Zhu L, Li J Q, Wang M. Multi-resource robust optimization of emergency human resource supply chain management under uncertainty[J]. Systems Engineering-Theory & Practice, 2015, 35(3):736-742.
[16] 彭春, 李金林, 王珊珊, 等. 多类应急资源配置的鲁棒选址-路径优化[J]. 中国管理科学, 2017, 25(6):143-150. Peng C, Li J L, Wang S S, et al. Multiple relief resources robust location-routing optimization[J]. Chinese Journal of Management Science, 2017, 25(6):143-150.
[17] Rahmani D, Heydari M. Robust and stable flow shop scheduling with unexpected arrivals of new jobs and uncertain processing times[J]. Journal of Manufacturing Systems, 2014, 33(1):84-92.
[18] 宁涛, 王旭坪, 胡祥培. 行驶受扰延迟下配送车辆调度的干扰管理决策模型[J]. 系统工程理论与实践, 2019, 39(5):1236-1245. Ning T, Wang X P, Hu X P. Disruption management decision model for vehicle scheduling under traffic disruption delay[J]. Systems Engineering-Theory & Practice, 2019, 39(5):1236-1245.
[19] Liu F, Wang S, Hong Y, et al. On the robust and stable flow shop scheduling under stochastic and dynamic disruptions[J]. IEEE Transactions on Engineering Management, 2017, 64(4):539-553.
[20] 唐秋华, 何明, 何晓霞, 等. 随机工时下柔性加工车间的鲁棒优化调度方法[J]. 计算机集成制造系统, 2015, 21(4):1002-1012. Tang Q H, He M, He X X, et al. Robust optimization scheduling of flexible job shops under stochastic processing times[J]. Computer Integrated Manufacturing Systems, 2015, 21(4):1002-1012.
[21] 王建军, 刘晓盼, 刘锋, 等. 随机机器故障下加工时间可控的并行机鲁棒调度[J]. 中国管理科学, 2017, 25(3):137-146. Wang J J, Liu X P, Liu F, et al. Robust scheduling of unrelated machines subject to stochastic breakdowns and controllable processing times[J]. Chinese Journal of Management Science, 2017, 25(3):137-146.
[22] Che A, Kats V, Levner E. An efficient bicriteria algorithm for stable robotic flow shop scheduling[J]. European Journal of Operational Research, 2017, 260(3):964-971.
[23] 曾庆成, 胡祥培, 杨忠振. 集装箱码头泊位分配-装卸桥调度干扰管理模型[J]. 系统工程理论与实践, 2010, 30(11):2026-2035. Zeng Q C, Hu X P, Yang Z Z. Model for disruption management of breth allocation & quay crane scheduling in container terminals[J]. Systems Engineering-Theory & Practice, 2010, 30(11):2026-2035.
[24] Xiang W, Yin J, Lim G. A short-term operating room surgery scheduling problem integrating multiple nurses roster constraints[J]. Artificial Intelligence in Medicine, 2015, 63(2):91-106.

基金

国家自然科学基金重点项目(71832001);国家自然科学基金(71771048,71531011,71571134)
PDF(1013 KB)

738

Accesses

0

Citation

Detail

段落导航
相关文章

/