@article{Li2023, 
author = {Shuguang Li and Mingsong Li and Muhammad Ijaz Khan},
title = {Algorithms for two-agent unbounded serial-batch scheduling with makespan and maximum lateness objectives},
year = {2023},
journal = {Networks and Heterogeneous Media},
volume = {18},
number = {4},
pages = {1678-1691},
keywords = {two-agent scheduling, unbounded serial-batch, compatibility/incompatibility, batch/item availability, maximum lateness},
url = {https://www.sciopen.com/article/10.3934/nhm.2023073},
doi = {10.3934/nhm.2023073},
abstract = {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.}
}