Summary
In this paper, we survey the literature on heuristic priority rule-based job shop scheduling. Priority rules have been intensively investigated over the last 30 years by means of simulation experiments. They are also used in Shop Floor Control software systems. We present a classification, a characterization, and an evaluation of elementary priority rules. Some priority rule-related model extensions are discussed.
Zusammenfassung
In diesem Beitrag wird ein Überblick über heuristische, prioritätsregelgestützte Auftragsreihenfolgeplanung gegeben. Prioritätsregeln sind in den letzten 30 Jahren eingehend anhand von Simulations-Experimenten untersucht worden. Sie haben ebenso in Programmsysteme zur Produktionsplanung und-steuerung Eingang gefunden. Der Beitrag bemüht sich um eine Klassifizierung, Charakterisierung und Beurteilung von elementaren Prioritätsregeln. Abschließend werden einige prioritätsregelrelevante Modellerweiterungen angeschnitten.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Adam D (1987) Ansätze zu einem integrierten Konzept der Fertigungssteuerung bei Werkstattfertigung. In: Adam D (Hrsg) Neuere Entwicklungen in der Produktions- und Investitionspolitik. Festschrift zum 60. Geburtstag von Herbert Jacob. Gabler, Wiesbaden, pp 17–52
Adam D (1988) Die Eignung der belastungsorientierten Auftragsfreigabe fur die Steuerung von Fertigungsprozessen mit diskontinuierlichem Materialfluß. Z Betriebsw 58:98–115
Adam N, Bertrand JWM, Surkis J (1984) Effective priority rules related to due date performance in multi-level assembly jobs. Paper presented at the TIMS XXVI meeting, Copenhagen, TB 11.1
Adam N, Surkis J (1980) Priority update intervals and anomalies in dynamic ratio type job shop scheduling rules. Manag Sci 26:1227–1237
Aggarwal SC, McCarl BA (1974) The development and evaluation of a cost-based composite scheduling rule. Nav Res Log Q 21:155–169
Aggarwal SC, Wyman FP, McCarl BA (1973) An investigation of a cost-based rule for job-shop scheduling. Int J Prod Res 11:247–261
Arumugam V, Ramani S (1980) Evaluation of value time sequencing rules in a real world job shop. J Op Res Soc 31: 895–904
Baker CT, Dzielinsky BP (1960) Simulation of a simplified job shop. Manag Sci 6:311–323
Baker KR (1968) Priority dispatching in the single channel queue with sequence-dependent setups. J Ind Eng:203–206
Baker KR (1974) Introduction to sequencing and scheduling. Wiley, New York
Baker KR (1984) Sequencing rules and due-date assignments in a job shop. Manag Sci 30:1093–1104
Baker KR, Bertrand JWM (1981) An investigation of duedate assignment rules with constrained tightness. J Op Manag 1:109–120
Baker KR, Bertrand JWM (1982) A dynamic priority rule for sequencing against due dates. J Op Manag 3:37–42
Baker KR, Kanet JJ (1983) Job shop scheduling with modified due dates. J Op Manag 4:11–22
Baker KR, Kanet JJ (1984) Improved decision rules in a combined system for minimizing job tardiness. Int J Prod Res 22:917–921
Berg CC (1979) Prioritätsregeln in der Reihenfolgeplanung. In: Kern W (Hrsg) HWProd, Poeschel, Stuttgart, pp 1425–1433
Berr U, Tangermann HP (1976) Einfluß von Prioritätsregeln auf die Kapazitätsterminierung der Werkstattfertigung. Wt-Z Ind Fertig 66:7–12
Berry WL, Finley RA (1976) Critical ratio scheduling with queue waiting information: an experimental analysis. AIIE-Transact 8:161–168
Berry WL, Rao V (1975) Critical ratio scheduling: an experimental analysis. Manag Sci 22:192–201
Bertrand JWM (1983) The effect of workload dependent due-dates on job shop performance. Manag Sci 29:799–816
Biendl P (1984) Ablaufsteuerung von Montagefertigungen. Haupt, Bern Stuttgart
Biggs JR (1979) Heuristic lot-sizing and sequencing rules in a multistage production-inventory system. Dec Sci 10: 96–115
Biggs JR (1985) Priority rules for shop floor control in a material requirements planning system under various levels of capacity. Int J Prod Res 23:33–46
Blackstone JH Jr, Phillips DT, Hogg GL (1982) A state-of-the-art survey of dispatching rules for manufacturing job shop operations. Int J Prod Res 20:27–45
Brown RG (1968) Simulations to explore alternative sequencing rules. Nav Res Log Q 15:281–286
Browne J, Davies BJ (1984) The design and validation of a digital simulation model for job shop control decision making. Int J Prod Res 22:335–357
Bulkin MH, Colley JL, Steinhoff HW (1967) Load forecasting, priority sequencing, and simulation in a job shop control system. Manag Sci 13:B29-B51
Bunnag P, Smith SB (1985) A multifactor priority rule for jobshop scheduling using computer search. IIE-Transact 17:141–146
Buzi K (1971) Die Simulation optimaler Prioritätsregeln für die Ablaufplanung in der Werkstattfertigung. Westdeutscher Verlag, Köln Opladen
Caroll DC (1965) Heuristic sequencing of single and multiple component jobs. PhD thesis, MIT, Cambridge/Mass
Cheng TCE (1986) Optimal due-date assignment in a job shop. Int J Prod Res 24:503–515
Colley JL Jr (1968) Principles for scheduling job shops. Syst Proced J 19, No 4
Conway RW (1965) Priority dispatching and work-in-process inventory in a job shop. J Ind Eng 16:123–130
Conway RW (1965) Priority dispatching and job lateness in a job shop. J Ind Eng 16:228–237
Conway RW, Maxwell WL (1962) Network dispatching by the shortest operation discipline. Oper Res 10:51–73
Conway RW, Maxwell WL, Miller LW (1967) Theory of scheduling. Addison-Wesley, Reading/Mass
Conway RW, Maxwell WL, Oldziey JW (1966) Sequencing against due-dates. In: Hertz DB, Melèse J (eds) Proceedings of the Fourth International Conference on Operational Research. Wiley, New York, pp 599–617
Day JE, Hottenstein MP (1970) Review of sequencing research. Nav Res Log Q 17:11–39
Deane RH, Moodie CL (1972) A dispatching methodology for balancing workload assignments in a job shop production facility. AIIE-Transact 4:277–283
Dörken W (1973) Simulationsmodelle und ihre Anwendung bei der Analyse von Prioritätsregeln zur Maschinenbelegungsplanung. Arbeitsvorb 10:89–95, 115–122
Dornia M (1976) Aufbau- und ablauforientierte Untersuchungen an einem Simulationsmodell der Mehrstellenbedienung. Dissertation, Köln
Eilon S (1973) Research note: The job shop simulation programme. Int J Prod Res 11:299–300
Eilon S (1979) Production scheduling. In: Haley KB (ed) OR '78. North-Holland, Amsterdam, pp 237–266
Eilon S, Chowdhury IG (1976) Due dates in job shop scheduling. Int J Prod Res 14:223–237
Eilon S, Chowdhury IG, Serghiou SS (1975) Experiments with the SI rules in job-shop scheduling. Simulation 24: 45–48
Eilon S, Cotterill DJ (1968) A modified SI rule in job shop scheduling. Int J Prod Res 7:135–145
Eilon S, Hodgson RM (1967) Job shops scheduling with due dates. Int J Prod Res 6:1–13
Ellinger T (1976) Reihenfolgeplanung. In: Grochla E, Wittmann W (eds) HWB 4. Aufl, Poeschel, Stuttgart, pp 3412–3420
Ellinger T, Schmitz P, Goldbecker H, Haupt R, Oellers B (1978) Simulationssystem für Reihenfolgeprobleme der industriellen Fertigung. Rationalisierung 29:17–21, 43–45
Elmaghraby SE (ed) (1973) Symposium on the theory of scheduling and its applications. Springer, Berlin Heidelberg New York
Elvers DA (1973) Job shop dispatching using various due date setting criteria. Prod Inv Manag 14:62–69
Elvers DA (1974) The sensitivity of the relative effectiveness ob job shop dispatching rules with respect to various arrival distributions. AIIE-Transact 6:41–49
Elvers DA, Taube LR (1983) Deterministic/stochastic assumptions in job shops. Eu J Oper Res 14:89–94
Elvers DA, Taube LR (1983) Time completion for various dispatching rules in job shops. Omega 11:81–89
Fabrycky WJ, Shamblin JE (1966) A probability based sequencing algorithm. J Ind Eng 17:308–312
Farn CK, Muhlemann AP (1979) The dynamic aspects of a production scheduling problem. Int J Prod Res 17:15–21
Fischer H, Thompson GL (1963) Probabilistic learning combinations of local job shop scheduling rules. In: Muth JF, Thompson GL (eds) Industrial scheduling, Prentice-Hall, Englewood Cliffs, chap 15
Fleischmann B (1987) Operations-Research-Modelle und -Verfahren in der Produktionsplanung (Übersichtsvortrag). In: Isermann H et al. (eds) Operations Research Proceedings 1986. Springer, Berlin Heidelberg New York, pp 278–285
French S (1982) Sequencing and scheduling. An introduction to the mathematics of the job-shop. Horwood, Chichester
Gere WS (1966) Heuristics in job shop scheduling. Manag Sci 13:167–190
Goodwin JS, Goodwin JC Jr (1982) Operating policies for scheduling assembled products. Dec Sci 13:585–603
Goodwin JS, Weeks JK (1986) Evaluating scheduling policies in a multi-level assembly system. Int J Prod Res 24:247–257
O'Grady PJ, Harrison C (1985) A general search sequencing rule for job shop sequencing. Int J Prod Res 23:961–973
Gräßler D (1968) Der Einfluß von Auftragsdaten und Entscheidungsregeln auf die Ablaufplanung von Fertigungsstraßen. Dissertation, TH Aachen
Graves SC (1977) A note on “Critical ratio scheduling: an experimental analysis” (Note). Manag Sci 23:1358–1359
Graves SC (1981) A review of production scheduling. Oper Res 29:646–675
Green GI, Appel LB (1981) An empirical analysis of job shop dispatch rule selection. J Oper Manag 1:197–203
Hauk W (1972) Beitrag zur Lösung des Reihenfolgeproblems bei der Auftragsplanung. Z Wirtsch Fert 67:45–49
Hauk W (1973) Einplanung von Produktionsaufträgen nach Prioritätsregeln. Eine Untersuchung von Prioritätsregeln mit Hilfe der Simulation. Beuth, Berlin Köln Frankfurt
Haupt R (1977) Reihenfolgeplanung im Sondermaschinenbau. Gabler, Wiesbaden
Haupt R (1978) Simulationsuntersuchungen zur Reihenfolgeplanung unter dem Einfluß von Vereinheitlichungs-Elementen in der Produktion. In: Brockhoff K et al. (eds) Proceedings in Operations Research 7. Physica, Würzburg Wien, pp 247–256
Haupt R (1987) Produktionstheorie und Ablaufmanagement. Zeitvariable Faktoreinsätze und ablaufbezogene Dispositionen in Produktionstheorie- und -planungs-Modellen. Poeschel, Stuttgart
Hershauer JC, Ebert RJ (1975) Search and simulation selection of a job shop sequencing rule. Manag Sci 21:833–843
Hoffmann TR, Scudder GD (1983) Priority scheduling with cost considerations. Int J Prod Res 21:881–889
Hollier RH (1986) A simulation study of sequencing in batch production. Oper Res Q 19:389–407
Huang PY (1984) A comparative study of priority dispatching rules in a hybrid assembly job shop. Int J Prod Res 22:375–387
Jackson JR (1957) Simulation research on job shop production. Nav Res Log Q 4:287–295
Jones CH (1973) An economic evaluation of job shop dispatching rules. Manag Sci 20:293–307
Kanet JJ (1982) On anomalies in dynamic ratio type scheduling rules: a clarifying analysis. Manag Sci 28: 1337–1341
Kanet JJ, Hayya JC (1982) Priority dispatching with operation due-dates in a job shop. J Oper Manag 2:155–163
Kettner H, Bechte W (1981) Neue Wege der Fertigungssteuerung durch belastungsorientierte Auftragsfreigabe. VDI-Z 123:459–465
Knolmayer G, Holdhof J (1986) BORA versus DORA: Ein Vergleich zweier Terminplanungsverfahren. Arbeitsvorbereitung 23:163–165
Le Grande E (1963) The development of a factory simulation system using actual operating data. Manag Tech 3: 1–19
Maxwell WL (1969) Priority dispatching and assembly operations in a job shop. The RAND Corp Memorandum RM-5370-PR, Santa Monica/Cal
Maxwell WL, Mehra M (1968) Multiple-factor rules for sequencing with assembly constraints. Nav Res Log Q 15:241–254
Mellor P (1966) A review of job shop scheduling. Oper Res Q 17:161–171
Miller LW, Ginsberg AS, Maxwell WL (1975) An experimental investigation of priority dispatching in a simple assembly shop. In: Geisler MA (ed) Logistics, TIMS Studies in the Management Sciences, vol 1. North-Holland, Amsterdam, pp 125–142
Miyazaki S (1981) Combined scheduling system for reducing job tardiness in a job shop. Int J Prod Res 19:201–211
Moodie CL, Novotny DJ (1968) Computer scheduling and control systems for discrete part production. J Ind Eng 19:336–341
Moodie CL, Roberts SD (1968) Experiments with priority dispatching rules in a parallel processor shop. Int J Prod Res 6:303–312
Moore JM, Wilson RC (1967) A review of simulation research in job shop scheduling. Prod Inv Manag 8:1–10
Mosier CT, Elvers DA, Kelly D (1984) Analysis of group technology scheduling heuristics. Int J Prod Red 22:857–875
Müller A (1987) Produktionsplanung und Pufferbildung bei Werkstattfertigung. Gabler, Wiesbaden
Müller G (1978) Job-Shop-Simulation auf dem Minicomputer: Ein Instrument zur Reihenfolge- und Terminplanung in der Textillohnveredelungsindustrie. Dissertation, Universität Zürich
Müller-Merbach H (1979) Ablaufplanung, Optimierungsmodelle zur. In: Kern W (Hrsg) HWProd, Poeschel, Stuttgart, pp 38–52
Muhlemann AP, Lockett AG, Farn CI (1982) Job shop scheduling heuristics and frequency of scheduling. Int J Prod Res 20:227–241
Nanot YR (1963) An experimental investigation and comparative evaluation of priority disciplines in job shoplike queuing networks. Manag Sci Res Proj, UCLA, Report No 87-1963
Nelson RT (1967) Labor and machine limited production systems. Manag Sci 13:648–671
New CC (1975) Job shop scheduling: is manual application of dispatching rules feasible? Oper Res Q 21:35–43
Oral M, Malouin JL (1973) Evaluation of the shortest processing time scheduling rule with truncation process. AIIE-Transact 5:357–365
Ow PS (1985) Focused scheduling in proportionate flowshops. Manag Sci 31:852–869
Pabst HJ (1985) Analyse der betriebswirtschaftlichen Effizienz einer computergestützten Fertigungssteuerung mit CAPOSS-E in einem Maschinenbauunternehmen mit Einzel- und Kleinserienfertigung. Lang, Frankfurt Bern New York
Pai AR, McRoberts KL (1971) Simulation research in interchangeable part manufacturing. Manag Sci 17:B732-B743
Panwalkar SS, Iskander W (1977) A survey of scheduling rules. Oper Res 25:45–61
Papendieck AJ (1971) Reihenfolgen und Losgroen in der Serienfertigung, untersucht an einem praxisbezogenen Simulationsmodell. Dissertation TH Braunschweig
Paulik R (1984) Kostenorientierte Reihenfolgeplanung in der Werkstattfertigung. Haupt, Bern Stuttgart
Pinto PA, Khumawala BM, Susko JA (1983) Application of a heuristic scheduling rule for a tyre testing department. J Opl Res Soc 34:243–248, 910
Putnam AO, Everdell R, Dormann GH, Cronan RR, Lindgren LH (1971) Updating critical ratio and slack time priority scheduling rules. Prod Inv Manag 12:51–73
Ragatz GL, Mabert VA (1984) A framework for the study of due date management in job shops. Int J Prod Res 22: 685–695
Reiter S (1966) A system for managing job shop production. J Business 39:371–393
Rinnooy Kan AHG (1976) Machine scheduling problems. Classification, complexity and computations. Nijhoff, Den Haag
Rochette R, Sadowski RP (1976) A statistical comparison of the performance of simple dispatching rules for a particular set of job shop. Int J Prod Res 14:63–75
Rowe AJ (1960) Toward a theory of scheduling. J Ind Eng 11:125–136
Russell RS, Taylor BW (1985) An evaluation of scheduling policies in a dual resource constrained assembly shop. IIE-Transact 17:219–232
Sägesser R (1976) Analytische und heuristische Methoden zur Lösung des Reihenfolgeproblems mit besonderer Berücksichtigung der Werkstattfertigung. Dissertation, Sankt Gallen
Sammler A (1970) Diskussion von Vorrangregeln (Prioritäten) zur Lösung des Reihenfolgeproblems in der Planung und Lenkung der Einzelteilefertigung. Fertigungstechnik Betrieb 20:408–411
Scudder GD (1984) Priority scheduling and spares stocking policies for a repair shop: the multiple failure case. Manag Sci 30:739–749
Scudder GD (1986) Scheduling and labor-assignment policies for a dual-constrained repair shop. Int J Prod Res 24:623–634
Scudder GD, Hoffmann TR (1985) An evaluation of value based dispatching rules in a flow shop. E J Oper Res 22: 310–318
Scudder GD, Hoffmann TR (1985) Composite cost-based rules for priority scheduling in a randomly routed job shop. Int J Prod Res 23:1185–1195
Sculli D (1980) Priority dispatching rules in job shops with assembly operations and random delays. Omega 8: 227–234
Sen T, Gupta SK (1984) A state-of-art survey of static scheduling research involving due dates. Omega 12:63–76
Siegel GB (1971) An investigation of job shop scheduling for jobs with assembly constraints. PhD Thesis, Cornell University, Ithaca/NY
Sprotte HG (1970) Simultane Termin- und Reihenfolgeplanung bei Mehrproduktunternehmen mit Auftragsfertigung und stochastischem Auftragseingang. Dissertation, Universität Köln
Stecke KE, Solberg JJ (1981) Loading and control policies for a flexible manufacturing system. Int J Prod Res 19: 481–490
Subramanyam S, Askin RG (1986) An expert systems approach to scheduling in flexible manufacturing systems. In: Kusiak A (ed) Flexible manufacturing systems: Methods and Studies. North-Holland, Amsterdam, pp 243–256
Tangermann HP (1973) Auftragsreihenfolgen und Losgrößen als Instrument der Fertigungsterminplanung, untersucht an einem praxisbezogenen Simulationsmodell. Dissertation, TH Braunschweig
Trilling DR (1966) Job-shop simulation of orders that are networks. J Ind Eng 17:59–71
Vepsalainen APJ, Morton TE (1987) Priority rules for job shops with weighted tardiness costs. Manag Sci 33:1035–1047
Weeks JK (1979) A simulation study of predictable duedates. Manag Sci 25:363–373
Weeks JK, Fryer JS (1976) A simulation study of operating policies in a hypothetical dual-constrained job shop. Manag Sci 22:1362–1371
Weeks JK, Fryer JS (1977) A methodology for assigning minimum cost due-dates. Manag Sci 23:872–881
Wegner N (1978) Simulation von Einplanungs- und Abfertigungsstrategien bei Werkstattfertigung. Dissertation, TU Hannover
Wiendahl HP (1987) Die belastungsorientierte Fertigungssteuerung. Oldenbourg, München Wien
Wiendahl HP, Buchmann W (1984) Realisierung alternativer Fertigungssteuerungsstrategien. VDI-Z 126:327–334
Worrall BM, Mert B (1980) Application of dynamic scheduling rules in maintenance planning and scheduling. Int J Prod Res 18:57–74
Zijm WHM (1988) Flexible Manufacturing Systems: background, examples, and models. In: Schellhaas H et al. (ed) Operations Research Proceedings 1987. Springer, Berlin Heidelberg New York, pp 142–161
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Haupt, R. A survey of priority rule-based scheduling. OR Spektrum 11, 3–16 (1989). https://doi.org/10.1007/BF01721162
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF01721162