Parallel-Machine Scheduling to Minimize Flowtime, Holding, and Batch Delivery Costs

This paper considers a batch delivery scheduling problem in which n independent and simultaneously available jobs are to be processed on m unrelated or uniform parallel machines. The jobs scheduled on the same machine are delivered in batches to customers and the delivery date of a batch equals the completion time of the last job in the batch. The number of jobs in each delivery batch is constrained by the batch size, and the cost of delivering a batch depends not only on the number of jobs in the batch but also on the machine on which the batch is processed. The objective is to find jointly the optimal number of batches on each machine, the optimal assignment of jobs to the batches, and the optimal job processing sequence to minimize the sum of total flowtime, total holding time, and delivery costs. When the number of batches has a fixed upper bound, we present polynomial-time algorithms to solve the problems with unrelated and uniform parallel machines. If the bound constraint on the number of batches is relaxed, we provide polynomial-time algorithms to solve two special cases of the problem with uniform parallel machines.