带有退化维护活动和工件可拒绝的非同类机排序问题

doi:10.15960/j.cnki.issn.1007-6093.2023.03.011

运筹学学报 ›› 2023, Vol. 27 ›› Issue (3): 137-149.doi: 10.15960/j.cnki.issn.1007-6093.2023.03.011

带有退化维护活动和工件可拒绝的非同类机排序问题

高洁¹, 邹娟¹, 隋玉康¹, 张玉忠²^,*()

1. 曲阜师范大学数学科学学院, 山东曲阜 273165
2. 曲阜师范大学运筹学研究院, 山东日照 276826

收稿日期:2022-01-18 出版日期:2023-09-15 发布日期:2023-09-14
通讯作者: 张玉忠 E-mail:yuzhongrz@163.com
作者简介:张玉忠, E-mail: yuzhongrz@163.com
基金资助:
国家自然科学基金(12271295)

Unrelated parallel-machine scheduling with deteriorating maintenance activities and job rejection

Jie GAO¹, Juan ZOU¹, Yukang SUI¹, Yuzhong ZHANG²^,*()

1. School of Mathematical Sciences, Qufu Normal University, Qufu 273165, Shandong, China
2. Institute of Operation Research, Qufu Normal University, Rizhao 276826, Shandong, China

Received:2022-01-18 Online:2023-09-15 Published:2023-09-14
Contact: Yuzhong ZHANG E-mail:yuzhongrz@163.com

摘要/Abstract

摘要：

本文研究了带有退化维护活动和工件可拒绝的非同类机排序问题。每台机器至多执行一次退化维护活动，退化维护活动的维护时长是其开始时刻的线性非减函数。工件或者被加工并支付生产成本，或者被拒绝并支付拒绝成本。目标是确定每台机器上退化维护活动的位置与所有接受工件的加工顺序使所有接受工件的排序指标、生产成本及所有拒绝工件的拒绝惩罚之和达到最小。当排序指标为最大完工时间时，我们给出一个最坏性能比为2的近似算法。当排序指标为总完工时间、机器总负载及完工时间的总绝对偏差时，我们指出这三个问题都是在多项式时间内可解的。

关键词: 排序, 非同类机, 退化维护活动, 近似算法

Abstract:

We study unrelated parallel-machine scheduling problems with deteriorating maintenance activities and job rejection. Each machine has at most one deteriorating maintenance activity throughout the scheduling horizon. The duration of the maintenance activity increases linearly with its starting time. Each job is either processed and it incurs a production cost, or is rejected with a penalty cost. The objective is to find the position of the maintenance activity of each machine and the sequence of the accepted jobs such that the scheduling cost of all accepted jobs plus the total cost of rejecting and processing jobs is minimized. When the scheduling cost is the makespan, we provide an approximation algorithm with worst-case ratio of 2. When the scheduling costs are the total completion time, the total machine load and the total absolute deviation of completion times, we show that the three versions of the scheduling problem can be optimally solved in polynomial time.

Key words: scheduling, unrelated machine, deteriorating maintenance activity, approximation algorithm

中图分类号:

O221.7

高洁, 邹娟, 隋玉康, 张玉忠. 带有退化维护活动和工件可拒绝的非同类机排序问题[J]. 运筹学学报, 2023, 27(3): 137-149.

Jie GAO, Juan ZOU, Yukang SUI, Yuzhong ZHANG. Unrelated parallel-machine scheduling with deteriorating maintenance activities and job rejection[J]. Operations Research Transactions, 2023, 27(3): 137-149.

参考文献 22

1	Lee C Y , Leon V J . Machine scheduling with a rate modifying activity[J]. European Journal of Operational Research, 2001, 128, 119- 128. doi: 10.1016/S0377-2217(99)00066-1
2	Kubzin M A , Strusevich V A . Planning machine maintenance in two-machine shop scheduling[J]. Operations Research, 2006, 54, 789- 800. doi: 10.1287/opre.1060.0301
3	Mosheiov G , Sidney J B . Scheduling a deteriorating maintenance activity on a single machine[J]. Journal of the Operational Research Society, 2010, 61, 882- 887. doi: 10.1057/jors.2009.5
4	Wang L Y , Huang X , Ji P , et al. Unrelated parallel-machine scheduling with a deteriorating maintenance activity to minimize the total completion time[J]. Optimization Letters, 2014, 8 (1): 129- 134. doi: 10.1007/s11590-012-0472-x
5	Zou J , Yuan J J . Equivalence of some different maintenance activities in single-machine scheduling[J]. Journal of the Operations Research Society of China, 2018, 6, 545- 556. doi: 10.1007/s40305-017-0182-2
6	Chung T P , Gupta J N D , Qiu M . Single machine scheduling problem with batch setups involving positional deterioration effects and multiple rate-modifying activities[J]. Engineering Optimization, 2019, 51, 1743- 1760. doi: 10.1080/0305215X.2018.1552269
7	Delorme M , Iori M , Mendes N F M . Solution methods for scheduling problems with sequencedependent deterioration and maintenance events[J]. European Journal of Operational Research, 2021, 3, 823- 837.
8	Mosheiov G , Daniel O . A note on scheduling a rate modifying activity to minimize total late work[J]. Computers & Industrial Engineering, 2021, 154, 107138.
9	Yu T S , Han J H . Scheduling proportionate flow shops with preventive machine maintenance[J]. International Journal of Production Economics, 2020, 231, 107874.
10	Zou J , Yuan J J . Single-machine scheduling with maintenance activities and rejection[J]. Discrete Optimization, 2020, 38, 100609. doi: 10.1016/j.disopt.2020.100609
11	Bartal Y , Leonardi S , Spaccamela A M , et al. Multiprocessor scheduling with rejection[J]. SIAM Journal on Discrete Mathematics, 2000, 13, 64- 78. doi: 10.1137/S0895480196300522
12	Shabtay D , Gasper N , Kaspi M . A survey on offline scheduling with rejection[J]. Journal of Scheduling, 2013, 16, 3- 28. doi: 10.1007/s10951-012-0303-z
13	Zhang L Q , Lu L F . Parallel-machine scheduling with release dates and rejection[J]. 4OR-A Quarterly Journal of Operations Research, 2016, 14, 165- 172. doi: 10.1007/s10288-016-0304-4
14	Liu P , Lu X . New approximation algorithms for machine scheduling with rejection on single and parallel machine[J]. Journal of Combinatorial Optimization, 2020, 40, 1- 24. doi: 10.1007/s10878-020-00561-9
15	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24, 111- 130.
16	Koulamas C , Steiner G . New results for scheduling to minimize tardiness on one machine with rejection and related problems[J]. Journal of Scheduling, 2021, 24, 27- 34. doi: 10.1007/s10951-020-00671-6
17	Li S S , Chen R X . Scheduling with rejection and a deteriorating maintenance activity on a single machine[J]. Asia-Pacific Journal of Operational Research, 2017, 34, 1750010. doi: 10.1142/S0217595917500105
18	Jiang D K , Tan J Y . Scheduling with job rejection and nonsimultaneous machine available time on unrelated parallel machines[J]. Theoretical Computer Science, 2016, 616, 94- 99. doi: 10.1016/j.tcs.2015.12.020
19	Lenstra J K , Shmoys D B , Tardos S E . Approximation algorithms for scheduling unrelated parallel machines[J]. Mathematical Programming, 1990, 46, 259- 271. doi: 10.1007/BF01585745
20	Karmarkar N . A new polynomial-time algorithm for linear programming[J]. Combinatorica, 1984, 4 (4): 373- 395. doi: 10.1007/BF02579150
21	Cheng T C E , Hsu C J , Yang D L . Unrelated parallel-machine scheduling with deteriorating maintenance activities[J]. Computers & Industrial Engineering, 2011, 60, 602- 605.
22	Brucker P . Scheduling Algorithm[M]. Berlin: Springer-Verlag, 2007.

[1]	袁藩, 徐大川, 张冬梅. k-均值问题的差分隐私算法综述[J]. 运筹学学报, 2022, 26(3): 1-16.
[2]	张安, 陈永, 陈光亭, 陈占文, 舒巧君, 林国辉. 优先序约束的排序问题：基于最大匹配的近似算法[J]. 运筹学学报, 2022, 26(3): 57-74.
[3]	龚铭炀, 谈之奕, 严羽洁. 两台同类机排序问题SPT算法的最坏情况比[J]. 运筹学学报, 2022, 26(3): 92-108.
[4]	成夏炎, 何滢, 赵聪聪, 李荣珩. 两台自私型机器上自私工件排序的PoA紧界[J]. 运筹学学报, 2022, 26(3): 109-119.
[5]	王冬, 李刚刚, 罗文昌. 工件具有任意尺寸的混合分批平行机排序问题的近似算法[J]. 运筹学学报, 2022, 26(3): 133-142.
[6]	周萍, 季敏, 蒋义伟. 极大化提前完工总量平行机排序问题的LPT算法[J]. 运筹学学报, 2022, 26(3): 151-156.
[7]	李文杰, 李钰晶, 刘海玲. 工件的释放时间和加工时间具有一致性的单机在线排序问题研究[J]. 运筹学学报, 2022, 26(2): 55-63.
[8]	毕春燕, 万龙, 罗文昌. 工件有到达时间及可拒绝下的同类平行机排序问题的近似算法[J]. 运筹学学报, 2022, 26(2): 73-82.
[9]	李建平, 蔡力健, 李陈筠然, 潘鹏翔. 限制性多源点偏心距增广问题[J]. 运筹学学报, 2022, 26(1): 60-68.
[10]	陈婳, 张国川. 经典一维装箱问题近似算法的研究进展[J]. 运筹学学报, 2022, 26(1): 69-84.
[11]	刘文杰, 张冬梅, 张鹏, 邹娟. 带惩罚μ-相似Bregman散度k-均值问题的初始化算法[J]. 运筹学学报, 2022, 26(1): 99-112.
[12]	剧嘉琛, 刘茜, 张昭, 周洋. 带惩罚的相同容量k-均值问题的局部搜索算法[J]. 运筹学学报, 2022, 26(1): 113-124.
[13]	王利博, 李文华, 余丹. 单机上带有可变前瞻区间的分批在线排序问题[J]. 运筹学学报, 2022, 26(1): 134-140.
[14]	李小玮, 成夏炎, 李荣珩. 带有线性惩罚的鲁棒k-种产品设施选址问题的近似算法[J]. 运筹学学报, 2021, 25(4): 31-44.
[15]	余山杉, 金苗苗, 罗文昌. 工件延误和可拒绝下的单机重新排序问题的近似方案[J]. 运筹学学报, 2021, 25(2): 104-114.

带有退化维护活动和工件可拒绝的非同类机排序问题

Unrelated parallel-machine scheduling with deteriorating maintenance activities and job rejection

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 22

相关文章 15

编辑推荐

Metrics

本文评价