Bicriteria scheduling on a batching machine to minimize maximum lateness and makespan (Q995579)

This paper studies the bicriteria problem of scheduling \(n\) jobs on a batching machine to minimize maximum lateness and makespan simultaneously. The authors consider the parallel-batching model in which the jobs that are processed together form a batch with the same starting time and completion time, and the processing time of a batch is equal to the largest processing time of jobs in it. A parallel-batching machine can handle up to \(b\) jobs in a batch. The authors analyse the unbounded model in which the number of jobs in each batch is unlimited, denoted by \(``b\geq n"\) in short. Based on the result by [\textit{P. Brucker, A. Gladky, H. Hoogeveen, M. Y. Kovalyov, C. N. Potts, T. Tautenhahn} and \textit{S. L. van de Velde}, J. Sched. 1, No. 1, 31--54 (1998; Zbl 0909.90172)], the authors show that for the bicriteria problem under consideration one can order the jobs according to the well-known SPT rule and then form an optimal schedule, specified by the jobs that start each batch. In the paper a dynamic programming algorithm (DP-algorithm) is developed to find a Pareto optimal schedule for the bicriteria problem. The running time of DP-algorithm is \(O(n)\). To generate all Pareto optimal solutions, a basic method is the so-called \(\epsilon\)-constrained approach (see \textit{H. Hoogeveen} [Eur. J. Oper. Res. 167, No. 3, 592--623 (2005; Zbl 1154.90458)]). Using this approach and the DP algorithm, the authors demonstrate how to produce all Pareto optimal solutions to the problem under consideration in \(O(n^3)\) time. The number of Pareto optimal schedules for this bicriteria problem is proved to be at most \(n(n-1)/2 +1\).