Impact of learning and fatigue factors on single machine scheduling with penalties for tardy jobs. (English) Zbl 0955.90029

Summary: 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-Hodgon’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 maximum-weighted network path algorithm. Then we combine these two techniques and solve the 0-1 knapsack proble, by inducing a nested constraint structure and constructing a network with fewer nodes.


90B35 Deterministic scheduling theory in operations research
90C27 Combinatorial optimization
Full Text: DOI


[1] Baker, K. R., (Introduction to Sequencing and Scheduling (1974), John Wiley and Sons, Inc.: John Wiley and Sons, Inc. New York, NY)
[2] French, S., (Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop (1982), Halstead Press: Halstead Press New York, NY) · Zbl 0479.90037
[3] Dondeti, V. R.; Mohanty, B. B., Minimizing average flow time on a single machine with learning and fatigue factors, (Proceedings of the 25th Annual Meeting. Proceedings of the 25th Annual Meeting, Southeast Region of the Decision Sciences Institute (1995)), 278-280
[4] Garey, M. R.; Johnson, D. S., (Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Company: W.H. Freeman and Company San Francisco, CA) · Zbl 0411.68039
[5] Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York, NY) · Zbl 0366.68041
[6] Lawler, E. L., Sequencing to minimize the weighted number of tardy jobs, Rev. Francaise Automat. Informat. Recherche Operationnelle Series Bleue, 10.5, supplement, 27-33 (1976) · Zbl 0333.68044
[7] Meilijson, I.; Tamir, A., Minimizing flow time on parallel identical processors with variable unit processing time, Operations Research, 32, 440-448 (1984) · Zbl 0573.90054
[8] Morton, T. E.; Pentico, D. W., (Heuristic Scheduling Systems with Applications to Production Engineering and Project Management (1993), John Wiley and Sons: John Wiley and Sons New York, NY)
[9] Nemhauser, G. L.; Wolsey, L. A., (Integer and Combinatorial Optimization (1988), John Wiley and Sons, Inc.: John Wiley and Sons, Inc. New York, NY) · Zbl 0652.90067
[10] Parzen, E., (Moderm Probability Theory and Applications (1960), John Wiley and Sons: John Wiley and Sons New York)
[11] Pinedo, M., (Scheduling—Theory, Algorithms, and Systems (1995), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.