SCIENCE@home

An improved algorithm on unbounded parallel-batching scheduling to minimize maximum cost and makespan

Cheng He,Jing Wu,Jinglei Xu,Junling Wang

Published 2023 in RAIRO Oper. Res.

ABSTRACT

This paper studies the bicriteria problem of scheduling $n$ jobs on a parallel-batching machine to minimize maximum cost and makespan simultaneously. A parallel-batching machine is a machine that can handle up to $b$ jobs in a batch. The jobs in a batch start and complete respectively at the same time and the processing time of a batch is equal to the largest processing time of jobs in the batch. We consider the unbounded case. For the above bicriteria scheduling problem, we present an $O(n^{3})$-time algorithm, which improved the best known $O(n^{4})$-time algorithm, and the time complexity is the same as the special case in which maximum cost is maximum lateness. Meanwhile, our algorithm can also solve the single-criterion unbounded parallel-batching scheduling problem  to minimize maximum cost  in $O(n^{3})$ time, which improved  the best known $O(n^{4})$-time algorithm.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-21 of 21 references · Page 1 of 1

CITED BY