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.
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
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.
| [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. |
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
DownLoad: