Operations Research Transactions >
2023 , Vol. 27 >Issue 3: 137 - 149
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2023.03.011
Unrelated parallel-machine scheduling with deteriorating maintenance activities and job rejection
Received date: 2022-01-18
Online published: 2023-09-14
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.
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 . DOI: 10.15960/j.cnki.issn.1007-6093.2023.03.011
| 1 | Lee C Y , Leon V J . Machine scheduling with a rate modifying activity[J]. European Journal of Operational Research, 2001, 128, 119- 128. |
| 2 | Kubzin M A , Strusevich V A . Planning machine maintenance in two-machine shop scheduling[J]. Operations Research, 2006, 54, 789- 800. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 11 | Bartal Y , Leonardi S , Spaccamela A M , et al. Multiprocessor scheduling with rejection[J]. SIAM Journal on Discrete Mathematics, 2000, 13, 64- 78. |
| 12 | Shabtay D , Gasper N , Kaspi M . A survey on offline scheduling with rejection[J]. Journal of Scheduling, 2013, 16, 3- 28. |
| 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. |
| 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. |
| 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. |
| 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. |
| 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. |
| 19 | Lenstra J K , Shmoys D B , Tardos S E . Approximation algorithms for scheduling unrelated parallel machines[J]. Mathematical Programming, 1990, 46, 259- 271. |
| 20 | Karmarkar N . A new polynomial-time algorithm for linear programming[J]. Combinatorica, 1984, 4 (4): 373- 395. |
| 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. |
/
| 〈 |
|
〉 |
