We consider the single-machine scheduling with coupled task and rejection, in which each coupled task is either accepted and processed on a single machine or rejected with a certain rejection penalty. Each accepted coupled task $ J_{j} $ is made of two tasks with processing times $ a_j $ and $ b_j $, respectively, and a fixed exactly time interval $ L_j $ between the two tasks is required. The objective is to minimize the makespan of the accepted coupled task and the total penalty of the rejected coupled task. We present $ 3 $-approximation algorithm for the cases of $ a_{j} = L_{j} = p $ and $ b_j = L_j = p $, respectively, and prove that the problems with common $ b_j $ or common $ a_j $ is polynomially solvable. Furthermore, when $ a_{j} = b_{j} = p $, we provide a $ 2 $-approximation algorithm for $ L_{j}>p $ and show that the problem with for $ L_{j}\leq p $ can be solved in polynomial time.
|
Citation:
|
| [1] |
A. Azadeh, M. H. Farahani, S. Torabzadeh and M. Baghersad, Scheduling prioritized patients in emergency department laboratories, Computer Methods and Programs in Biomedicine, 117 (2014), 61-70.
doi: 10.1016/j.cmpb.2014.08.006. |
| [2] |
Y. Bartal, S. Leonardi, A. Marchetti-Spaccamela, J. Sgall and L. Stougie, Multiprocessor scheduling with rejection, SIAM Journal on Discrete Mathematics, 13 (2000), 64-78.
doi: 10.1137/S0895480196300522. |
| [3] |
B. Chen and X. Zhang, Scheduling coupled tasks with exact delays for minimum total job completion time, Journal of Scheduling, 24 (2021), 209-221.
doi: 10.1007/s10951-020-00668-1. |
| [4] |
A. Condotta and N. V. Shakhlevich, Scheduling coupled-operation jobs with exact time-lags, Discrete Applied Mathematics, 160 (2012), 2370-2388.
doi: 10.1016/j.dam.2012.05.026. |
| [5] |
M. Elshafei, H. D. Sherali and J. C. Smith, Radar pulse interleaving for multitarget tracking, Naval Research Logistics, 51 (2004), 72-94.
doi: 10.1002/nav.10103. |
| [6] |
J. Gao, J. Zou and X. X. Cheng, Machine scheduling with job rejection and DeJong's learning effect, Mathematical Foundations of Computing, 6 (2023), 253-267.
doi: 10.3934/mfc.2022024. |
| [7] |
R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Operations Research, 5 (1979), 287-326.
doi: 10.1016/S0167-5060(08)70356-X. |
| [8] |
F. J. Hwang and B. M. T. Lin, Coupled-task scheduling on a single machine subject to a fixed-job-sequence, Computers and Industrial Engineering, 60 (2011), 690-698.
doi: 10.1016/j.cie.2011.01.002. |
| [9] |
D. W. Li and X. W. Lu, Two-agent parallel-machine scheduling with rejection, Theoretical Computer Science, 703 (2017), 66-75.
doi: 10.1016/j.tcs.2017.09.004. |
| [10] |
L. F. Lu, L. Q. Zhang and J. J. Yuan, The unbounded parallel batch machine scheduling with release dates and rejection to minimize makespan, Theoretical Computer Science, 396 (2008), 283-289.
doi: 10.1016/j.tcs.2008.02.015. |
| [11] |
J. C. Moskop and K. V. Iserson, Triage in medicine, Part Ⅱ: Underlying values and principles, Annals of Emergency Medicine, 49 (2007), 51-60.
doi: 10.1016/j.annemergmed.2006.07.012. |
| [12] |
A. J. Orman and C. N. Potts, On the complexity of coupled-task scheduling, Discrete Applied Mathematics, 72 (1997), 141-154.
doi: 10.1016/S0166-218X(96)00041-8. |
| [13] |
D. Shabtay, N. Gaspar and M. Kaspi, A survey on offline scheduling with rejection, Journal of Scheduling, 16 (2013), 3-28.
doi: 10.1007/s10951-012-0303-z. |
| [14] |
R. D. Shapiro, Scheduling coupled tasks, Naval Research Logistics Quarterly, 28 (1980), 489-498.
doi: 10.1002/nav.3800270312. |
| [15] |
M. I. Skolnik, Introduction to Radar Systems, New York, 1980.
|
| [16] |
Z. H. Yang, Y. M. Ying and Q. L. Min, Online optimization for residential PV-ESS energy system scheduling, Mathematical Foundations of Computing, 2 (2019), 55-71.
doi: 10.3934/mfc.2019005. |
| [17] |
W. Yu, H. Hoogeveen and J. K. Lenstra, Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard, Journal of Scheduling, 7 (2004), 333-348.
doi: 10.1023/B:JOSH.0000036858.59787.c2. |
| [18] |
L. Q. Zhang, L. F. Lu and J. J. Yuan, Single machine scheduling with release dates and rejection, European Journal of Operational Research, 198 (2009), 975-978.
doi: 10.1016/j.ejor.2008.10.006. |