Mixed batch scheduling with non-identical job sizes to minimize makespan

This paper studies a mixed batch scheduling problem with non-identical job sizes to minimize the makespan. Multiple jobs can be processed simultaneously as a batch on a mixed batch machine as long as the total size of the jobs in the batch does not exceed the machine capacity. The processing time of a batch is the weighted sum of the maximum processing time and total processing time of the jobs in the batch. We show that the problem is strongly NP-hard even with a single machine, and analyze the worst-case performance ratio of the longest processing time first fit (LPTFF) algorithm. Furthermore, we present the longest processing time first fit greedy (LPTFFG) algorithm, and show that the worst-case performance ratio of algorithm LPTFFG is better than that of algorithm LPTFF. Computational experiments show that algorithm LPTFFG fits the case with a large number of machines, small job sizes, and small weight of the maximum processing time.