Minimizing weighted number of early and tardy jobs with a common due window involving location penalty

Minimizing weighted number of early and tardy jobs with a common due window involving location penalty

0.00 Avg rating0 Votes
Article ID: iaor2003187
Country: Netherlands
Volume: 108
Issue: 1
Start Page Number: 33
End Page Number: 54
Publication Date: Nov 2001
Journal: Annals of Operations Research
Authors: , ,
Keywords: programming: dynamic
Abstract:

This paper studies a single machine scheduling problem to minimize the weighted number of early and tardy jobs with a common due window. There are n non-preemptive and simultaneously available jobs. Each job will incur an early (tardy) penalty if it is early (tardy) with respect to the common due window under a given schedule. The window size is a given parameter but the window location is a decision variable. The objective of the problem is to find a schedule that minimizes the weighted number of early and tardy jobs and the location penalty. We show that the problem is NP-complete in the ordinary sense and develop a dynamic programming based pseudo-polynomial algorithm. We conduct computational experiments, the results of which show that the performance of the dynamic algorithm is very good in terms of memory requirement and CPU time. We also provide polynomial time algorithms for two special cases.

Reviews

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