Approximation Scheme for Single Machine Rescheduling Problem with an Unavailable Interval and Job Rejection
JIN Miao-miao1, WU Meng-jie2, LUO Wen-chang2
1. School of Mathematics and Information Engineering, Wenzhou University of Technology, Wenzhou 325006, China; 2. School of Mathematics and Statistics, Ningbo University, Ningbo 315211, China
JIN Miao-miao, WU Meng-jie, LUO Wen-chang. Approximation Scheme for Single Machine Rescheduling Problem with an Unavailable Interval and Job Rejection[J]. Operations Research and Management Science, 2021, 30(8): 87-92.
[1] Graham R L, Lawler E L, Lenstra J K, Rinnooy Kan A H G. Optimization and approximation in deterministic sequencing and scheduling: a survey[J]. Annals of Discrete Mathematics, 1979, 5(1): 287-326. [2] Lee C Y. Machine scheduling with an availability constraint[J]. Journal of Global Optimization, 1996, 9(3-4): 395-416. [3] Kacem I, Chu C, Souissi A. Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times[J]. Computers & Operations Research, 2008, 35(3): 827-844. [4] Kellerer H, Kubzin M A, Strusevich V A. Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval[J]. European Journal of Operational Research, 2009, 199(1): 111-116. [5] Kellerer H, Strusevich V A. Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications[J]. Algorithmica, 2010, 57(4): 769-795. [6] Huo Y, Reznichenko B, Zhao H. Minimizing total weighted completion time with an unexpected machine unavailable interval[J]. Journal of Scheduling, 2014, 17(2): 161-172. [7] Liu P, Wang C, Lu X. A note on minimizing total weighted completion time with an unexpected machine unavailable interval[J]. Journal of Scheduling, 2019, 22: 255-262. [8] Liu Z, Ro Y K. Rescheduling for machine disruption to minimize makespan and maximum lateness[J]. Journal of Scheduling, 2014, 17: 339-352. [9] Liu Z, Lu L, Qi X. Cost allocation in rescheduling with machine unavailable period[J]. European Journal of Operational Research, 2018, 266(1): 16-28.