Journal
ANNALS OF OPERATIONS RESEARCH
Volume 191, Issue 1, Pages 171-181Publisher
SPRINGER
DOI: 10.1007/s10479-011-1000-6
Keywords
Scheduling; Due date assignment; Batching; Number of tardy jobs
Categories
Funding
- Natural Sciences and Engineering Research Council of Canada [1798-08]
Ask authors/readers for more resources
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 NP-hard problems reduce to our problem. Then we propose a pseudo-polynomial algorithm for the problem, establishing that it is NP-hard only in the ordinary sense. Finally, we convert the algorithm into an efficient fully polynomial time approximation scheme.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available