MINIMIZING MEAN FLOW TIMES CRITERIA ON A SINGLE BATCH PROCESSING MACHINE WITH NONIDENTICAL JOBS SIZES

This paper considers the problem of scheduling jobs with non-identical capacity requirements or sizes on a single-batch processing machine ( BPM) to minimize the mean-flow times of jobs. A batch processing machi ne is one which can process up to B jobs simultaneously. The processin g time of a batch is equal to the longest processing time among all jo bs in the batch. We provide various new heuristics for this problem. C omputational experiments shaw that the heuristics are capable of obtai ning near-optimal solutions in very reasonable CPU times. (C) 1998 Els evier Science B.V. All rights reserved.