Makespan Minimization of a Capacitated Batch Processing MachineUsing Lagrange Relaxation

摘要

A batch processing machine which can process a batch of jobs as long as the total number of jobs and the total sizeof all the jobs in a batch do not exceed its capacity is considered. Given the processing times and sizes of the jobs,the jobs need to be grouped into batches and the batches need to be scheduled to minimize the makespan. The batchprocessing time is equal to the longest processing job in the batch. The problem under study is NP-hard. ALagrangian Relaxation approach is proposed to find good lower bounds and a heuristic is proposed to find feasiblesolutions. Experiments were conducted to evaluate the performance of the proposed approach by comparing itsresults with a simulated annealing algorithm.