This paper studies the problem of scheduling $ n $ jobs on a single machine to minimize total completion time and maximum cost, simultaneously. Each job is associated with a positional deadline that indicates the largest ordinal number of this job in any feasible schedule. The jobs have agreeable release and processing times, meaning that jobs with larger release times also have larger processing times. The agreeability assumption is reasonable since both the single-criterion problems (without positional deadline constraints) of minimizing total completion time and maximum lateness on a single machine with arbitrary release and processing times are strongly NP-hard. An $ O(n^3) $-time Pareto optimal algorithm is presented. The previously known algorithms only solve two special cases of the agreeability assumption: either the case of equal release times in $ O(n^4) $ time, or the case of equal processing times (without positional deadline constraints) in $ O(n^3) $ time.
Citation: Shuguang Li, Yong Sun, Muhammad Ijaz Khan. Single machine Pareto scheduling with positional deadlines and agreeable release and processing times[J]. Electronic Research Archive, 2023, 31(5): 3050-3063. doi: 10.3934/era.2023154
This paper studies the problem of scheduling $ n $ jobs on a single machine to minimize total completion time and maximum cost, simultaneously. Each job is associated with a positional deadline that indicates the largest ordinal number of this job in any feasible schedule. The jobs have agreeable release and processing times, meaning that jobs with larger release times also have larger processing times. The agreeability assumption is reasonable since both the single-criterion problems (without positional deadline constraints) of minimizing total completion time and maximum lateness on a single machine with arbitrary release and processing times are strongly NP-hard. An $ O(n^3) $-time Pareto optimal algorithm is presented. The previously known algorithms only solve two special cases of the agreeability assumption: either the case of equal release times in $ O(n^4) $ time, or the case of equal processing times (without positional deadline constraints) in $ O(n^3) $ time.
| [1] |
H. Hoogeveen, Multicriteria scheduling, Eur. J. Oper. Res., 167 (2005), 592–623. https://doi.org/10.1016/j.ejor.2004.07.011 doi: 10.1016/j.ejor.2004.07.011
|
| [2] | P. Brucker, Scheduling Algorithms, fifth Edition, Springer, 2007. https://doi.org/10.1007/978-3-540-69516-5 |
| [3] | V. T'kindt, J. C. Billaut, Multicriteria Scheduling: Theory, Models and Algorithms, Springer Verlag, Berlin, 2006. |
| [4] | J. K. Lenstra, A. R. Kan, P. Brucker, Complexity of machine scheduling problems, in Annals of Discrete Mathematics, Elsevier, (1977), 343–362. https://doi.org/10.1016/S0167-5060(08)70743-X |
| [5] |
J. K. Lenstra, A. R. Kan, Complexity of scheduling under precedence constraints, Oper. Res., 26 (1978), 22–35. https://doi.org/10.1287/opre.26.1.22 doi: 10.1287/opre.26.1.22
|
| [6] | Y. Gao, J. Yuan, Pareto minimizing total completion time and maximum cost with positional due indices, J. Oper. Res. Soc. China, 3 (2015), 381–387. |
| [7] |
Z. Liu, S. Li, Pareto optimal algorithms for minimizing total (weighted) completion time and maximum cost on a single machine, Math. Biosci. Eng., 19 (2022), 7337–7348. https://doi.org/10.3934/mbe.2022346 doi: 10.3934/mbe.2022346
|
| [8] |
P. Perez-Gonzalez, J. M. Framinan, A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs: Multi-agent scheduling problems, Eur. J. Oper. Res., 235 (2014), 1–16. https://doi.org/10.1016/j.ejor.2013.09.017 doi: 10.1016/j.ejor.2013.09.017
|
| [9] |
A. Herzel, S. Ruzika, C. Thielen, Approximation methods for multiobjective optimization problems: A survey, INFORMS J. Comput., 33 (2021), 1284–1299. https://doi.org/10.1287/ijoc.2020.1028 doi: 10.1287/ijoc.2020.1028
|
| [10] |
L. N. V. Wassenhove, L. F. Gelders, Solving a bicriterion scheduling problem, Eur. J. Oper. Res., 4 (1980), 42–48. https://doi.org/10.1016/0377-2217(80)90038-7 doi: 10.1016/0377-2217(80)90038-7
|
| [11] |
T. C. John, Tradeoff solutions in single machine production scheduling for minimizing flow time and maximum penalty, Comput. Oper. Res., 16 (1989), 471–479. https://doi.org/10.1016/0305-0548(89)90034-8 doi: 10.1016/0305-0548(89)90034-8
|
| [12] |
J. Hoogeveen, S. L. van de Velde, Minimizing total completion time and maximum cost simultaneously is solvable in polynomial time, Oper. Res. Lett., 17 (1995), 205–208. https://doi.org/10.1016/0167-6377(95)00023-D doi: 10.1016/0167-6377(95)00023-D
|
| [13] |
G. Steiner, P. Stephenson, Pareto optima for total weighted completion time and maximum lateness on a single machine, Discrete Appl. Math., 155 (2007), 2341–2354. https://doi.org/10.1016/j.dam.2007.06.012 doi: 10.1016/j.dam.2007.06.012
|
| [14] |
Y. Gao, J. Yuan, A note on pareto minimizing total completion time and maximum cost, Oper. Res. Lett., 43 (2015), 80–82. https://doi.org/10.1016/j.orl.2014.12.001 doi: 10.1016/j.orl.2014.12.001
|
| [15] |
C. He, H. Lin, X. Wang, Single machine bicriteria scheduling with equal-length jobs to minimize total weighted completion time and maximum cost, 4OR-Q. J. Oper. Res., 12 (2014), 87–93. https://doi.org/10.1007/s10288-013-0244-1 doi: 10.1007/s10288-013-0244-1
|
| [16] |
Q. Zhao, L. Lu, J. Yuan, Rescheduling with new orders and general maximum allowable time disruptions, 4OR-Q. J. Oper. Res., 14 (2016), 261–280. https://doi.org/10.1007/s10288-016-0308-0 doi: 10.1007/s10288-016-0308-0
|
| [17] |
Q. Zhao, J. Yuan, Rescheduling to minimize the maximum lateness under the sequence disruptions of original jobs, Asia Pac. J. Oper. Res., 34 (2017), 1750024. https://doi.org/10.1142/S0217595917500245 doi: 10.1142/S0217595917500245
|
| [18] |
Y. Gao, J. Yuan, Bi-criteria pareto-scheduling on a single machine with due indices and precedence constraints, Discrete Optim., 25 (2017), 105–119. https://doi.org/10.1016/j.disopt.2017.02.004 doi: 10.1016/j.disopt.2017.02.004
|
| [19] |
R. Chen, J. Yuan, Single-machine scheduling of proportional-linearly deteriorating jobs with positional due indices, 4OR-Q. J. Oper. Res., 18 (2020), 177–196. https://doi.org/10.1007/s10288-019-00410-4 doi: 10.1007/s10288-019-00410-4
|
| [20] |
R. Chen, J. Yuan, L. Lu, Single-machine scheduling with positional due indices and positional deadlines, Discrete Optim., 34 (2019), 100549. https://doi.org/10.1016/j.disopt.2019.06.002 doi: 10.1016/j.disopt.2019.06.002
|
| [21] |
R. Chen, J. Yuan, Z. Geng, Nd-agent scheduling of linear-deteriorating tasks with positional due indices to minimize total completion time and maximum cost, Appl. Math. Comput., 365 (2020), 124697. https://doi.org/10.1016/j.amc.2019.124697 doi: 10.1016/j.amc.2019.124697
|
| [22] |
Y. Gao, J. Yuan, C. Ng, T. Cheng, A note on competing-agent pareto-scheduling, Optim. Lett., 15 (2021), 249–262. https://doi.org/10.1007/s11590-020-01576-1 doi: 10.1007/s11590-020-01576-1
|
| [23] |
C. He, C. Xu, H. Lin, Serial-batching scheduling with two agents to minimize makespan and maximum cost, J. Sched., 23 (2020), 609–617. https://doi.org/10.1007/s10951-020-00656-5 doi: 10.1007/s10951-020-00656-5
|
| [24] |
Z. Geng, J. Liu, Single machine batch scheduling with two non-disjoint agents and splitable jobs, J. Comb. Optim., 40 (2020), 774–795. https://doi.org/10.1007/s10878-020-00626-9 doi: 10.1007/s10878-020-00626-9
|
| [25] |
Y. Gao, J. Yuan, C. Ng, T. Cheng, Pareto-scheduling with family jobs or nd-agent on a parallel-batch machine to minimize the makespan and maximum cost, 4OR-Q. J. Oper. Res., 20 (2022), 273–287. https://doi.org/10.1007/s10288-021-00480-3 doi: 10.1007/s10288-021-00480-3
|
| [26] |
S. Li, Z. Geng, Bicriteria scheduling on an unbounded parallel-batch machine for minimizing makespan and maximum cost, Inf. Process. Lett., 180 (2023), 106343. https://doi.org/10.1016/j.ipl.2022.106343 doi: 10.1016/j.ipl.2022.106343
|
| [27] |
W. E. Smith, Various optimizers for single-stage production, Nav. Res. Log., 3 (1956), 59–66. https://doi.org/10.1002/nav.3800030106 doi: 10.1002/nav.3800030106
|
Shuguang Li, Yong Sun, Muhammad Ijaz Khan. Single machine Pareto scheduling with positional deadlines and agreeable release and processing times[J]. Electronic Research Archive, 2023, 31(5): 3050-3063. doi: 10.3934/era.2023154
DownLoad: