Algorithms for two-agent unbounded serial-batch scheduling with makespan and maximum lateness objectives

Shuguang Li; Mingsong Li; Muhammad Ijaz Khan; Shuguang Li; Mingsong Li; Muhammad Ijaz Khan

doi:10.3934/nhm.2023073

Networks and Heterogeneous Media

2023, Volume 18, Issue 4: 1678-1691. doi: 10.3934/nhm.2023073

Previous Article Next Article

Research article

Algorithms for two-agent unbounded serial-batch scheduling with makespan and maximum lateness objectives

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

Received: 30 December 2022 Revised: 04 June 2023 Accepted: 21 September 2023 Published: 27 September 2023

We study the problem of non-preemptively scheduling jobs from two agents on an unbounded serial-batch machine. Agents $A$ and $B$ have $n_A$ and $n_B$ jobs. The machine can process any number of jobs sequentially as a batch, and the processing time of the batch is equal to the total processing time of the jobs in it. Each batch requires a setup time before it is processed. Compatibility means that the jobs from different agents can be processed in a common batch; Otherwise, the jobs from different agents are incompatible. Both the compatible and incompatible models are considered, under both the batch availability and item availability assumptions. Batch availability means that any job in a batch is not available until all the jobs in this batch are completed. Item availability means that a job in a batch becomes available immediately after it is completed processing. The completion time of a job is defined to be the moment when it is available. The goal is to minimize the makespan of agent $A$ and the maximum lateness of agent $B$ simultaneously. For the compatible model with batch availability, an $O(n_A+n_B^2\log n_B)$ -time algorithm is presented which improves the existing $O(n_A+n_B^4\log n_B)$ -time algorithm. A slight modification of the algorithm solves the incompatible model with batch availability in $O(n_A+n_B^2\log n_B)$ time, which has the same time complexity as the existing algorithm. For the compatible model with item availability, the analysis shows that it is easy and admits an $O(n_A+n_B\log n_B)$ -time algorithm. For the incompatible model with item availability, an $O(n_A+n_B\log n_B)$ -time algorithm is also obtained which improves the existing $O(n_A+n_B^2)$ -time algorithm. The algorithms can generate all Pareto optimal points and find a corresponding Pareto optimal schedule for each Pareto optimal point.

Keywords:

Citation: Shuguang Li, Mingsong Li, Muhammad Ijaz Khan. Algorithms for two-agent unbounded serial-batch scheduling with makespan and maximum lateness objectives[J]. Networks and Heterogeneous Media, 2023, 18(4): 1678-1691. doi: 10.3934/nhm.2023073

Related Papers:

[1]	Joseph Muiruri, Raphael Wahome, Kiemo Karatu . Assessment of methods practiced in the disposal of solid waste in Eastleigh Nairobi County, Kenya. AIMS Environmental Science, 2020, 7(5): 434-448. doi: 10.3934/environsci.2020028
[2]	Clare Maristela V. Galon, James G. Esguerra . Impact of COVID-19 on the environment sector: a case study of Central Visayas, Philippines. AIMS Environmental Science, 2022, 9(2): 106-121. doi: 10.3934/environsci.2022008
[3]	Siti Rachmawati, Syafrudin, Budiyono, Ellyna Chairani, Iwan Suryadi . Life cycle analysis and environmental cost-benefit assessment of utilizing hospital medical waste into heavy metal safe paving blocks. AIMS Environmental Science, 2024, 11(5): 665-681. doi: 10.3934/environsci.2024033
[4]	Jana Sallwey, Hiroshan Hettiarachchi, Stephan Hülsmann . Challenges and opportunities in municipal solid waste management in Mozambique: a review in the light of nexus thinking. AIMS Environmental Science, 2017, 4(5): 621-639. doi: 10.3934/environsci.2017.5.621
[5]	Tahseen Sayara, Ruba Hanoun, Yamen Hamdan . Survey on the factors and social perspectives to participate in home composting schemes in Palestine: Anabta case study. AIMS Environmental Science, 2022, 9(3): 232-243. doi: 10.3934/environsci.2022016
[6]	Yifeng Wang, Carlos F. Jove-Colon, Robert J. Finch . On the Durability of Nuclear Waste Forms from the Perspective of Long-Term Geologic Repository Performance. AIMS Environmental Science, 2014, 1(1): 26-35. doi: 10.3934/environsci.2013.1.26
[7]	Patrycja Przewoźna, Piotr Jankowski, Alfred Stach . Solid waste management in urban space: the volume-weight relationship. AIMS Environmental Science, 2020, 7(6): 575-588. doi: 10.3934/environsci.2020036
[8]	Obidike Emeka Esae, Jatau Sarah, Ayu Mofe . A critical analysis of the role of energy generation from municipal solid waste (MSW). AIMS Environmental Science, 2020, 7(5): 387-405. doi: 10.3934/environsci.2020026
[9]	Hamid Rastegari Kopaei, Mehdi Nooripoor, Ayatollah Karami, Myriam Ertz . Modeling consumer home composting intentions for sustainable municipal organic waste management in Iran. AIMS Environmental Science, 2021, 8(1): 1-17. doi: 10.3934/environsci.2021001
[10]	María Sancho, José Miguel Arnal, Gumersindo Verdú-Martín, Cristina Trull-Hernandis, Beatriz García-Fayos . Management of hospital radioactive liquid waste: treatment proposal for radioimmunoassay wastes. AIMS Environmental Science, 2021, 8(5): 449-464. doi: 10.3934/environsci.2021029

Abstract

References

[1]	A. Agnetis, J. C. Billaut, S. Gawiejnowicz, D. Pacciarelli, A. Soukhal, Multiagent scheduling: models and algorithms, Berlin Heidelberg: Springer, 2014.
[2]	C. N. Potts, M. Y. Kovalyov, Scheduling with batching: a review, Eur. J. Oper. Res., 120 (2000), 228–249. https://doi.org/10.1016/S0377-2217(99)00153-8 doi: 10.1016/S0377-2217(99)00153-8
[3]	J. W. Fowler, L. Monch, A survey of scheduling with parallel batch (p-batch) processing, Eur. J. Oper. Res., 298 (2022), 1–24.
[4]	R.L. Graham, E. L. Lawler, J. K. Lenstra, A. R. Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math., 5 (1979), 287–326. https://doi.org/10.1016/S0167-5060(08)70356-X doi: 10.1016/S0167-5060(08)70356-X
[5]	V. T'Kindt, J. C. Billaut, Multicriteria scheduling: theory, models and algorithms, second edition, Berlin: Springer Verlag, 2006.
[6]	H. Hoogeveen, Multicriteria scheduling, Eur. J. Oper. Res., 167 (2005), 592–623. https://doi.org/10.1016/j.ejor.2004.07.011
[7]	A. Allahverdi, The third comprehensive survey on scheduling problems with setup times/costs, Eur. J. Oper. Res., 246 (2015), 345–378. https://doi.org/10.1016/j.ejor.2015.04.004 doi: 10.1016/j.ejor.2015.04.004
[8]	K. R. Baker, J. Cole Smith, A multiple-criterion model for machine scheduling, J. Scheduling, 6 (2003), 7–16.
[9]	A. Agnetis, P. B. Mirchandani, D. Pacciarelli, A. Pacifici, Scheduling problems with two competing agents, Oper. Res., 52 (2004), 229–242. https://doi.org/10.1016/j.ejor.2015.04.004 doi: 10.1016/j.ejor.2015.04.004
[10]	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.
[11]	S. Webster, K. R. Baker, Scheduling groups of jobs on a single machine, Oper. Res., 43 (1995), 692–703. https://doi.org/10.1287/opre.43.4.692 doi: 10.1287/opre.43.4.692
[12]	A. P. M. Wagelmans, A. E. Gerodimos, Improved dynamic programs for some batching problems involving the maximum lateness criterion, Oper. Res. Lett., 27 (2000), 109–118. https://doi.org/10.1016/S0167-6377(00)00040-7 doi: 10.1016/S0167-6377(00)00040-7
[13]	C. He, Y. Lin, J. Yuan, Bicriteria scheduling of minimizing maximum lateness and makespan on a serial-batching machine, Found. Comput. Decis. S., 33 (2008), 369–376.
[14]	C. He, H. Lin, Y. Lin, J. Tian, Bicriteria scheduling on a series-batching machine to minimize maximum cost and makespan, Cent. Eur. J. Oper. Res., 21 (2013), 177–186. https://doi.org/10.1007/s10100-011-0220-9 doi: 10.1007/s10100-011-0220-9
[15]	C. He, H. Lin, Y. Lin, Bounded serial-batching scheduling for minimizing maximum lateness and makespan, Discrete Optim., 16 (2015), 70–75. https://doi.org/10.1016/j.disopt.2015.02.001 doi: 10.1016/j.disopt.2015.02.001
[16]	Z. Geng, J. Yuan, J. Yuan, Scheduling with or without precedence relations on a serial-batch machine to minimize makespan and maximum cost, Appl. Math. Comput., 332 (2018), 1–18. https://doi.org/10.1016/j.cam.2017.10.002 doi: 10.1016/j.cam.2017.10.002
[17]	M. Y. Kovalyov, A. Oulamara, A. Soukhal, Two-agent scheduling with agent specific batches on an unbounded serial batching machine, J. Scheduling, 18 (2015), 423–434. https://doi.org/10.1007/s10951-014-0410-0 doi: 10.1007/s10951-014-0410-0
[18]	Q. Feng, Z. Yu, W. Shang, Pareto optimization of serial-batching scheduling problems on two agents, Proceedings of the 2011 International Conference on Advanced Mechatronic Systems, (2011), 165–168.
[19]	C. He, C. Xu, H. Lin, Serial-batching scheduling with two agents to minimize makespan and maximum cost, J. Scheduling, 23 (2020), 609–617. https://doi.org/10.1007/s10951-020-00656-5 doi: 10.1007/s10951-020-00656-5
[20]	C. He, H. Lin, Improved algorithms for two-agent scheduling on an unbounded serial-batching machine, Discrete Optim., 41 (2021), 100655. https://doi.org/10.1016/j.disopt.2021.100655 doi: 10.1016/j.disopt.2021.100655
[21]	C. He, H. Lin, X. Han, Two-agent scheduling on a bounded series-batch machine to minimize makespan and maximum cost, Discrete Appl. Math., 322 (2022), 94–101. https://doi.org/10.1016/j.dam.2022.08.001 doi: 10.1016/j.dam.2022.08.001
[22]	C. He, S. S. Li, J. Wu, Simultaneous optimization scheduling with two agents on an unbounded serial-batching machine, RAIRO-Oper. Res., 55 (2021), 3701–3714. https://doi.org/10.1051/ro/2021175 doi: 10.1051/ro/2021175
[23]	S. Li, T. Cheng, C. Ng, J. Yuan, Two-agent scheduling on a single sequential and compatible batching machine, Nav. Res. Log., 64 (2017), 628–641. https://doi.org/10.1002/nav.21779 doi: 10.1002/nav.21779
[24]	T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, Cambridge: MIT press, 2022.

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)