Minimizing the weighted number of tardy jobs with due date assignment and capacity‐constrained deliveries

Minimizing the weighted number of tardy jobs with due date assignment and capacity‐constrained deliveries

0.00 Avg rating0 Votes
Article ID: iaor201111674
Volume: 191
Issue: 1
Start Page Number: 171
End Page Number: 181
Publication Date: Nov 2011
Journal: Annals of Operations Research
Authors: ,
Keywords: scheduling, allocation: resources, programming: dynamic
Abstract:

We study a supply chain scheduling problem, where a common due date is assigned to all jobs and the number of jobs in delivery batches is constrained by the batch size. Our goal is to minimize the sum of the weighted number of tardy jobs, the due‐date‐assignment costs and the batch‐delivery costs. We show that some well‐known 𝒩𝒫 equ1 ‐hard problems reduce to our problem. Then we propose a pseudo‐polynomial algorithm for the problem, establishing that it is 𝒩𝒫 equ2 ‐hard only in the ordinary sense. Finally, we convert the algorithm into an efficient fully polynomial time approximation scheme.

Reviews

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