目标是最小化最大完工时间带柔性维修时间限制的两台机器排序问题的一个近似算法

doi:10.12005/orms.2021.0155

运筹与管理 ›› 2021, Vol. 30 ›› Issue (5): 129-133.DOI: 10.12005/orms.2021.0155

目标是最小化最大完工时间带柔性维修时间限制的两台机器排序问题的一个近似算法

李刚刚¹, 鲁习文²

1.江西财经大学信息管理学院,江西南昌 330077;
2.华东理工大学理学院,上海 200237

收稿日期:2019-01-13 出版日期:2021-05-25
通讯作者: 鲁习文(1962-),男,教授,博士学位,组合最优化。
作者简介:李刚刚(1985-),男,河南省汝州人,讲师,博士学位,组合最优化。
基金资助:
国家自然科学基金资助项目(11901255);江西省教育厅科技项目(GJJ150447)

An Approximation Algorithm for Two-machine scheduling Problem with Flexible Maintenance to Minimize Makespan

LI Gang-gang¹, LU Xi-wen²

1. Jiangxi University of Finance and Economics, School of Information Managenent, Nanchang 330077, China;
2. East China University of Science and Technology, College of science, Shanghai 200237, China

Received:2019-01-13 Online:2021-05-25

摘要/Abstract

摘要： 本文研究了两台机器带柔性维修时间限制的排序问题,其中第一台机器在固定的时间内必须进行维修,而第二台机器一直可用,目标是最小化所有工件的最大完工时间。工件在加工过程中不允许中断。对于该问题,我们给出了一个性能比为的近似算法,并证明了该性能比是紧的。

关键词: 序, 柔性维修, 算法, 性能比

Abstract: This paper considers a two-machine scheduling problem with flexible maintenance with the objective to minimize makespan. In the scheduling model, the first machine needs maintenance during a fixed period, while the other one is available all the time. Preemption is not allowed. We provide an approximation algorithm with worst-case ratio ofand show that the worst-case ratio is tight.

Key words: scheduling, flexible maintenance, algorithm, worst-case ratio

中图分类号:

O224

李刚刚, 鲁习文. 目标是最小化最大完工时间带柔性维修时间限制的两台机器排序问题的一个近似算法[J]. 运筹与管理, 2021, 30(5): 129-133.

LI Gang-gang, LU Xi-wen. An Approximation Algorithm for Two-machine scheduling Problem with Flexible Maintenance to Minimize Makespan[J]. Operations Research and Management Science, 2021, 30(5): 129-133.

参考文献

[1] Schmidt G. Scheduling with limited machine availability[J]. European Journal of Operational Research, 2000, 121: 1-15.
[2] Sanlaville E, Schmidt G. Machine scheduling with availability constraints[J]. Acta Informatica, 1998, 35: 795-811.
[3] Luo W C, Cheng T C E, Ji M. Single-machine scheduling with a variable maintenance activity[J]. Computers & Industrial Engineering, 2015, 79: 168-174.
[4] Li W X, Zhao C L. Deteriorating jobs scheduling on a single machine with release dates, rejection and a fixed non-availability interval[J]. Journal of Applied Mathematics and Computing, 2015, 48: 585-605.
[5] Zhong X L, Ou J W, Wang G Q. Order acceptance and scheduling with machine availability constraints[J]. European Journal of Operational Research, 2014, 232: 435-441.
[6] Wang S J, Liu M. A branch and bound algorithm for single-machine production scheduling integrated with preventive maintenance planning[J]. International Journal of Production Research, 2013, 51: 847-868.
[7] Luo W C, Ji M. Scheduling a variable maintenance and linear deteriorating jobs on a single machine[J]. Information Processing Letters, 2015, 115: 33-39.
[8] Xu D H, Wan L, Liu A H, Yang D L. Single machine total completion time scheduling problem with workload-dependent maintenance duration[J]. Omega, 2015, 52: 101-106.
[9] Detti P, Nicosia G, Pacifici A, Lara de G Z M. Robust single machine scheduling with a flexible maintenance activity[J]. Computers & Operations Research, 2019, 107: 19-31.
[10] Ji M, He Y, Cheng T C E. Single-machine scheduling with periodic maintenance to minimize makespan[J]. Computers & Operations Research, 2007, 34: 1764-1770.
[11] Yu X Y, Zhang Y L, Steiner G. Single-machine scheduling with periodic maintenance to minimize makespan revisited[J]. Journal of Scheduling, 2014, 17: 263-270.
[12] Nesello V, Subramanian A, Battarra M, Laporte G. Exact solution of the single-machine scheduling problem with periodic maintenances and sequence-dependent setup times[J]. European Journal of Operational Research, 2018, 266: 498-507.
[13] Yin Y Q, Xu J Y, Cheng T C E, Wu C C, Wang D J. Approximation schemes for single-machine scheduling with a fixed maintenance activity to minimize the total amount of late work[J]. Naval Research Logistics, 2016, 63: 172-183.
[14] Liu M, Wang S J, Chu C B, Chu F. An improved exact algorithm for single-machine scheduling to minimize the number of tardy jobs with periodic maintenance[J]. International Journal of Production Research, 2016, 54: 3591-3602.
[15] Luo W C, Liu F. On single-machine scheduling with workload-dependent maintenance duration[J]. Omega, 2017, 68: 119-122.
[16] Cui W W, Lu Z Q. Minimizing the makespan on a single machine with flexible maintenances and jobs' release dates[J]. Computers & Operations Research, 2017, 80: 11-22.
[17] Wang X L, Cheng T C E. A heuristic for scheduling jobs on two identical parallel machines with a machine availability constraint[J]. International Journal of Production Economics, 2015, 161: 74-82.
[18] Hashemian N, Diallo C, Vizvári B. Makespan minimization for parallel machines scheduling with multiple availability constraints[J]. Annals of Operations Research, 2014, 213: 173-186.
[19] Xu D H, Cheng Z M, Yin Y Q, Li H X. Makespan minimization for two parallel machines scheduling with a periodic availability constraint[J]. Computers & Operations Research, 2009, 36: 1809-1812.
[20] Li G G, Lu X W. Two-machine scheduling with periodic availability constraints to minimize makespan[J]. Journal of Industrial and Management Optimization, 2015, 11: 685-700.
[21] Lee J Y, Kim Y D. A branch and bound algorithm to minimize total tardiness of jobs in a two identical-parallel-achine scheduling problem with a machine availability constraint[J]. Journal of the Operational Research Society, 2015, 66: 1542-1554.
[22] Huo Y M, Zhao H R. Two machine scheduling subject to arbitrary machine availability constraint[J]. Omega, 2018, 76: 128-136.
[23] Kaabi J, Harrath Y. Scheduling on uniform parallel machines with periodic unavailability constraints[J]. International Journal of Production Research, 2019, 57: 216-227.
[24] Li D B, Chen K J, Wang X. Properties of two-machine no-wait flow-shop scheduling with a non-resumable unavailable interval[J]. Journal of Industrial and Production Engineering, 2017, 34: 232-238.

目标是最小化最大完工时间带柔性维修时间限制的两台机器排序问题的一个近似算法

An Approximation Algorithm for Two-machine scheduling Problem with Flexible Maintenance to Minimize Makespan

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	刘琴, 申海, 黎建强. 基于部件指派的多状态系统可靠度优化研究[J]. 运筹与管理, 2021, 30(9): 25-30.
[2]	郑红星, 段爽, 孙丛. 考虑翻箱的场桥调度和提箱集卡数量的集成优化[J]. 运筹与管理, 2021, 30(9): 48-55.
[3]	陈煜婷, 张惠珍. 双层级医疗设施选址问题及禁忌搜索算法[J]. 运筹与管理, 2021, 30(9): 56-63.
[4]	闫妍, 张锦, 唐秋宇, 张洪基. 航线联盟下航空货运网络枢纽点选址问题研究[J]. 运筹与管理, 2021, 30(9): 64-72.
[5]	初良勇, 左世萍, 阮志毅. 考虑退货不确定性的多层次多站点逆向物流网络选址优化研究[J]. 运筹与管理, 2021, 30(9): 73-79.
[6]	丁肇炜, 杨建华, 王艾, 王欣. 面向突发事件的安保巡逻选址-路径优化研究[J]. 运筹与管理, 2021, 30(8): 1-6.
[7]	马咏, 何正文, 江波, 王能民. 一种求解柔性资源约束前摄性项目调度问题的启发式算法[J]. 运筹与管理, 2021, 30(8): 14-20.
[8]	庞南生, 叶博童. 项目鲁棒调度的资源分配启发式算法研究[J]. 运筹与管理, 2021, 30(8): 21-27.
[9]	刘万琳, 张静文, 刘婉君. 带有资源柔性约束的max-NPV分布式多项目调度问题[J]. 运筹与管理, 2021, 30(8): 37-43.
[10]	胡修武, 徐悦, 王秀利. 呼叫中心坐席人员排班问题优化模型与算法研究[J]. 运筹与管理, 2021, 30(8): 44-51.
[11]	王愚勤, 胡卉, 刘富鑫, 王艳慧, 赵姣, 韩毅. 智能网联下无人车配送路径优化[J]. 运筹与管理, 2021, 30(8): 52-58.
[12]	金苗苗, 吴蒙洁, 罗文昌. 具有不可用区间且工件可拒绝下的单机重新排序问题的近似方案[J]. 运筹与管理, 2021, 30(8): 87-92.
[13]	邱莹莹, 王尔大, 于洋. 基于贝叶斯多元有序probit模型的休闲渔业游客满意度研究[J]. 运筹与管理, 2021, 30(8): 147-152.
[14]	刘畅, 姚建明. 高铁场景下的无人零售终端补货供应链调度优化研究[J]. 运筹与管理, 2021, 30(7): 9-15.
[15]	陈伟, 张玉林. “仓店一体化”模式下订单拣选与配送集成调度优化[J]. 运筹与管理, 2021, 30(7): 16-22.