A survey of results for sequencing problems with controllable processing times. (English) Zbl 0693.90056

This paper reviews algorithms and complexity results for scheduling problems in which the processing time of a job is a decision variable. For each job, an upper and lower bound on its processing time is specified and a processing cost, which is a linear decreasing function of processing time, is given. In addition to the processing cost, a schedule cost (maximum completion time, maximum lateness or total weighted completion time, for example) is associate with completion times of the jobs. Most results relate to the problem of scheduling a single machine to minimize the processing plus schedule cost. Throughout the paper, a typical algorithm first selects a processing order of the jobs and then solves a linear program to fix the processing times; this linear program can often be solved very efficiently. For some problems, this type of algorithm provides an exact solution; for others, it is a heuristic and worst-case performance bounds are available.
Reviewer: C.N.Potts


90B35 Deterministic scheduling theory in operations research
68Q25 Analysis of algorithms and problem complexity
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
Full Text: DOI


[1] Błazewicz, J.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Scheduling subject to resource constraints: Classification and complexity, Discrete Appl. Math., 5, 11-24 (1983) · Zbl 0516.68037
[2] Elmaghraby, S. E., Activity Networks (1977), Wiley: Wiley New York · Zbl 0203.52502
[3] Grabowski, J.; Janiak, A., Job-shop scheduling with resource-time models of operations, European J. Oper. Res., 28, 58-73 (1986) · Zbl 0614.90048
[4] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and scheduling: A survey, Ann. Discrete Math., 5, 287-326 (1979) · Zbl 0411.90044
[5] Ishi, H.; Martel, C.; Masuda, T.; Nishida, A generalized uniform processor system, Oper. Res., 33, 346-362 (1985) · Zbl 0587.90055
[6] Jackson, J. R., Scheduling a production line to minimize maximum tardiness, (Res. Rept., 43 (1955), Management Science Research Project, University of California: Management Science Research Project, University of California Los Angeles, CA)
[7] Johnson, S. M., Optimal two and three stage production scheduling with set-up times included, Naval Res. Logist. Quart., 1, 61-68 (1954) · Zbl 1349.90359
[8] Lageweg, B. J.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Minimizing maximum lateness on one machine, computational experience and some applications, Statist. Neerlandica, 30, 25-41 (1976) · Zbl 0336.90029
[9] Lawler, E. L., Combinatorial Optimization: Networks and Matroids (1976), Holt, Rinehart and Winston: Holt, Rinehart and Winston New York · Zbl 0358.68059
[10] Lawler, E. L.; Moore, J. M., A functional equation and its application to resource allocation and sequencing problems, Management Sci., 16, 77-84 (1969) · Zbl 0184.23303
[11] Lenstra, J. K.; Rinnooy Kan, A. H.G.; Brucker, P., Complexity of machine scheduling problems, Ann. Discrete Math., 1, 343-362 (1977) · Zbl 0301.90025
[12] Nowicki, E.; Zdrzałka, S., Two-machine flow shop scheduling problem with controllable job processing times, European J. Oper. Res., 34, 208-220 (1988) · Zbl 0647.90041
[13] Potts, C. N., Anaysis of a heuristic for one machine with release dates and delivery times, Oper. Res., 28, 1436-1441 (1980) · Zbl 0447.90041
[14] Ruiz Diaz, F. M.; French, S., A survey of multi-objective combinatorial scheduling, (French, S.; Hartley, R.; Thomas, L. C.; White, D. J., Multi-Objective Decision Making (1983), Academic Press: Academic Press New York) · Zbl 0541.90058
[15] Ruiz Diaz, F. M.; French, S., A note on SPT scheduling of a single machine with controllable processing time (1984), Department of Decision Theory, University of Manchester, Note 154
[16] Słowinski, R., Multiobjective network scheduling with efficient use of renewable and nonrenewable resource, European J. Oper. Res., 7, 265-273 (1981) · Zbl 0455.90049
[17] Talbot, B. F., Resource-constrained project scheduling with time-resource tradeoff: The nonpre-emptive case, Management Sci., 28, 1197-1210 (1986) · Zbl 0493.90042
[18] Tuzikov, A. V., A two-criterion scheduling problem allowing for variation in job execution, Z̆. Vyc̆isl. Mat. i Mat. Fiz., 24, 1585-1590 (1984) · Zbl 0572.90054
[19] Vickson, R. G., Two single machine sequencing problems involving controllable job processing times, AIIE Trans., 12, 258-262 (1980)
[20] Vickson, R. G., Choosing the job sequence and processing times to minimize total processing plus flow cost on a single machine, Oper. Res., 28, 1155-1167 (1980) · Zbl 0449.90054
[21] van Wassenhove, L. N.; Baker, K. R., A bicriterion approach to time/cost tradeoffs in sequencing, European J. Oper. Res., 11, 48-54 (1982) · Zbl 0482.90043
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.