Article ID: | iaor19992312 |
Country: | Netherlands |
Volume: | 105 |
Issue: | 3 |
Start Page Number: | 509 |
End Page Number: | 524 |
Publication Date: | Mar 1998 |
Journal: | European Journal of Operational Research |
Authors: | Mohanty Bidhu B., Dondeti V. Reddy |
Keywords: | knapsack problem |
We consider a single machine scheduling problem in which the machine experiences the effects of learning or fatigue as it continues to work and the jobs have due dates and are subject to penalties if they are not completed on time. Because of the effects of learning or fatigue, the performance rate of the machine varies over time. As a result, the processing time of a job depends on its work content as well as the total work content of the jobs completed prior to its loading. In this paper, we prove that even when the machine works at a variable rate, the pair-wise interchange of jobs minimizes the maximum tardiness and a simple modification to the well-known Moore–Hodgson's algorithm yields the minimum number of tardy jobs. Further, we formulate the problem of minimizing the total penalty for tardy jobs as a 0–1 knapsack problem with nested constraints, and solve it by using dynamic programming recursion as well as the maximum-weighted network path algorithm. Then we combine these two techniques and solve the 0–1 knapsack problem, by inducing a nested constraint structure and constructing a network with fewer nodes.