A branch and price algorithm to minimize makespan on a single batch processing machine with non-identical job sizes

In this paper, we consider the scheduling problem on a single batch processing machine with nonidentical job sizes: in which the machine has a limited capacity and can process a group of jobs simultaneously as a batch. The processing time of a batch is the longest processing time of all jobs in the batch. The objective is to minimize the makespan. We formulate the problem using Dantzig-Wolfe decomposition as a set partitioning problem. Based on the set partitioning formulation, we present a tight lower bound using column generation method. A heuristic algorithm is also developed to generate the basic solution in the column generation method. A branch and price algorithm which combines the column generation technique with branch and bound method is then presented to obtain the optimal solution of the problem. The efficiency of the proposed branch and price algorithm is ultimately compared to the branch and bound algorithm from the literature, based on the generated sample problems. (C) 2009 Elsevier Ltd. All rights reserved.