zbMATH — the first resource for mathematics

Scheduling problems with a learning effect. (English) Zbl 1017.90051
Summary: In many realistic settings, the production facility (a machine, a worker) improves continuously as a result of repeatig the same or similar activities, hence, the later a given product is scheduled in the sequence, the shorter is production time. This “learning effect” is investigated in the context of various scheduling problems. It is shown in several examples that although the optimal schedule may be very different from that of the classical version of the problem, and the computational effort becomes significantly greater, polynomial-time solutions still exist. In particular, we introduce polynomial solutions for the single-machine makespan minimization problem, and two for multi-criteria single-machine problems and the minimum flow-time problem on parallel identical machines.

90B36 Stochastic scheduling theory in operations research
60K30 Applications of queueing theory (congestion, allocation, storage, traffic, etc.)
Full Text: DOI
[1] Bagchi, U.B., Simultaneous minimization of Mean and variation of flow-time and waiting time in single machine systems, Operations research, 37, 118-125, (1989) · Zbl 0661.90046
[2] Biskup, D., Single-machine scheduling with learning considerations, European journal of operational research, 115, 173-178, (1999) · Zbl 0946.90025
[3] Jackson, J.R., 1955. Scheduling a production line to minimize maximum tardiness. Research Report 43, Management Science Research Project, University of California, Los Angeles
[4] Moore, J.M., An n job one machine sequencing algorithm for minimizing the number of late jobs, Management science, 15, 102-109, (1968) · Zbl 0164.20002
[5] Nadler, G.; Smith, W.D., Manufacturing progress functions for types of processes, International journal of production research, 2, 115-135, (1963)
[6] Panwalker, S.S.; Smith, M.L.; Seidmann, A., Common due-date assignment to minimize total penalty for the one machine scheduling problem, Operations research, 30, 391-399, (1982) · Zbl 0481.90042
[7] Smith, M.L., Various optimizers for single-machine production, Naval research logistics quarterly, 3, 59-66, (1956)
[8] Yelle, L.E., The learning curve: historic 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.