Parallel machine scheduling with batch delivery costs

Parallel machine scheduling with batch delivery costs

0.00 Avg rating0 Votes
Article ID: iaor20012318
Country: Netherlands
Volume: 68
Issue: 2
Start Page Number: 177
End Page Number: 183
Publication Date: Jan 2000
Journal: International Journal of Production Economics
Authors: ,
Keywords: programming: dynamic
Abstract:

We consider a scheduling problem in which n independent and simultaneously available jobs are to be be processed on m parallel machines. The jobs are delivered in batches and the delivery date of a batch is equal to the completion time of the last job in the batch. The delivery cost depends on the number of deliveries. The objective is to minimize the sum of the total flow time and delivery cost. We first show that the problem is NP-complete in the ordinary sense even when m = 2, and NP-complete in the strong sense when m is arbitrary. Then we develop a dynamic programming algorithm to solve the problem. The algorithm is pseudopolynomial when m is constant and the number of batches has a fixed upper bound. Finally, we identify two polynomially solvable cases by introducing their corresponding solution methods.

Reviews

Required fields are marked *. Your email address will not be published.