Minimizing makespan on a single batch processing machine with nonidenticaljob sizes

We deal with the problem of minimizing makespan on a single batch processin g machine. In this problem, each job has both processing time and size (cap acity requirement). The batch processing machine can process a number of jo bs simultaneously as long as the total size of these jobs being processed d oes not exceed the machine capacity. The processing time of a batch is just the processing time of the longest job in the batch. An approximation algo rithm with worst-case ratio 3/2 is given for the version where the processi ng times of large jabs (with sizes greater than 1/2) are not less than thos e of small jobs (with sizes not greater than 1/2). This result is the best possible unless P = NP. For the general case, we propose an approximation a lgorithm with worst-case ratio 7/4. A number of heuristics by Uzosy are als o analyzed and compared. (C) 2001 John Wiley & Sons, Inc. Naval Research Lo gistics 48. 226-240, 2001.