Scheduling a capacitated batch-processing machine to minimize makespan

This paper aims at improving the utilization of a single batch-processing machine. The batch-processing machine can process a batch of jobs, as long as the number of jobs and the total size of all the jobs in a batch do not violate the machine's capacity. The processing time of the job and its size is known. The processing time of a batch is the longest processing time among all the jobs in the batch. The objective is to minimize the makespan. Since the problem under study is NP-hard, a Simulated Annealing (SA) approach is proposed. The effectiveness of our solution procedure in terms of solution quality and run time is evaluated through experiments. The results obtained from the SA approach were compared with a commercial solver called CPLEX. Our computational study demonstrates the effectiveness of our approach in solving problem instances with 20 or more jobs in a shorter run time with better solutions.