Skip to main content
Log in

Fifty years of scheduling: a survey of milestones

  • Special Issue Paper
  • Published:
Journal of the Operational Research Society

Abstract

Scheduling has become a major field within operational research with several hundred publications appearing each year. This paper explores the historical development of the subject since the mid-1950s when the landmark publications started to appear. A discussion of the main topics of scheduling research for the past five decades is provided, highlighting the key contributions that helped shape the subject. The main topics covered in the respective decades are combinatorial analysis, branch and bound, computational complexity and classification, approximate solution algorithms and enhanced scheduling models.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

References

  • Adams J, Balas E and Zawack D (1988). The shifting bottleneck procedure for job shop scheduling. Mngt Sci 34: 391–401.

    Article  Google Scholar 

  • Afrati F, Bampis E, Chekuri C, Karger D, Kenyon C, Khanna S, Mills I, Queyranne M, Skutella M, Stein C and Sviridenko M (1999). Approximation schemes for minimizing average weighted completion time with release dates. In: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press: Los Alamitos, CA, pp. 32–43.

    Google Scholar 

  • Ahuja RK, Ergun Ö, Orlin JB and Punnen AP (2002). A survey of very large-scale neighborhood search techniques. Disc Appl Math 123: 75–102.

    Article  Google Scholar 

  • Akers SB Jr, and Friedman J (1955). A non-numerical approach to production scheduling problems. Opns Res 3: 429–442.

    Google Scholar 

  • Aksjonov VA (1988). A polynomial-time algorithm for an approximate solution of a scheduling problem. Upravlyaemye Sistemy 28: 8–11 (in Russian).

    Google Scholar 

  • Anderson EJ and Potts CN (2004). Online scheduling of a single machine to minimize total weighted completion time. Math Opns Res 29: 686–697.

    Article  Google Scholar 

  • Atkin JAD, Burke EK, Greenwood JS and Reeson D (2007). Hybrid metaheuristics to aid runway scheduling at London Heathrow airport. Trans Sci 41: 90–106.

    Article  Google Scholar 

  • Baker KR (1974). Introduction to Sequencing and Scheduling . Wiley: New York.

    Google Scholar 

  • Baker KR and Scudder GD (1990). Sequencing with earliness and tardiness penalties: A review. Opns Res 38: 22–36.

    Article  Google Scholar 

  • Balas E and Vazacopoulos A (1998). Guided local search with shifting bottleneck for job shop scheduling. Mngt Sci 44: 262–275.

    Article  Google Scholar 

  • Bárány I and Fiala T (1982). Nearly optimum solution of multi-machine scheduling problems. Szigma 15: 177–191 (in Hungarian).

    Google Scholar 

  • Barnes JW and Chambers JB (1993). Solving the job shop scheduling problem with tabu search. IIE Trans 27: 257–263.

    Article  Google Scholar 

  • Beasley JE, Sonander J and Havelock P (2001). Scheduling aircraft landings at London Heathrow using a population heuristic. J Opl Res Soc 52: 483–493.

    Article  Google Scholar 

  • Billaut J-C, Gribkovskaia IV and Strusevich VA (2008). An improved approximation algorithm for the two-machine open shop scheduling problem with family setup times. IIE Trans 40: 478–493.

    Article  Google Scholar 

  • Blazewicz J, Ecker KH, Schmidt G and Wȩglarz J (1993). Scheduling in Computer and Manufacturing Systems . Springer: Berlin.

    Book  Google Scholar 

  • Boese KD, Kahng AB and Muddu S (1994). A new adaptive multi-start technique for combinatorial global optimizations. Opns Res Lett 16: 101–113.

    Article  Google Scholar 

  • Bratley P, Florian M and Robillard P (1973). On sequencing with earliest starts and due dates with application to computing bounds for the (n|m|G|Fmax) problem. Nav Res Logist Quart 20: 57–67.

    Article  Google Scholar 

  • Brooks GH and White CR (1965). An algorithm for finding optimal or near optimal solutions to the production scheduling problem. J Indust Eng 16: 34–40.

    Google Scholar 

  • Brucker P (1995). Scheduling Algorithms . Springer: Berlin.

    Book  Google Scholar 

  • Brucker P, Hurink J and Werner F (1996). Improving local search heuristics for some scheduling problems—I. Disc Appl Math 65: 97–122.

    Article  Google Scholar 

  • Brucker P, Hurink J and Werner F (1997). Improving local search heuristics for some scheduling problems. Part II. Disc Appl Math 72: 47–69.

    Article  Google Scholar 

  • Brucker P, Gladky A, Hoogeveen JA, Kovalyov MY, Potts CN, Tautenhahn T and Van de Velde SL (1998). Scheduling a batching machine. J Schedul 1: 31–54.

    Article  Google Scholar 

  • Bruno JL and Downey PJ (1978). Complexity of task sequencing with deadlines, set-up times and changeover costs. SIAM J Comput 7: 393–404.

    Article  Google Scholar 

  • Bruno JL, Coffman EG Jr, and Sethi R (1974). Scheduling independent tasks to reduce mean finishing time. Comm ACM 17: 382–387.

    Article  Google Scholar 

  • Carlier J (1982). The one-machine sequencing problem. Eur J Opl Res 11: 42–47.

    Article  Google Scholar 

  • Carlier J and Pinson E (1989). An algorithm for solving the job-shop problem. Mngt Sci 35: 164–176.

    Article  Google Scholar 

  • Cerny V (1985). Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. J Opti Theory Appl 45: 41–51.

    Article  Google Scholar 

  • Charlton JM and Death CC (1970). A method of solution for general machine-scheduling problems. Opns Res 18: 689–707.

    Article  Google Scholar 

  • Chen B and Strusevich VA (1993). Approximation algorithms for three-machine open shop scheduling. ORSA J Comput 5: 321–326.

    Article  Google Scholar 

  • Chen B, Glass CA, Potts CN and Strusevich VA (1996). A new heuristic for three-machine flow shop scheduling. Opns Res 44: 891–898.

    Article  Google Scholar 

  • Chen B, Potts CN and Strusevich VA (1998). Approximation algorithms for two-machine flow shop scheduling with batch setup times. Math Progr B 82: 255–271.

    Article  Google Scholar 

  • Chen Z-L (2009). Integrated production and outbound distribution scheduling: Review and extensions. Opns Res, to appear.

  • Chen Z-L and Hall NG (2007). Supply chain scheduling: Conflict and cooperation in assembly systems. Opns Res 55: 1072–1089.

    Article  Google Scholar 

  • Chen Z-L and Powell WB (1999). Solving parallel machine scheduling problems by column generation. INFORMS J Comput 11: 78–94.

    Article  Google Scholar 

  • Cheng TCE and Kahlbacher HG (1993). Scheduling with delivery and earliness penalties. Asia-Pacific J Opl Res 10: 145–152.

    Google Scholar 

  • Congram RK, Potts CN and Van de Velde SL (2002). An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem. INFORMS J Comput 14: 52–67.

    Article  Google Scholar 

  • Conway RW, Maxwell WL and Miller LW (1967). Theory of Scheduling . Addison-Wesley: Reading, MA.

    Google Scholar 

  • Cook SA (1971). The complexity of theorem-proving procedures. In: Proceedings of the 3rd Annual ACM Symposium on Theory of Computing. The Association for Computing Machinery: New York, pp. 151–158.

    Google Scholar 

  • Crauwels HAJ, Potts CN and Van Wassenhove (1998). Local search heuristics for the single machine total weighted tardiness scheduling problem. INFORMS J Comput 10: 341–350.

    Article  Google Scholar 

  • Croes GA (1958). A method for solving traveling-salesman problems. Opns Res 6: 791–812.

    Article  Google Scholar 

  • Crowder H and Padberg MW (1980). Solving large-scale symmetric travelling salesman problems to optimality. Mngt Sci 26: 495–509.

    Article  Google Scholar 

  • Davis L (1985). Job shop scheduling with genetic algorithms. In: Grefenstette JJ (ed). Proceedings of the First International Conference on Genetic Algorithms and Their Applications. Lawrence Erlbaum: Hillsdale, NJ, pp. 136–140.

    Google Scholar 

  • Della Croce F, Tadei R and Volta G (1995). A genetic algorithm for the job shop problem. Comput Opns Res 22: 15–24.

    Article  Google Scholar 

  • Dell'Amico M and Trubian M (1993). Applying tabu-search to the job-shop scheduling problem. Ann Opns Res 41: 231–252.

    Article  Google Scholar 

  • Dempster MAH, Lenstra JJ and Rinnooy Kan AHG (eds). (1982). Deterministic and Stochastic Scheduling. Reidel: Dordrecht, the Netherlands.

  • de Werra D (1970). On some combinatorial problems arising in scheduling. CORS J 8: 165–175.

    Google Scholar 

  • de Werra D (1989). Graph-theoretical models for preemptive scheduling. In: Slowinski R and Weglarz J (eds). Advances in Project Scheduling. Elsevier: Amsterdam, pp. 171–185.

    Chapter  Google Scholar 

  • Dorndorf U and Pesch E (1995). Evolution based learning in a job shop scheduling environment. Comput Opns Res 22: 25–40.

    Article  Google Scholar 

  • Du J and Leung JY-T (1990). Minimizing total tardiness on one machine is NP-hard. Math Opns Res 15: 483–495.

    Article  Google Scholar 

  • Eastman WL (1958a). Linear programming with pattern constraints. PhD thesis, Report No. BL. 20, The Computation Laboratory, Harvard University.

  • Eastman WL (1958b). A solution to the traveling-salesman problem. Presentation at the American Summer Meeting of the Econometric Society, Cambridge, MA.

  • Edmonds J (1965). Paths, trees, and flowers. Canad J Math 17: 449–467.

    Article  Google Scholar 

  • Elmaghraby SE (1968). The one-machine sequencing problem with delay costs. J Indust Eng 19: 105–108.

    Google Scholar 

  • Emmons H (1969). One-machine sequencing to minimize certain functions of job tardiness. Opns Res 17: 701–715.

    Article  Google Scholar 

  • Falkenauer E and Bouffouix S (1991). A genetic algorithm for job shop. In: Proceedings of the 1991 IEEE International Conference on Robotics and Automation. IEEE Computer Society Press: Los Alamitos, CA, pp. 824–829.

    Chapter  Google Scholar 

  • Federgruen A and Groenvelt H (1986). Preemptive scheduling of uniform machines by ordinary network flow techniques. Mngt Sci 32: 341–349.

    Article  Google Scholar 

  • Fisher ML (1976). A dual algorithm for the one-machine scheduling problem. Math Progr 11: 229–251.

    Article  Google Scholar 

  • Gabow HN and Kariv O (1982). Algorithms for edge coloring bipartite graphs. SIAM J Comput 11: 117–129.

    Article  Google Scholar 

  • Gantt HL (1916). Work, Wages, and Profits, 2nd edn. Engineering Magazine Co: New York (reprinted by Hive Publishing Company: Easton, Maryland, 1973).

    Google Scholar 

  • Garey MR and Johnson DS (1979). Computers and Intractability. A Guide to the Theory of NP-Completeness . Freeman: San Francisco, CA.

    Google Scholar 

  • Garey MR, Johnson DS and Sethi R (1976). The complexity of flowshop and jobshop scheduling. Math Opns Res 1: 117–129.

    Article  Google Scholar 

  • Gelders L and Kleindorfer PR (1974). Coordinating aggregate and detailed scheduling decisions in the one-machine job shop: Part I, Theory. Opns Res 22: 46–60.

    Article  Google Scholar 

  • Gelders L and Kleindorfer PR (1975). Coordinating aggregate and detailed scheduling decisions in the one-machine job shop: Part II, Computation and structure. Opns Res 23: 312–324.

    Article  Google Scholar 

  • Gilmore PC and Gomory RE (1964). Sequencing a one-state variable machine: A solvable case of the traveling salesman problem. Opns Res 12: 665–679.

    Article  Google Scholar 

  • Glover F (1986). Future paths for integer programming and links to artificial intelligence. Comput Opns Res 13: 533–549.

    Article  Google Scholar 

  • Glover F (1989). Tabu search: Part I. ORSA J Comput 1: 190–206.

    Article  Google Scholar 

  • Glover F (1990). Tabu search: Part II. ORSA J Comput 2: 4–32.

    Article  Google Scholar 

  • Goldberg DE (1989). Genetic Algorithms in Search, Optimization and Machine Learning . Adison-Wesley: Reading, MA.

    Google Scholar 

  • Gonzalez T and Sahni S (1976). Open shop scheduling to minimize finish time. J Assoc Comput Mach 23: 665–679.

    Article  Google Scholar 

  • Gonzalez T and Sahni S (1978). Flowshop and jobshop schedules: Complexity and approximation. Opns Res 26: 36–52.

    Article  Google Scholar 

  • Graham RL (1966). Bounds for certain multiprocessing anomalies. Bell Syst Techn J 45: 1563–1581.

    Article  Google Scholar 

  • Graham RL (1969). Bounds on multiprocessing timing anomalies. SIAM J Appl Math 17: 416–429.

    Article  Google Scholar 

  • Graham RL, Lawler EL, Lenstra JK and Rinnooy Kan AHG (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann Disc Math 5: 287–326.

    Article  Google Scholar 

  • Grötschel M (1980). On the symmetric travelling salesman problem: Solution of a 120-city problem. Math Progr Study 12: 61–77.

    Article  Google Scholar 

  • Gupta JND (1971). An improved combinatorial algorithm for the flowshop-scheduling problem. Opns Res 19: 1753–1758.

    Article  Google Scholar 

  • Hall LA (1998). Approximability of flow shop scheduling. Math Progr B 82: 175–190.

    Google Scholar 

  • Hall LA, Schulz A, Shmoys DB and Wein J (1997). Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Math Opns Res 22: 513–544.

    Article  Google Scholar 

  • Hall NG and Posner ME (1991). Earliness–tardiness scheduling problems, I: Weighted deviation of completion times about a common due date. Opns Res 39: 836–846.

    Article  Google Scholar 

  • Hall NG and Potts CN (1993). Supply chain scheduling: Batching and delivery. Opns Res 51: 566–584.

    Article  Google Scholar 

  • Hall NG, Kubiak W and Sethi SP (1991). Earliness–tardiness scheduling problems, II: Deviation of completion times about a restrictive common due date. Opns Res 39: 836–846.

    Article  Google Scholar 

  • Hariri AMA and Potts CN (1983). An algorithm for single machine sequencing with release dates to minimize total weighted completion time. Disc Appl Math 5: 99–109.

    Article  Google Scholar 

  • Held M and Karp RM (1971). The traveling-salesman problem and minimum spanning trees: Part II. Math Progr 1: 6–25.

    Article  Google Scholar 

  • Held M, Wolfe P and Crowder HP (1974). Validation of subgradient optimization. Math Progr 6: 62–88.

    Article  Google Scholar 

  • Hochbaum DS and Landy D (1997). Scheduling semiconductor burn-in operations to minimize total flowtime. Opns Res 45: 874–885.

    Article  Google Scholar 

  • Hochbaum DS and Shmoys DB (1987). Using dual approximation algorithms for scheduling problems: Theoretical and practical results. J Assoc Comput Mach 34: 144–162.

    Article  Google Scholar 

  • Hochbaum DS and Shmoys DB (1988). A polynomial approximation scheme for machine scheduling on uniform processors: Using the dual approximating approach. SIAM J Comput 17: 539–551.

    Article  Google Scholar 

  • Hoogeveen JA and Van de Velde SL (1991). Scheduling around a small common due date. Eur J Opl Res 55: 237–242.

    Article  Google Scholar 

  • Hoogeveen JA and Vestjens APA (1996). Optimal online algorithms for single-machine scheduling. In: Cunningham WH, McCormick ST and Queyranne M (eds). Integer Programming and Combinatorial Optimization :Lecture Notes in Computer Science Vol. 1084. Springer: Berlin, pp. 404–414.

    Chapter  Google Scholar 

  • Hoogeveen JA, Oosterhout H and Van de Velde SL (1994). New lower and upper bounds for scheduling around a small common due date. Opns Res 42: 102–110.

    Article  Google Scholar 

  • Hoogeveen JA, Lenstra JK and Van de Velde SL (1997). Sequencing and scheduling. In: Dell'Amico M, Maffioli F and Martello S (eds). Annotated Bibliographies in Combinatorial Optimization. Wiley: Chichester, pp. 181–197.

    Google Scholar 

  • Hoogeveen H, Schuurman P and Woeginger GJ (2001). Non-approximability results for scheduling problems with minsum criteria. INFORMS J Comput 13: 157–168.

    Article  Google Scholar 

  • Horn WA (1974). Some simple scheduling algorithms. Nav Res Logist Quart 21: 177–185.

    Article  Google Scholar 

  • Horowitz H and Sahni S (1976). Exact and approximate algorithms for scheduling nonidentical processors. J Assoc Comput Mach 23: 317–327.

    Article  Google Scholar 

  • Ibarra OH and Kim CE (1975). Fast approximation algorithms for the knapsack and sum of subset problems. J Assoc Comput Mach 22: 463–468.

    Article  Google Scholar 

  • Ignall E and Schrage L (1965). Application of the branch and bound technique to some flow-shop scheduling problems. Opns Res 13: 400–412.

    Article  Google Scholar 

  • Jackson JR (1955). Scheduling a production line to minimize maximum tardiness. Research Report 43, Management Science Research Project, University of California, Los Angeles, CA.

  • Jackson JR (1956). An extension of Johnson's result on job lot scheduling. Nav Res Logist Quart 3: 201–203.

    Article  Google Scholar 

  • Johnson SM (1954). Optimal two- and three-stage production schedules with setup times included. Nav Res Logist Quart 1: 61–68.

    Article  Google Scholar 

  • Karmarkar N (1984). A new polynomial-time algorithm for linear programming. In: Proceedings of the 16th Annual ACM Symposium on Theory of Computing. The Association for Computing Machinery: New York, pp. 302–311.

    Google Scholar 

  • Karp RM (1972). Reducibility among combinatorial problems. In: Miller RE and Thatcher JM (eds). Complexity of Computer Computations. Plenum Press: New York, pp. 85–103.

    Chapter  Google Scholar 

  • Khachiyan LG (1979). A polynomial algorithm in linear programming. Sov Math Doklady 20: 191–194.

    Google Scholar 

  • Kirkpatrick S, Gelatt CD Jr, and Vecchi MP (1983). Optimization by simulated annealing. Science 220: 671–680.

    Article  Google Scholar 

  • Kleinau U (1993). Two-machine shop scheduling problems with batch processing. Math Comput Model 17: 55–66.

    Article  Google Scholar 

  • Kononov A and Sviridenko M (2002). A linear time approximation scheme for makespan minimization in an open shop with release dates. Opns Res Lett 30: 276–280.

    Article  Google Scholar 

  • Kovalyov MY and Kubiak W (1999). A fully polynomial approximation scheme for weighted earliness–tardiness problem. Opns Res 47: 757–761.

    Article  Google Scholar 

  • Kubzin MA and Strusevich VA (2006). Planning machine maintenance in two-machine shop scheduling. Opns Res 54: 789–800.

    Article  Google Scholar 

  • Kubzin MA, Potts CN and Strusevich VA (2009). Approximation results for flow shop scheduling problems with machine availability constraints. Comput Opns Res 36: 379–390.

    Article  Google Scholar 

  • Labetoulle J, Lawler EL, Lenstra JK and Rinnooy Kan AHG (1984). Preemptive scheduling of uniform machines subject to release dates. In: Pulleyblank WR (ed). Progress in Combinatorial Optimization. Academic Press: New York, pp. 245–261.

    Chapter  Google Scholar 

  • Lageweg BJ, Lenstra JK and Rinnooy Kan AHG (1978). A general bounding scheme for the permutation flow-shop problem. Opns Res 26: 53–67.

    Article  Google Scholar 

  • Lageweg BJ, Lawler EL, Lenstra JK and Rinnooy Kan AHG (1982). Computer-aided complexity classification of combinatorial problems. Comm ACM 25: 817–822.

    Article  Google Scholar 

  • Land AH and Doig A (1960). An automatic method for solving discrete programming problems. Econometrica 28: 497–520.

    Article  Google Scholar 

  • Lawler EL (1964). On scheduling problems with deferral costs. Mngt Sci 11: 280–288.

    Article  Google Scholar 

  • Lawler EL (1977). A ‘pseudopolynomial' algorithm for sequencing jobs to minimize total tardiness. Ann Disc Math 1: 331–342.

    Article  Google Scholar 

  • Lawler EL (1978). Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Ann Disc Math 2: 75–90.

    Article  Google Scholar 

  • Lawler EL (1991). Old stories. In: Lenstra JK, Rinnooy Kan AHG and Schrijver A (eds). History of Mathematical Programming. A Collection of Personal Reminiscences. CWI and North-Holland: Amsterdam, pp. 97–106.

    Google Scholar 

  • Lawler EL and Labetoulle J (1978). On preemptive scheduling of unrelated parallel processors by linear programming. J Assoc Comput Mach 25: 612–619.

    Article  Google Scholar 

  • Lawler EL and Moore JM (1969). A functional equation and its application to resource allocation and sequencing problems. Mngt Sci 16: 77–84.

    Article  Google Scholar 

  • Lawler EL, Lenstra JK and Rinnooy Kan AHG (1982a). Recent developments in deterministic sequencing and scheduling: A survey. In: Dempster MAH, Lenstra JK and Rinnooy Kan AHG (eds). Deterministic and Stochastic Scheduling. Reidel: Dordrecht, pp. 35–73.

    Chapter  Google Scholar 

  • Lawler EL, Luby MG and Vazirani VV (1982b). Scheduling open shops with parallel machines. Opns Res Lett 82: 161–164.

    Article  Google Scholar 

  • Lawler EL, Lenstra JK, Rinnooy Kan AHG and Shmoys DB (1993). Sequencing and scheduling: Algorithms and complexity. In: Graves S, Rinnooy Kan AHG and Zipkin P (eds). Handbooks in Operations Research and Management Science, Volume 4, Logistics of Production and Inventory. North Holland: Amsterdam, pp. 445–522.

    Google Scholar 

  • Lee C-Y (1996). Machine scheduling with an availability constraint. J Global Opti 9: 395–416.

    Article  Google Scholar 

  • Lee C-Y (2004). Machine scheduling with availability constraints. In: Leung JY-T (ed). Handbook of Scheduling: Algorithms, Models and Performance Analysis. Chapman & Hall/CRC: Boca Raton, FL pp 22-1–22-13.

    Google Scholar 

  • Lee C-Y and Chen Z-L (2000). Scheduling jobs and maintenance activities on parallel machines. Nav Res Logist 47: 145–165.

    Article  Google Scholar 

  • Lee C-Y and Chen Z-L (2001). Machine scheduling with transportation considerations. J Schedul 4: 3–24.

    Article  Google Scholar 

  • Lee C-Y and Leon J (2001). Machine scheduling with a rate-modifying activity. Eur J Opl Res 128: 119–128.

    Article  Google Scholar 

  • Lenstra JK (1998). The mystical power of twoness: In memoriam Eugene L. Lawler. J Schedul 1: 3–14.

    Article  Google Scholar 

  • Lenstra JK and Rinnooy Kan AHG (1978). Complexity of scheduling under precedence constraints. Opns Res 26: 22–35.

    Article  Google Scholar 

  • Lenstra JK, Rinnooy Kan AHG and Brucker P (1977). Complexity of machine scheduling problems. Ann Disc Math 1: 343–362.

    Article  Google Scholar 

  • Lenstra JK, Shmoys DB and Tardos É (1990). Approximation algorithms for scheduling unrelated parallel machines. Math Progr. 46: 259–271.

    Article  Google Scholar 

  • Leung JYT (ed). (2004). Handbook of Scheduling: Algorithms, Models and Performance Analysis. Chapman & Hall/CRC, Boca Raton, FL.

  • Lin S (1965). Computer solutions of the traveling salesman problem. Bell Syst Techn J 44: 2245–2269.

    Article  Google Scholar 

  • Liu Z and Yu W (2000). Scheduling groups of jobs in two-machine open shop. J East China Univ Sci Technol 26: 665–669 (in Chinese).

    Google Scholar 

  • Lomnicki ZA (1965). A ‘branch-and-bound' algorithm for the exact solution of the three-machine scheduling problem. Opl Res Quart 16: 89–100.

    Article  Google Scholar 

  • Martel CU (1982). Preemptive scheduling with release times, deadlines and due times. J Assoc Comput Mach 29: 812–829.

    Article  Google Scholar 

  • Matsuo H, Suh CJ and Sullivan RS (1988). A controlled search simulated annealing method for the general problem. Working paper 03-04-88, Graduate School of Business, University of Texas at Austin, TX.

  • Matsuo H, Suh CJ and Sullivan RS (1989). A controlled search simulated annealing method for the single machine weighted tardiness problem. Ann Opns Res 21: 85–108.

    Article  Google Scholar 

  • McMahon GB (1969). Optimal production schedules for flowshops. CORS J 7: 141–151.

    Google Scholar 

  • McMahon GB and Burton PG (1967). Flow-shop scheduling with the branch-and-bound method. Opns Res 15: 473–481.

    Article  Google Scholar 

  • McMahon GB and Florian M (1975). On scheduling with ready times and due dates to minimize maximum lateness. Opns Res 23: 475–482.

    Article  Google Scholar 

  • McNaughton R (1959). Scheduling with deadlines and loss functions. Mngt Sci 6: 1–12.

    Article  Google Scholar 

  • Miliotis P (1976). Integer programming approaches to the travelling salesman problem. Math Progr 10: 367–378.

    Article  Google Scholar 

  • Miliotis P (1978). Using cutting planes to solve the symmetric travelling salesman problem. Math Progr 15: 177–188.

    Article  Google Scholar 

  • Monma CL and Potts CN (1989). On the complexity of scheduling with batch setup times. Opns Res 37: 798–804.

    Article  Google Scholar 

  • Monma CL and Rinnooy Kan AHG (1983). A concise survey of efficiently solvable cases of the permutation flow-shop problem. RAIRO Rech Oper 17: 105–119.

    Google Scholar 

  • Monma CL and Sidney JB (1979). Sequencing with series-parallel precedence constraints. Math Opns Res 4: 215–234.

    Article  Google Scholar 

  • Moore JM (1968). An n job, one machine sequencing algorithm for minimizing the number of late jobs. Mngt Sci 15: 102–109.

    Article  Google Scholar 

  • Muth JF and Thompson GL (eds). (1963). Industrial Scheduling. Prentice-Hall, Englewood Cliffs, NJ.

  • Nabeshima I (1961). The order of n items processed on m machines: I. J Opns Res Soc Japan 3: 170–175.

    Google Scholar 

  • Nabeshima I (1967). On the bound of makespans and its application in M machine scheduling problem. J Opns Res Soc Japan 9: 98–136.

    Google Scholar 

  • Németi L (1964). Das Reihenfolgeproblem in der Fertigungsprogrammierung und Linear-planung mit logischen Bedingungen. Mathematica (Cluj) 6: 87–99.

    Google Scholar 

  • Ng CT and Kovalyov MY (2004). An FPTAS for scheduling a two-machine flowshop with one unavailability interval. Nav Res Logist 51: 307–315.

    Article  Google Scholar 

  • Nicholson TAJ (1967). A sequential method for discrete optimization problems and its application to the assignment, travelling salesman, and three machine scheduling problems. J Inst Math Appl 3: 362–375.

    Article  Google Scholar 

  • Nowicki E and Smutnicki C (1996a). A fast taboo search algorithm for the job shop problem. Mngt Sci 42: 797–813.

    Article  Google Scholar 

  • Nowicki E and Smutnicki C (1996b). A fast tabu search algorithm for the permutation flow-shop problem. Eur J Opl Res 91: 160–175.

    Article  Google Scholar 

  • Ogbu FA and Smith DK (1990). The application of the simulated annealing algorithm to the solution of the n|m|Cmax flowshop problem. Comput Opns Res 17: 243–253.

    Article  Google Scholar 

  • Osman IH and Potts CN (1989). Simulated annealing for permutation flow-shop scheduling. Omega 17: 551–557.

    Article  Google Scholar 

  • Padberg MW and Hong S (1980). On the symmetric travelling salesman problem: A computational study. Math Progr Study 12: 78–107.

    Article  Google Scholar 

  • Piehler J (1960). Ein Beitrag zum Reihenfolge problem. Unternehmensforschung 4: 138–142.

    Google Scholar 

  • Pinedo M (1995). Scheduling: Theory, Algorithms, and Systems . Prentice Hall: Englewood Cliffs, NJ.

    Google Scholar 

  • Pinedo M and Schrage L (1982). Stochastic shop scheduling: A survey. In: Dempster MAH, Lenstra JK and Rinnooy Kan AHG (eds). Deterministic and Stochastic Scheduling. Riedel: Dordrecht, pp. 181–196.

    Chapter  Google Scholar 

  • Potts CN (1974). The job-machine scheduling problem. PhD thesis, University of Birmingham, UK.

  • Potts CN (1980). An adaptive branching rule for the permutation flow-shop problem. Eur J Opl Res 5: 19–25.

    Article  Google Scholar 

  • Potts CN (1985). Analysis of a linear programming heuristic for scheduling unrelated parallel machines. Disc Appl Math 10: 155–164.

    Article  Google Scholar 

  • Potts CN and Kovalyov MY (2000). Scheduling with batching: A review. Eur J Opl Res 120: 228–249.

    Article  Google Scholar 

  • Potts CN and Van Wassenhove LN (1982). A decomposition algorithm for the single machine total tardiness problem. Opns Res Lett 1: 177–181.

    Article  Google Scholar 

  • Potts CN and Van Wassenhove LN (1983). An algorithm for single machine sequencing with deadlines to minimize total weighted completion time. Eur J Opl Res 12: 379–387.

    Article  Google Scholar 

  • Potts CN and Van Wassenhove LN (1985). A branch and bound algorithm for the total weighted tatrdiness problem. Opns Res 33: 363–377.

    Article  Google Scholar 

  • Potts CN and Van Wassenhove LN (1991). Single machine tardiness sequencing heuristics. IIE Trans 23: 346–354.

    Article  Google Scholar 

  • Potts CN and Van Wassenhove LN (1992). Integrating scheduling with batching and lot-sizing: A review of algorithms and complexity. J Opl Res Soc 43: 395–406.

    Article  Google Scholar 

  • Potts CN, Strusevich VA and Tautenhahn T (2001). Scheduling batches with simultaneous job processing for two-machine shop problems. J Schedul 4: 25–51.

    Article  Google Scholar 

  • Pruhs K, Sgall J and Torng E (2004). Online scheduling. In: Leung JY-T (ed). Handbook of Scheduling: Algorithms, Models and Performance Analysis. Chapman & Hall/CRC: Boca Raton, FL, pp. 15-1–15-43.

    Google Scholar 

  • Queyranne M and Wang Y (1991). Single machine scheduling polyhedra with precedence constraints. Math Opns Res 16: 1–20.

    Article  Google Scholar 

  • Reeves CR (1995). A genetic algorithm for flowshop sequencing. Comput Opns Res 22: 5–13.

    Article  Google Scholar 

  • Reeves CR (1999). Landscapes, operators and heuristic search. Ann Opns Res 86: 473–490.

    Article  Google Scholar 

  • Rinnooy Kan AHG, Lageweg BJ and Lenstra JK (1975). Minimizing total costs in one-machine scheduling. Opns Res 23: 908–927.

    Article  Google Scholar 

  • Rothkopf MH (1966). Scheduling independent tasks on parallel processors. Mngt Sci 12: 437–447.

    Article  Google Scholar 

  • Roy B and Sussman B (1964). Les problemes d'ordonnancement avec contraintes disjonctives. Note DS No. 9 bis, SEMA, Montrouge.

  • Sahni S (1976). Algorithms for scheduling independent tasks. J Assoc Comput Mach 23: 116–127.

    Article  Google Scholar 

  • Sanlaville E and Schmidt G (1998). Machine scheduling with availability constraints. Acta Informat 5: 795–811.

    Article  Google Scholar 

  • Schmidt G (2000). Scheduling with limited machine availability. Eur J Opl Res 121: 1–15.

    Article  Google Scholar 

  • Schrage L (1968). A proof of the shortest remaining processing time processing discipline. Opns Res 16: 687–690.

    Article  Google Scholar 

  • Schrage L (1970a). Solving resource-constrained network problems by implicit enumeration—Nonpreemptive case. Opns Res 18: 253–278.

    Article  Google Scholar 

  • Schrage L (1970b). A bound based on the equivalence of min-max-completion time and min-max-lateness scheduling objectives. Report 7042, Department of Economics and Graduate School of Business, Chicago, IL.

  • Schuurman P and Vredeveld T (2001). Performance guarantees of local search for multiprocessor scheduling. In: Aardal KI and Gerards AMH (eds). Integer Programming and Combinatorial Optimization :Lecture Notes in Computer Science Vol. 2081. Springer: Berlin, pp. 370–382.

    Chapter  Google Scholar 

  • Schuurman P and Woeginger GJ (1999). Polynomial time approximation algorithms for machine scheduling: Ten open problems. J Schedul 2: 203–213.

    Article  Google Scholar 

  • Sevastianov SV (1994). On some geometric methods in scheduling theory: A survey. Disc Appl Math 55: 59–82.

    Article  Google Scholar 

  • Sevastianov SV (1995). Vector summation in Banach space and polynomial algorithms for flow shops and open shops. Math Opns Res 20: 90–103.

    Article  Google Scholar 

  • Sevastianov SV and Woeginger GJ (1998). Makespan minimization in open shops: A polynomial time approximation scheme. Math Progr B 82: 191–198.

    Google Scholar 

  • Shwimer J (1972). On the N-job one-machine, sequence-independent scheduling problem with tardiness penalties: A branch-bound solution. Mngt Sci 18: B301–B313.

    Article  Google Scholar 

  • Sitters RA (2005). Complexity of preemptive minsum scheduling on unrelated parallel machines. J Algorithms 57: 37–48.

    Article  Google Scholar 

  • Skutella M (2001). Convex quadratic and semidefinite programming relaxations in scheduling. J Assoc Comput Mach 48: 206–242.

    Article  Google Scholar 

  • Smith WE (1956). Various optimizers for single-stage production. Nav Res Logist Quart 3: 59–66.

    Article  Google Scholar 

  • Smith SP (1992). Experiment on using genetic algorithms to learn scheduling heuristics. In: Biswas G (ed). Proceedings of SPIE, Volume 1707, Applications of Artificial Intelligence X: Knowledge-Based Systems. The International Society for Optical Engineering: Bellingham, WA, pp. 378–386.

    Chapter  Google Scholar 

  • Smith RD and Dudek RA (1969). Errata. Opns Res 17: 756.

    Article  Google Scholar 

  • Storer RH, Wu SD and Vaccari R (1992). New search spaces for sequencing problems with application to job shop scheduling. Mngt Sci 38: 1495–1509.

    Article  Google Scholar 

  • Strusevich VA (2000). Group technology approach to the open shop scheduling problem with batch setup times. Opns Res Lett 26: 181–192.

    Article  Google Scholar 

  • Sturm LBJM (1970). A simple optimality proof of Moore's sequencing algorithm. Mngt Sci 17: 116–118.

    Article  Google Scholar 

  • Szwarc W (1968). On some sequencing problems. Nav Res Logist Quart 15: 127–155.

    Article  Google Scholar 

  • Szwarc W (1971). Elimination methods in the m × n sequencing problem. Nav Res Logist Quart 18: 295–305.

    Article  Google Scholar 

  • Szwarc W (1973). Optimal elimination methods in the m × n sequencing problem. Opns Res 21: 1250–1259.

    Article  Google Scholar 

  • Taillard E (1990). Some efficient heuristic methods for the flow shop sequencing problem. Eur J Opl Res 47: 65–74.

    Article  Google Scholar 

  • Taillard E (1994). Parallel taboo search techniques for the job shop scheduling problem. ORSA J Comput 6: 108–117.

    Article  Google Scholar 

  • Tanaev VS, Gordon VS and Shafransky (1984). Scheduling Theory. Single-Stage Systems (in Russian). Nauka: Moscow; English translation by Kluwer: Dordrecht, 1994.

  • Tanaev VS, Gordon VS and Shafransky (1989). Scheduling Theory. Multi-Stage System (in Russian). Nauka: Moscow; English translation by Kluwer: Dordrecht, 1994.

  • Van den Akker JM, Hoogeveen JA and Van de Velde SL (1999). Parallel machine scheduling by column generation. Opns Res 47: 862–872.

    Article  Google Scholar 

  • Van Wassenhove LN (1979). Special purpose algorithms for one-machine sequencing problems with single and composite objectives. PhD thesis, Katholieke Universiteit Leuven, Belgium.

  • Widmer M and Hertz A (1989). A new heuristic method for the flow shop sequencing problem. Eur J Opl Res 41: 186–193.

    Article  Google Scholar 

  • Wilkerson L and Irwin J (1971). An improved method for scheduling independent tasks. AIIE Trans 33: 239–245.

    Article  Google Scholar 

  • Williamson DP, Hall LA, Hoogeveen JA, Hurkens CAJ, Lenstra JK, Sevastianov SV and Shmoys DB (1997). Short shop schedules. Opns Res 45: 288–294.

    Article  Google Scholar 

  • Yamada T and Nakano R (1992). A genetic algorithm applicable to large-scale job-shop problems. In: Männer R and Manderick B (eds). Parallel Problem Solving from Nature 2. North Holland: Amsterdam, pp. 281–290.

    Google Scholar 

  • Yamada T, Rosen BE and Nakano R (1994). A simulated annealing approach to job shop scheduling using critical block transition operators. In: Proceedings of the IEEE International Conference on Neural Networks, ICNN'94. IEEE: New York, pp. 4687–4692.

    Google Scholar 

Download references

Acknowledgements

The authors are grateful to NG Hall and ME Posner for some useful suggestions on the content of some sections of this paper.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to C N Potts.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Potts, C., Strusevich, V. Fifty years of scheduling: a survey of milestones. J Oper Res Soc 60 (Suppl 1), S41–S68 (2009). https://doi.org/10.1057/jors.2009.2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2009.2

Keywords

Navigation