article

Job-Shop Scheduling Theory: What Is Relevant?

Interfaces, Volume 18, Issue 4

Pages 84 - 90

https://doi.org/10.1287/inte.18.4.84

Published: 01 August 1988 Publication History

Abstract

<P>The theoretical approach of OR and AI to scheduling often is not applicable to the dynamic characteristics of the actual situation. A preliminary field study is used to illustrate that the basic theoretical approach does not represent the reality of open job-shop scheduling, and its applicability is limited to those situations that are fundamentally static and behave like the models. Better understanding and modeling of the scheduling situation is needed.</P>

References

[1]

Baker, K. R. 1974, Introduction to Sequencing and Scheduling, John Wiley and Sons, New York.

[2]

Bellman, R.; Esogbue, A. O.; and Nabeshima, I. 1982, Mathematical Aspects of Scheduling and Applications, Pergamon Press, Oxford, England.

[3]

Blackstone, J. H.; Phillips, D. X; and Hogg, G. L. 1982, "A state-of-the-art survey of dispatching rules for manufacturing job shop operations," International Journal of Production Research, Vol. 20, No. 1, pp. 27-45.

[4]

Coffman, E. G., Jr. 1976, "Introduction to deterministic scheduling theory," Computer and job-Shop Scheduling Theory, ed. E. G. Coffman, Jr., John Wiley and Sons, New York.

[5]

Conway, R. W.; Maxwell, W. L.; and Miller, L. W. 1967, Theory of Scheduling, Addison-Wesley, Reading, Massachusetts.

[6]

Eilon, S. 1979, "Production scheduling," in OR' 78, ed. K. B. Haley, North-Holland, Amsterdam, The Netherlands.

[7]

Emmons, H. 1978, "A survey of static job shop scheduling theory," working paper, Department of Operations Research, Case Western Reserve University.

[8]

Fox, M. S. 1983, "Constraint-directed search: A case study of job-shop scheduling," PhD diss., Computer Science Department, Carnegie-Mellon University.

Digital Library

[9]

French, S. 1982, Sequencing and Scheduling: An Introduction to the Mathematics of the fob-Shop, Ellis Horwood, Chichester, England.

[10]

Gere, W. S. 1966, "Heuristics in job shop scheduling," Management Science, Vol. 13, No. 3, pp. 167-190.

Digital Library

[11]

Glover, F. and McMillan, C. 1985, "The general employee scheduling problem: An effective large scale solution approach," CAAI Report 85-7, Center for Applied Artificial Intelligence, Graduate School of Business, University of Colorado.

[12]

Grant, T. J. 1986, "Lessons for O.R. from A.I.: A scheduling case study," journal of the Operational Research Society, Vol. 37, No. 1, pp. 41-57.

[13]

Graves, S. C. 1981, "A review of production scheduling," Operations Research, Vol. 29, No. 4, pp. 646-675.

Digital Library

[14]

Kim, C. 1986, "Knowledge based production planning and scheduling," working paper, The Leavey School of Business, Santa Clara University.

[15]

Lawler, E. L.; Lenstra, J. K.; and Rinnooy Kan, A. H. G. 1982, "Recent developments in deterministic sequencing and scheduling: A survey," Deterministic and Stochastic Scheduling, eds. M. A. H. Dempster, J. K. Lenstra, and A. H. G. Rinnooy Kan, D. Reidel Publishing, Dordrecht, The Netherlands.

[16]

Lipton, M. J. 1985, "The development of a real time scheduling system for automated production," Autofact '85 Conference Proceedings, Society of Manufacturing Engineers, Detroit, Michigan, pp. 13.45-13.58.

[17]

Maley, J. G.; Ruiz-Mier, S. R.; and Solberg, J. J. 1986, "Dynamic control in automated manufacturing: A knowledge integrated approach," Proceedings of the Symposium on Real-Time Optimization in Automated Manufacturing Facilities, Gaithersburg, Maryland, January 1986, eds. R. H. F. Jackson and A. W. T. Jones, NBS Special Publication 724, National Bureau of Standards, Gaithersburg, Maryland, pp. 136-144.

[18]

Mishkoff, H. C. 1985, Understanding Artificial Intelligence, Texas Instruments, Dallas, Texas.

Digital Library

[19]

Morton, T. E. 1984, "A.I. from an O.R. perspective," presentation notes, Carnegie-Mellon University.

[20]

Morton, T. E. and Smunt, T. L. 1986, "A planning and scheduling system for flexible manufacture," Flexible Manufacturing Systems: Methods and Studies, ed. A. Kusiak, North-Holland, Amsterdam, The Netherlands.

[21]

Nash, P. and Weber, R. R. 1982, "Dominant strategies in stochastic allocation and scheduling programs," Deterministic and Stochastic Scheduling, eds. M. A. H. Dempster, J. K. Lenstra, and A. H. G. Rinnooy Kan, D Reidel Publishing, Dordrecht, The Netherlands.

[22]

Ow, P. S. 1986, "Experiments in knowledge-based scheduling," working paper No. 50-85-86, Carnegie-Mellon University.

[23]

Panwalkar, S. S. and Iskander, W. 1977, "A survey of scheduling rules," Operations Research, Vol. 25, No. 1, pp. 45-61.

Digital Library

[24]

Park, Y. B.; Pedgen, C. D.; and Enscore, E. E. 1984, " A survey and evaluation of static flowshop scheduling heuristics," international journal of Production Research, Vol. 22, No. 1, pp. 127-141.

[25]

Rinnooy Kan, AH G. 1976, Machine Scheduling Problems, Martinus Nijhoff, The Hague, The Netherlands.

[26]

Robbins, J. H., jr. 1985, "PEPS: The prototype expert priority scheduler," Autofact '85 Conference Proceedings, Society of Manufacturing Engineers, Detroit, Michigan, pp. 13.10-13.34.

[27]

Sarin, S. C. and Dar-El, E. M. 1984, "Approaches to the scheduling problem in FMS," 1984 Fall Industrial Engineering Conference Proceedings, pp. 76-86.

[28]

Shaw, M. J. P. and Whinston, A. B. 1986, "Applications of artificial intelligence to planning and scheduling in flexible manufacturing," Flexible Manufacturing Systems: Methods and Studies, ed. A. Kusiak, North-Holland, Amsterdam, The Netherlands.

[29]

Steffen, M. S. and Green, T. J. 1986, "Hierarchies of sub-periods in constraint-directed scheduling," Proceedings of the Symposium on Real-Time Optimization m Automated Manufacturing Facilities, Gaithersburg, Maryland, January 1986, eds. R. H. F. Jackson and A. W. T. Jones, NBS Special Publication 724 National Bureau of Standards, Gaithersburg. Maryland, pp. 167-183.

[30]

Subramanyam, S, and Askin, R. G. 1986, "An expert systems approach to scheduling in flexible manufacturing systems," Flexible Manufacturing Systems: Methods and Studies, ed. A. Kusiak, North-Holland, Amsterdam, The Netherlands.

Cited By

Fan ZJi RChang SChang K(2024)Novel integer L-shaped method for parallel machine scheduling problem under uncertain sequence-dependent setupsComputers and Industrial Engineering10.1016/j.cie.2024.110282193:COnline publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1016/j.cie.2024.110282
Liu ZWang YLiang XMa YFeng YCheng GLiu Z(2022)A graph neural networks-based deep Q-learning approach for job shop scheduling problems in traffic managementInformation Sciences: an International Journal10.1016/j.ins.2022.06.017607:C(1211-1223)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1016/j.ins.2022.06.017
Wurster MMichel MMay MKuhnle AStricker NLanza G(2022)Modelling and condition-based control of a flexible and hybrid disassembly system with manual and autonomous workstations using reinforcement learningJournal of Intelligent Manufacturing10.1007/s10845-021-01863-333:2(575-591)Online publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1007/s10845-021-01863-3
Show More Cited By

Job-Shop Scheduling Theory: What Is Relevant?
1. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Online algorithms
      1. Online learning algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Effective ensembles of heuristics for scheduling flexible job shop problem with new job insertion

Flexible job shop scheduling problem.Ensembles of heuristics.Re-scheduling for new job insertion.Multiple objectives scheduling problem. This study investigates the flexible job shop scheduling problem (FJSP) with new job insertion. FJSP with new job ...
A GEP-based reactive scheduling policies constructing approach for dynamic flexible job shop scheduling problem with job release dates

Flexible job shop scheduling problem (FJSSP) is generalization of job shop scheduling problem (JSSP), in which an operation may be processed on more than one machine each of which has the same function. Most previous researches on FJSSP assumed that all ...
A Broader View of the Job-Shop Scheduling Problem

We define a job-shop scheduling problem with three dynamic decisions: assigning due-dates to exogenously arriving jobs, releasing jobs from a backlog to the shop floor, and sequencing jobs at each of two workstations in the shop. The job-shop is modeled ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Interfaces

Interfaces Volume 18, Issue 4

August 1988

110 pages

ISSN:0092-2102

EISSN:1526-551X

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 August 1988

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fan ZJi RChang SChang K(2024)Novel integer L-shaped method for parallel machine scheduling problem under uncertain sequence-dependent setupsComputers and Industrial Engineering10.1016/j.cie.2024.110282193:COnline publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1016/j.cie.2024.110282
Liu ZWang YLiang XMa YFeng YCheng GLiu Z(2022)A graph neural networks-based deep Q-learning approach for job shop scheduling problems in traffic managementInformation Sciences: an International Journal10.1016/j.ins.2022.06.017607:C(1211-1223)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1016/j.ins.2022.06.017
Wurster MMichel MMay MKuhnle AStricker NLanza G(2022)Modelling and condition-based control of a flexible and hybrid disassembly system with manual and autonomous workstations using reinforcement learningJournal of Intelligent Manufacturing10.1007/s10845-021-01863-333:2(575-591)Online publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1007/s10845-021-01863-3
Freeman NKeskin BMcCullough C(2020)IJAAInterfaces10.1287/inte.2020.106050:6(355-372)Online publication date: 1-Nov-2020
https://dl.acm.org/doi/10.1287/inte.2020.1060
Lee WKim D(2019)Dynamic scheduling using a pheromone-based approach in multi-agent systemsApplied Soft Computing10.1016/j.asoc.2019.10587585:COnline publication date: 1-Dec-2019
https://dl.acm.org/doi/10.1016/j.asoc.2019.105875
Park JMei YNguyen SChen GZhang M(2018)An investigation of ensemble combination schemes for genetic programming based hyper-heuristic approaches to dynamic job shop schedulingApplied Soft Computing10.1016/j.asoc.2017.11.02063:C(72-86)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1016/j.asoc.2017.11.020
Brown ADimitrov SBarlatt A(2015)Routing distributions and their impact on dispatch rulesComputers and Industrial Engineering10.1016/j.cie.2015.07.01488:C(293-306)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1016/j.cie.2015.07.014
Sarin SSherali HLiao L(2014)Minimizing conditional-value-at-risk for stochastic scheduling problemsJournal of Scheduling10.1007/s10951-013-0349-617:1(5-15)Online publication date: 1-Feb-2014
https://dl.acm.org/doi/10.1007/s10951-013-0349-6
Monfared MYang J(2004)Design of an intelligent manufacturing scheduling and control system using fuzzy logic: Sensitivity analysis and parameter optimizationJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.5555/1300646.130065015:2(89-104)Online publication date: 1-Apr-2004
https://dl.acm.org/doi/10.5555/1300646.1300650
Jain SBarber KOsterfeld D(1990)Expert simulation for on-line schedulingCommunications of the ACM10.1145/84537.8454733:10(54-60)Online publication date: 1-Oct-1990
https://dl.acm.org/doi/10.1145/84537.84547

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents