Mixed batch scheduling on identical machines.

This paper studies a new mixed batch scheduling problem that arises in vacuum heat treatment. A mixed batch machine can process at most a given number of jobs simultaneously. The processing time of a batch is the weighted sum of the maximum processing time and the total processing time of jobs in the batch. The objective is to minimize the makespan. We first prove that the problem on a single machine can be solved in polynomial time, while the problem on multiple identical machines is NP-hard. Then, we develop a pseudopolynomial time exact algorithm when the number of machines is fixed. Further, we analyze the worst-case performance ratio of a full batch longest processing time algorithm and design Algorithm LPT-Greedy with improved worst-case performance. [ABSTRACT FROM AUTHOR]