SINGLE-MACHINE SCHEDULING TO MINIMIZE BATCH DELIVERY AND JOB EARLINESS PENALTIES

We study a problem in which a set of n jobs has to be batched as well as scheduled for processing on a single machine. A constant machine se t-up time is required before the first job of each batch is processed. A schedule specifies the sequence of batches, where each batch compri ses a sequence of jobs. The batch delivery time is defined as the comp letion time of the last job in a batch. The earliness of a job is defi ned as the difference between the delivery time of the batch to which it belongs and the job completion time. The objective is to find a num ber B of batches and a schedule so as to minimize the sum of the total weighted job earliness and mean batch delivery time. The problem is s hown to be strongly NP-hard. It remains strongly NP-hard if the set-up time is zero and B less than or equal to U for any variable U greater than or equal to 2 or if B greater than or equal to U for any constan t U greater than or equal to 2. The problem is proved to be ordinary N P-hard even if the set-up time is zero and B less than or equal to 2. For the case B less than or equal to U, a dynamic programming algorith m is presented, which is pseudopolynomial for any constant U greater t han or equal to 2. Algorithms with O(n(2)) running times are derived f or the cases when all weights are equal or all processing times are eq ual. For the general problem, a family of heuristics is suggested. Com putational experiments on the proposed heuristic algorithm are conduct ed. The results suggest that the heuristics are effective in generatin g near-optimal solutions quickly.