Impact of learning and fatigue factors on single machine scheduling with penalties for tardy jobs

Impact of learning and fatigue factors on single machine scheduling with penalties for tardy jobs

0.00 Avg rating0 Votes
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: ,
Keywords: knapsack problem
Abstract:

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.

Reviews

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