Bicriteria multi-machine scheduling with equal processing times subject to release dates

Zhimeng Liu; Shuguang Li; Muhammad Ijaz Khan; Shaimaa A. M. Abdelmohsen; Sayed M. Eldin; Zhimeng Liu; Shuguang Li; Muhammad Ijaz Khan; Shaimaa A. M. Abdelmohsen; Sayed M. Eldin

doi:10.3934/nhm.2023060

Networks and Heterogeneous Media

2023, Volume 18, Issue 3: 1378-1392. doi: 10.3934/nhm.2023060

Previous Article Next Article

Research article

Bicriteria multi-machine scheduling with equal processing times subject to release dates

1.
School of Computer Science and Technology, Shandong Technology and Business University, Yantai 264005, China
2.
Department of Mechanical Engineering, Lebanese American University, Beirut 362060, Lebanon
3.
Department of Mechanics and Engineering Science, Peking University, Beijing 100871, China
4.
Department of Physics, College of Science, Princess Nourah bint Abdulrahman University, Riyadh 11671, Saudi Arabia
5.
Center of Research, Faculty of Engineering, Future University in Egypt, New Cairo 11835, Egypt

Received: 05 January 2023 Revised: 07 May 2023 Accepted: 10 May 2023 Published: 23 May 2023

This paper addresses the problem of scheduling $ n $ equal-processing-time jobs with release dates non-preemptively on identical machines to optimize two criteria simultaneously or hierarchically. For simultaneous optimization of total completion time (and makespan) and maximum cost, an algorithm is presented which can produce all Pareto-optimal points together with the corresponding schedules. The algorithm is then adapted to solve the hierarchical optimization of two min-max criteria, and the final schedule has a minimum total completion time and minimum makespan among the hierarchical optimal schedules. The two algorithms provided in this paper run in $ O(n^3) $ time.
- scheduling,
- Pareto optimization,
- lexicographical optimization,
- identical machines,
- release dates
Citation: Zhimeng Liu, Shuguang Li, Muhammad Ijaz Khan, Shaimaa A. M. Abdelmohsen, Sayed M. Eldin. Bicriteria multi-machine scheduling with equal processing times subject to release dates[J]. Networks and Heterogeneous Media, 2023, 18(3): 1378-1392. doi: 10.3934/nhm.2023060

Related Papers:

Abstract

This paper addresses the problem of scheduling $ n $ equal-processing-time jobs with release dates non-preemptively on identical machines to optimize two criteria simultaneously or hierarchically. For simultaneous optimization of total completion time (and makespan) and maximum cost, an algorithm is presented which can produce all Pareto-optimal points together with the corresponding schedules. The algorithm is then adapted to solve the hierarchical optimization of two min-max criteria, and the final schedule has a minimum total completion time and minimum makespan among the hierarchical optimal schedules. The two algorithms provided in this paper run in $ O(n^3) $ time.

References

[1]	H. Hoogeveen, Multicriteria scheduling, Eur. J. Oper., 167 (2005), 592–623. https://doi.org/10.1016/j.ejor.2004.07.011
[2]	V. T'kindt, J. C. Billaut, Multicriteria Scheduling: Theory, Models and Algorithms, Berlin: Springer Verlag, 2006.
[3]	P Brucker, Scheduling Algorithms, J Oper Res Soc, 50 (1999), 774–774. https://doi.org/10.2307/3010332
[4]	A. Nagar, J. Haddock, S. Heragu, Multiple and bicriteria scheduling: A literature survey, Eur. J. Oper., 81 (1995), 88–104. https://doi.org/10.1016/0022-4049(94)00117-2 doi: 10.1016/0022-4049(94)00117-2
[5]	M. Pfund, J. W. Fowler, J. N. D Gupta, A survey of algorithms for single and multi-objective unrelated parallel-machine deterministic scheduling problems, Journal of the Chinese Institute of Industrial Engineers, 21 (2004), 230–241. https://doi.org/10.1080/10170660409509404 doi: 10.1080/10170660409509404
[6]	D. M. Lei, Multi-objective production scheduling: a survey, Int. J. Adv. Manuf., 43 (2009), 926–938. https://doi.org/10.1007/s00170-008-1770-4 doi: 10.1007/s00170-008-1770-4
[7]	F. S. Erenay, I. Sabuncuoglu, A. Toptal, M. K. Tiwari, New solution methods for single machine bicriteria scheduling problem: Minimization of average flowtime and number of tardy jobs, Eur. J. Oper., 201 (2010), 89–98. https://doi.org/10.1057/fsp.2010.5 doi: 10.1057/fsp.2010.5
[8]	Y. K. Lin, J. W. Fowler, M. E. Pfund, Multiple-objective heuristics for scheduling unrelated parallel machines, Eur. J. Oper., 227 (2013), 239–253. https://doi.org/10.1016/j.ejor.2012.10.008 doi: 10.1016/j.ejor.2012.10.008
[9]	A. J. Ruiz-Torres, J. H. Ablanedo-Rosas, S. Mukhopadhyay, G. Paletta, Scheduling workers: A multi-criteria model considering their satisfaction, Comput Ind Eng, 128 (2019), 747–754. https://doi.org/10.1016/j.cie.2018.12.070 doi: 10.1016/j.cie.2018.12.070
[10]	J. C. Yepes-Borrero, F. Perea, R. Ruiz, F. Villa, Bi-objective parallel machine scheduling with additional resources during setups, Eur. J. Oper., 292 (2021), 443–455. https://doi.org/10.1016/j.ejor.2020.10.052 doi: 10.1016/j.ejor.2020.10.052
[11]	J. Mar-Ortiz, A. J. Ruiz Torres, B. Adenso-Díaz, Scheduling in parallel machines with two objectives: analysis of factors that influence the pareto frontier, Oper. Res., 22 (2022), 4585–4605. https://doi.org/10.1007/s12351-021-00684-9 doi: 10.1007/s12351-021-00684-9
[12]	J. ND Gupta, A. J. Ruiz-Torres, Minimizing makespan subject to minimum total flow-time on identical parallel machines, Eur. J. Oper., 125 (2000), 370–380. https://doi.org/10.1016/S0377-2217(99)00386-0 doi: 10.1016/S0377-2217(99)00386-0
[13]	C. H. Lin, C. J. Liao, Makespan minimization subject to flowtime optimality on identical parallel machines, Comput. Oper. Res., 31 (2004), 1655–1666. https://doi.org/10.1016/S0305-0548(03)00113-8 doi: 10.1016/S0305-0548(03)00113-8
[14]	L. H. Su, Minimizing earliness and tardiness subject to total completion time in an identical parallel machine system, Comput. Oper. Res., 36 (2009), 461–471. https://doi.org/10.1016/j.cor.2007.09.013 doi: 10.1016/j.cor.2007.09.013
[15]	J. L. Bruno, E. G. Coffman Jr, R. Sethi, Algorithms for minimizing mean flow time, Proceedings of the IFIP Congress, 74 (1974), 504–510.
[16]	J. ND Gupta, A. J. Ruiz-Torres, S. Webster, Minimizing maximum tardiness and number of tardy jobs on parallel machines subject to minimum flow-time, J. Oper. Res. Soc., 54 (2003), 1263–1274. https://doi.org/10.1057/palgrave.jors.2601638 doi: 10.1057/palgrave.jors.2601638
[17]	E. L. Lawler, J. K. Lenstra, A. H. G. R. Kan, D. B. Shmoys, Sequencing and scheduling: Algorithms and complexity, Handbooks in operations research and management science, 4 (1993), 445–522.
[18]	J. K. Lenstra, A. H. G. R. Kan, P. Brucker, Complexity of machine scheduling problems, Annals of discrete mathematics, 1 (1977), 343–362.
[19]	S. A. Kravchenko, F. Werner, Scheduling jobs with equal processing times, Proceedings of the 13th IFAC Symposium on Information Control Problems in Manufacturing, 42 (2009), 1262–1267. https://doi.org/10.3182/20090603-3-RU-2001.0042 doi: 10.3182/20090603-3-RU-2001.0042
[20]	S. A. Kravchenko, F. Werner, Parallel machine problems with equal processing times: a survey, J. Sched., 14 (2011), 435–444. https://doi.org/10.1007/s10951-011-0231-3 doi: 10.1007/s10951-011-0231-3
[21]	P. Brucker, N. V. Shakhlevich, Necessary and sufficient optimality conditions for scheduling unit time jobs on identical parallel machines, J. Sched., 19 (2016), 659–685. https://doi.org/10.1007/s10951-016-0471-3 doi: 10.1007/s10951-016-0471-3
[22]	J. Hong, K. Lee, M. L. Pinedo, Scheduling equal length jobs with eligibility restrictions, Ann. Oper. Res., 285 (2020), 295–314. https://doi.org/10.1007/s10479-019-03172-8 doi: 10.1007/s10479-019-03172-8
[23]	N. Vakhania, A better algorithm for sequencing with release and delivery times on identical machines, J. Algorithm, 48 (2003), 273–293. https://doi.org/10.1016/S0196-6774(03)00072-5 doi: 10.1016/S0196-6774(03)00072-5
[24]	N. Vakhania, F. Werner, A polynomial algorithm for sequencing jobs with release and delivery times on uniform machines, 2021010142, [Preprint], (2021) [cited 2023 May 23 ]. Available from: https://www.preprints.org/manuscript/202101.0142/v2
[25]	A. Tuzikov, M. Makhaniok, R. Männer, Bicriterion scheduling of identical processing time jobs by uniform processors, Comput. Oper. Res., 25 (1998), 31–35. https://doi.org/10.1016/S0305-0548(98)80005-1 doi: 10.1016/S0305-0548(98)80005-1
[26]	S. C. Sarin, D. Prakash, Equal processing time bicriteria scheduling on parallel machines, J Comb Optim, 8 (2004), 227–240.
[27]	Q. L. Zhao, J. J. Yuan, Bicriteria scheduling of equal length jobs on uniform parallel machines, J Comb Optim, 39 (2020), 637–661. https://doi.org/10.1007/s10878-019-00507-w doi: 10.1007/s10878-019-00507-w
[28]	B. Simons, Multiprocessor scheduling of unit-time jobs with arbitrary release times and deadlines, SIAM J. Comput., 12 (1983), 294–299. https://doi.org/10.1137/0212018 doi: 10.1137/0212018
[29]	B. B. Simons, M. K. Warmuth, A fast algorithm for multiprocessor scheduling of unit-length jobs, SIAM J. Comput., 18 (1989), 690–710. https://doi.org/10.1137/0218048 doi: 10.1137/0218048
[30]	C. Dürr, M. Hurand, Finding total unimodularity in optimization problems solved by linear programs, Algorithmica, 59 (2011), 256–268. https://doi.org/10.1007/s00453-009-9310-7 doi: 10.1007/s00453-009-9310-7
[31]	A. López-Ortiz, C. G. Quimper, A fast algorithm for multi-machine scheduling problems with jobs of equal processing times, Symposium on Theoretical Aspects of Computer Science, 9 (2011), 380–391.
[32]	H. Fahimi, C. G. Quimper, Variants of multi-resource scheduling problems with equal processing times, In Combinatorial Optimization and Applications: 9th International Conference, Houston: Springer International Publishing, 2015.
[33]	D. Elvikis, V.Tkindt, Two-agent scheduling on uniform parallel machines with min-max criteria, Ann. Oper. Res., 213 (2014), 79–94.

Reader Comments

Your name:*

Email:*
© 2023 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)