Scheduling a single batch processing machine with non-identical two-dimensional job sizes

This paper considers a single batch processing machine scheduling problem with non-identical two-dimensional job sizes. Jobs may be rotated but must be placed orthogonally without overlapping in the machine. The machine can simultaneously process a batch of jobs as long as its two-dimensional capacity is not exceeded. The processing time of a batch is defined by the longest processing time of all jobs in the batch. The objective is to assign jobs to batches considering the machine capacity constraint such that the makespan is minimized. An improved mixed integer programming formulation is proposed to reduce the solution space. 16 heuristics, combining four job sequencing, two batch selection, and two job placement alternatives, are investigated. The effectiveness of the model and heuristics is analyzed through a comprehensive experimental study. The results show that the LPTBFSA heuristic outperforms the others, in which jobs are sorted in decreasing processing time, a batch is selected for each job based on the best-fit algorithm, and a job is placed in the selected batch following the "as compact as possible" packing principle. The LPTFFSA heuristic also works well, in which the first-fit algorithm is used to select a batch for each job.