A batch processing machine which can process a batch of jobs as long as the total number of jobs and the total size of 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 batch processing time is equal to the longest processing job in the batch. The problem under study is NP-hard. A Lagrangian Relaxation approach is proposed to find good lower bounds and a heuristic is proposed to find feasible solutions. Experiments were conducted to evaluate the performance of the proposed approach by comparing its results with a simulated annealing algorithm.
展开▼
