Pareto optimal algorithms for minimizing total (weighted) completion time and maximum cost on a single machine

Zhimeng Liu; Shuguang Li; Zhimeng Liu; Shuguang Li

doi:10.3934/mbe.2022346

Mathematical Biosciences and Engineering

2022, Volume 19, Issue 7: 7337-7348. doi: 10.3934/mbe.2022346

Previous Article Next Article

Research article

Pareto optimal algorithms for minimizing total (weighted) completion time and maximum cost on a single machine

Zhimeng Liu ,
Shuguang Li ^,

College of Computer Science and Technology, Shandong Technology and Business University, Yantai 264005, China

Academic Editor: Yang Kuang

Received: 21 March 2022 Revised: 10 May 2022 Accepted: 16 May 2022 Published: 18 May 2022

This paper studies the Pareto scheduling problem of minimizing total weighted completion time and maximum cost on a single machine. It is known that the problem is strongly NP-hard. Algorithms with running time $ O(n^3) $ are presented for the following cases: arbitrary processing times, equal release dates and equal weights; equal processing times, arbitrary release dates and equal weights; equal processing times, equal release dates and arbitrary weights.
- scheduling,
- Pareto optimization,
- single machine,
- total weighted completion time,
- maximum cost
Citation: Zhimeng Liu, Shuguang Li. Pareto optimal algorithms for minimizing total (weighted) completion time and maximum cost on a single machine[J]. Mathematical Biosciences and Engineering, 2022, 19(7): 7337-7348. doi: 10.3934/mbe.2022346

Related Papers:

Abstract

This paper studies the Pareto scheduling problem of minimizing total weighted completion time and maximum cost on a single machine. It is known that the problem is strongly NP-hard. Algorithms with running time $ O(n^3) $ are presented for the following cases: arbitrary processing times, equal release dates and equal weights; equal processing times, arbitrary release dates and equal weights; equal processing times, equal release dates and arbitrary weights.

References

[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]	D. Jones, S. Firouzy, A. Labib, A. V. Argyriou, Multiple criteria model for allocating new medical robotic devices to treatment centres, Eur. J. Oper. Res., 297 (2022), 652–664. https://doi.org/10.1016/j.ejor.2021.06.003 doi: 10.1016/j.ejor.2021.06.003
[3]	F. F. Ostermeier, On the trade-offs between scheduling objectives for unpaced mixed-model assembly lines, Int. J. Prod. Res., 60 (2022), 866–893. https://doi.org/10.1080/00207543.2020.1845914 doi: 10.1080/00207543.2020.1845914
[4]	P. M. Kumar, G. C. Babu, A. Selvaraj, M. Raza, A. K. Luhach, V. G. Daaz, Multi-criteria-based approach for job scheduling in industry 4.0 in smart cities using fuzzy logic, Soft Comput., 25 (2021), 12059–12074.
[5]	V. T'Kindt, J. C. Billaut, Multicriteria scheduling: theory, models and algorithms, second edition, Springer Verlag, Berlin, 2006.
[6]	P. Brucker, Scheduling algorithms, fifth edition, Springer, 2007.
[7]	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
[8]	J. K. Lenstra, A. R. Kan, P. Brucker, Complexity of machine scheduling problems, Ann. Discrete Math., 1 (1977), 343–362. https://doi.org/10.1016/S0167-5060(08)70743-X doi: 10.1016/S0167-5060(08)70743-X
[9]	L. N. V. Wassenhove, 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
[10]	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
[11]	J. A. Hoogeveen, S. L. V. D. 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
[12]	Y. Gao, J. J. Yuan, A note on Pareto minimizing total completion time and maximum cost, Oper. Res. Lett., 43 (2015), 80–82. https://doi.org/10.1080/01576895.2014.1000811 doi: 10.1080/01576895.2014.1000811
[13]	Y. Gao, J. J. Yuan, Pareto minimizing total completion time and maximum cost with positional due indices, J. Oper. Res. Soc. China, 3 (2015), 381–387. https://doi.org/10.1007/s40305-015-0083-1 doi: 10.1007/s40305-015-0083-1
[14]	C. He, H. Lin, X. M. 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.
[15]	A. A. Lazarev, D. I. Arkhipov, F. Werner, Scheduling jobs with equal processing times on a single machine: minimizing maximum lateness and makespan, Optim. Lett., 11 (2016), 165–177. https://doi.org/10.1007/s11590-016-1003-y doi: 10.1007/s11590-016-1003-y
[16]	J. A. Hoogeveen, Single-machine scheduling to minimize a function of two or three maximum cost criteria, J. Algorithms, 21 (1996), 415–433. https://doi.org/10.1006/jagm.1996.0051 doi: 10.1006/jagm.1996.0051
[17]	S. A. Kravchenko, F. Werner, Parallel machine problems with equal processing times: A survey, J. Scheduling, 14 (2011), 435–444. https://doi.org/10.1007/s10951-011-0231-3 doi: 10.1007/s10951-011-0231-3
[18]	H. Emmons, A note on a scheduling problem with dual criteria, Nav. Res. Log., 22 (1975), 615–616. https://doi.org/10.1002/nav.3800220317 doi: 10.1002/nav.3800220317
[19]	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
[20]	T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to algorithms, third edition, MIT press, 2009.
[21]	F. Koehler, S. Khuller, Optimal batch schedules for parallel machines, in Proceedings of the 13th International Conference on Algorithms and Data Structures, Springer-VerlagBerlin, Heidelberg, 2013.

Reader Comments

Your name:*

Email:*
© 2022 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)