Single-machine scheduling with learning considerations. (English) Zbl 0946.90025

Summary: The focus of this work is to analyze learning in single-machine scheduling problems. It is surprising that the well-known learning effect has never been considered in connection with scheduling problems. It is shown in this paper that even with the introduction of learning to job processing times two important types of single-machine problems remain polynomially solvable.


90B35 Deterministic scheduling theory in operations research


scheduling; learning
Full Text: DOI


[1] Alidaee, B; Ahmadian, A, Two parallel machine sequencing problems involving controllable job processing times, European journal of operational research, 70, 335-341, (1993) · Zbl 0791.90028
[2] Baker, K.R., 1974. Introduction to Sequencing and Scheduling. Wiley, New York
[3] Baker, K.R; Scudder, G.D, Sequencing with earliness and tardiness penalties: A review, Operations research, 38, 22-36, (1990) · Zbl 0699.90052
[4] Biskup, D., Cheng, T.C.E., 1997a. Single-machine scheduling with controllable processing times and earliness, tardiness and completion time penalties. Engineering Optimization, to appear
[5] Biskup, D., Cheng, T.C.E., 1997b. Multiple-machine scheduling with earliness, tardiness and completion time penalties. Computers & Operations Research, to appear · Zbl 0957.90056
[6] Cheng, T.C.E; Chen, Z.L; Li, C.-L, Parallel-machine scheduling with controllable processing times, IIE transactions, 28, 177-180, (1996)
[7] Cheng, T.C.E; Oguz, C; Qi, X.D, Due-date assignment and single machine scheduling with compressible processing times, International journal of production economics, 43, 29-35, (1996)
[8] Higgins, P., Le Roy, P., Tierney, L., 1996. Manufacturing Planning and Control - Beyond MRP II. Chapman & Hall, London
[9] Kanet, J.J, Minimizing the average deviation of job completion times about a common due date, Naval research logistics quarterly, 28, 643-651, (1981) · Zbl 0548.90037
[10] Li, C.-L; Cheng, T.C.E, An economic production quantity model with learning and forgetting considerations, Production and operations management, 3, 118-132, (1994)
[11] Li, C.-L; Sewell, E.C; Cheng, T.C.E, Scheduling to minimize release-time resource consumption and tardiness penalties, Naval research logistics, 42, S.949-966, (1995) · Zbl 0845.90074
[12] Nadler, G; Smith, W.D, Manufacturing progress functions for types of processes, International journal of production research, 2, 115-135, (1963)
[13] Panwalkar, S.S., Dudek, R.A., Smith, M.L., 1973. Sequencing research and the industrial scheduling problem. In: Elmaghraby, S.E. (Ed.), Symposium on the Theory of Scheduling and its Applications. Springer, Berlin, pp. 29-38 · Zbl 0269.90025
[14] Panwalkar, S.S; Smith, M.L; Seidmann, A, Common due date assignment to minimize total penalty for the one machine scheduling problem, Operations research, 30, S.391-399, (1982) · Zbl 0481.90042
[15] Panwalkar, S.S; Rajagopalan, R, Single-machine sequencing with controllable processing times, European journal of operational research, 59, 298-302, (1992) · Zbl 0760.90058
[16] Papadimitriou, C.H., Steiglitz, K., 1982. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, NJ · Zbl 0503.90060
[17] Schmenner, R.W, The merit of making things fast, Sloan management review, 30, 11-17, (1988)
[18] Smith, W.E, Various optimizers for single-stage production, Naval research logistics quarterly, 3, 59-66, (1956)
[19] Vasilev, S.H; Foote, B.L, On minimizing resource consumption with constraints on the makespan and the total completion time, European journal of operational research, 96, 612-621, (1997) · Zbl 0917.90202
[20] Vickson, R.G, Choosing the job sequence and processing times to minimize total processing plus flow cost on a single machine, Operations research, 28, 1155-1167, (1980) · Zbl 0449.90054
[21] Vickson, R.G, Two single machine sequencing problems involving controllable job processing times, AIIE transactions, 12, 258-262, (1980)
[22] Wright, T.P, Factors affecting the cost of airplanes, Journal of aeronautical sciences, 3, 122-128, (1936)
[23] Yelle, L.E, The learning curve: historical review and comprehensive survey, Decision science, 10, 302-328, (1979)
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.