Hierarchical optimization with double due dates on an unbounded parallel-batching machine to minimize maximum lateness

This paper studies a hierarchical optimization problem on an unbounded parallel‐batching machine, in which two objective functions are maximum lateness induced by two sets of due dates, representing different purposes of two decision‐makers. By a hierarchical optimization problem, we mean the problem of optimizing the secondary criterion under the constraint that the primary criterion is optimized. A parallel‐batching machine is a machine that can handle several jobs in a batch in which all jobs start and complete respectively at the same time. We present an $O(nlogP)$ ‐time algorithm and an $O(n^3)$ ‐time algorithm for this hierarchical scheduling problem, where P is the total processing time of all jobs.