Abstract
In this paper we study a single machine scheduling problem in which the job processing times will decrease as a result of learning. A volume-dependent piecewise linear processing time function is used to model the learning effects. The objective is to minimize the maximum lateness. We first show that the problem is NP-hard in the strong sense and then identify two special cases which are polynomially solvable. We also propose two heuristics and analyse their worst-case performance.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
G.L. Alder, The effects of learning on optimal single and multiple lot size determination, Unpublished Ph.D. dissertation, New York University (1973).
E.S. Buffa, Meeting the Competitive Challenge (Irwin, Homewood, 1984).
T.C.E. Cheng and M.Y. Kovalyov, Scheduling with learning effects on job processing times, Working Paper, No. 06/94, Faculty of Business and Information Systems, The Hong Kong Polytechnic University (1994).
E.N. Corlett and V.J. Morcombe, Straightening out the learning curve, Personnel Management 2 (1970) 14–19.
M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NPCompleteness (Freeman, New York, 1979).
M.R. Garey, D.S. Johnson and R. Sethi, The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research 1 (1976) 117–129.
S. Gawiejnowicz, A note on scheduling on a single processor with speed dependent on a number of executed jobs, Information Processing Letters 56 (1996) 297–300.
R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics 5 (1979) 287–326.
T.J. Greene and R.P. Sadowski, A review of cellular manufacturing assumptions, advantages and design techniques, Journal of Operations Management 4 (1984) 85–97.
W.M. Hancock, Prediction of learning rates for manual operations, Journal of Industrial Engineering 18 (1967) 42–47.
K.I.-J. Ho, J.Y.-T. Leung and W.-D. Wei, Complexity of scheduling tasks with time-dependent execution times, Information Processing Letters 48 (1993) 315–320.
E.K. Ivanov, Group Production Organization and Technology (Translated by E. Bishop) (Business Publications, London, 1968).
J.R. Jackson, Scheduling a production line to minimize maximum tardiness, Research Report 43, Management Science Research Project, UCLA (1955).
E.C. Keachie and R.J. Fontana, Effects of learning on optimal lot size, Management Science 13 (1966) 102–108.
M. Kilbridge, Predetermined learning curves for clerical operations, Journal of Industrial Engineering 10 (1959) 203–209.
H. Kise, T. Ibaraki and H. Mine, Performance analysis of six approximation algorithms for the onemachine maximum lateness scheduling problem with ready times, Journal of the Operational Research Society of Japan 22 (1979) 205–224.
C.L. Li and T.C.E. Cheng, An economic production quantity model with learning and forgetting considerations, Production and Operations Management 3 (1994) 118–132.
I. Meilijson and A. Tamir, Minimizing flow time on parallel identical processors with variable unit processing time, Operations Research 32 (1984) 440–448.
C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization (Prentice-Hall, Englewood Cliffs, NJ, 1982).
D.R. Sule, A note on production time variation in determining EMQ under influence of learning and forgetting, AIIE Transactions 13 (1981) 91–95.
T.M. Wright, Factors affecting the cost of airplanes, Journal of Aeronautical Sciences 3 (1936) 122–128.
L.E. Yelle, The leaning curve: historical review and comprehensive survey, Decision Sciences 10 (1984) 302–327.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Cheng, T.E., Wang, G. Single Machine Scheduling with Learning Effect Considerations. Annals of Operations Research 98, 273–290 (2000). https://doi.org/10.1023/A:1019216726076
Issue Date:
DOI: https://doi.org/10.1023/A:1019216726076