Evaluation and comparison of production schedules

https://doi.org/10.1016/S0166-3615(99)00071-8Get rights and content

Abstract

The understanding of what constitutes a “good” production schedule is central to the development and evaluation of automated scheduling systems and their implementation in real-world factories. In this paper, we provide a definition of a schedule and discuss potential uses for a schedule within the organization. We then describe a number of different considerations that must be taken into account when assessing the quality of a schedule, and discuss their implications for the design and implementation of scheduling systems.

Introduction

Although there has been a vast body of work on production scheduling in both the technical literature and industrial practice [36], [50], [58], the problem of assessing the quality of a given production schedule does not seem to have been studied extensively to date. However, a clear understanding of how the quality of a schedule is assessed (i.e., what constitutes a “good” schedule) is critical to the successful implementation of scheduling systems in real-world manufacturing environments. Unless we can compare the schedules generated by a given system, either automated or manual, to those generated by alternative systems in some objective and quantifiable way, we will lack a systematic framework for evaluating the performance of scheduling systems and their impact on the performance of the manufacturing system as a whole. Our goal in this paper is to describe some of the issues involved in assessing the quality of production schedules in order to bring them, and their implications for the development and implementation of scheduling systems, to the attention of the scheduling community and encourage research towards their effective resolution. While many of these issues appear obvious when stated, many of them have not been considered in much of the scheduling work done to date. Thus, there appears to be considerable benefit in presenting them within a coherent framework.

We begin by discussing the nature of a production schedule — what it is, some basic characteristics of schedules and how schedules are used in a manufacturing facility. We then examine the problem of assessing schedule quality from several different perspectives. We conclude the paper with a discussion of the implications of the issues raised in the paper for the development of automated scheduling systems and their implementation in practice.

Section snippets

What is a schedule?

The most general definition of the scheduling problem is that of assigning scarce resources to competing activities over a given time horizon to obtain the best possible system performance. In this paper, we will focus on the problem of factory scheduling, where the resources are machines and the competing activities are jobs that require processing on the machines. Thus, we shall refer to a workpiece or batch of workpieces requiring processing at several different workcenters as a job. The

Feasible and acceptable schedules

Whether we are dealing with a predictive or a historical schedule, the question “What makes a good schedule good?” is valid. The first condition that any schedule must satisfy is feasibility — it should not violate any of the constraints present in the manufacturing system in which it is to be executed. In other words, its execution over the specified scheduling horizon must be physically possible. It must put jobs through operations in the order specified by the process plans. It must assign

Issues in schedule quality assessment

Once a feasible, acceptable schedule is available, the problem of assessing schedule quality can begin to be addressed. This question can be approached from a number of different perspectives including: individual schedules vs. a group of schedules, absolute measurement vs. relative comparison, tradeoffs between multiple metrics, static vs. dynamic measurements and schedule vs. state measurements. These ideas are discussed briefly before addressing metrics at a more concrete level. While many

Selection of metrics to apply

The issue of what metrics to use in assessing the quality of a schedule is far from trivial. Answering this question is equivalent to describing the kind of behavior we want the scheduling system to induce in the manufacturing system, which in turn is equivalent to deciding what the goals of factory management should be. At an abstract level, this is easy enough: the factory should be run in such a way as to maximize the value to the organization. This involves decisions such as whether the

Implications for design and implementation of scheduling systems

The above discussion should highlight the fact that the problem of assessing the quality of a schedule is actually a complicated question that can be addressed from a number of different perspectives. The first characteristic of the schedule measurement problem is its multiobjective, multiattribute nature. Even when a single individual is involved in the evaluation process, the question of how to address the tradeoffs between the different metrics of interest is hard to address without keeping

Acknowledgments

Part of the research of Reha Uzsoy was performed while a visiting researcher at Intel in July–August 1992. The authors would like to thank Prof. K.N. McKay for his extensive, insightful comments.

Karl Kempf is a Principal Scientist in the Knowledge Application Laboratory at the Intel Corp. in Phoenix, AZ. He was the founding co-chairman of the AAAI Special Interest Group in Manufacturing (SIGMAN), and serves on the editorial board of IEEE Expert. He receive his BS in Chemistry and BA in Physics from Otterbein College, and did graduate work at Stanford University and the University of Akron while earning his PhD in Computer Science. His research interests center on spatial and temporal

References (66)

  • J. Adams et al.

    The shifting bottleneck procedure for job-shop scheduling

    Management Science

    (1988)
  • X. Bai et al.

    Hierarchical real-time scheduling of a semiconductor fabrication facility

  • R.S. Barr et al.

    Designing and reporting on computational experiments with Heuristic methods

    Journal of Heuristics

    (1995)
  • J.C. Bean et al.

    Matchup scheduling with multiple resources, release dates and disruptions

    Operations Research

    (1991)
  • K. Bhaskaran et al.

    Dispatching

  • S. Chand et al.

    A note on the single-machine scheduling problem with minimum weighted completion time and minimum allowable tardiness

    Naval Research Logistics Quarterly

    (1986)
  • Y.L. Chang et al.

    Ranking dispatching rules by data envelopment analysis in a job shop environment

    IIE Transactions on Scheduling and Logistics

    (1986)
  • L.K. Church et al.

    Analysis of periodic and event-driven rescheduling policies in dynamic shops

    International Journal of Computer-Integrated Manufacturing

    (1992)
  • R.W. Conway et al.

    Theory of scheduling

    (1967)
  • R.L. Daniels et al.

    Robust scheduling to hedge against processing time uncertainty in single-stage production

    Management Science

    (1995)
  • D.G. Dannenbring

    Procedures for estimating optimal solution values for large combinatorial problems

    Management Science

    (1977)
  • S. Dauzere-Peres et al.

    An integrated approach in production planning and scheduling

    Lecture notes in economics and mathematical systems

    (1994)
  • P. Elleby et al.

    A constraint-based scheduling system for VLSI wafer fabrication

  • J. Fisher

    Use of nonfinancial performance measures

    Journal of Cost Management

    (1992)
  • M.S. Fox et al.

    ISIS: a knowledge-based system for factory scheduling

    Expert Systems

    (1984)
  • K. Gary et al.

    Assessing the quality of production schedules

  • M.R. Garey et al.

    Computers and intractability: a guide to the theory of NP-completeness

    (1979)
  • B.L. Golden et al.

    Interval estimation of a global optimum for large combinatorial problems

    Naval Research Logistics Quarterly

    (1979)
  • E.M. Goldratt

    The goal: a process of ongoing improvement

    (1986)
  • Gong L., Matsuo H. A control policy for a manufacturing system with random yield and rework. The Graduate School of...
  • K. Hadavi et al.

    ReDS: a dynamic planning, scheduling and control system for manufacturing

    Journal of Manufacturing Systems

    (1989)
  • J.M. Harrison et al.

    Measuring delivery performance: a case study from the semiconductor industry

  • R.H. Hayes et al.

    Restoring our competitive edge: computing through manufacturing

    (1984)
  • Cited by (53)

    • A unified view on planning, scheduling and dispatching for a factory

      2020, Advanced Engineering Informatics
      Citation Excerpt :

      This definition sometimes is refined to fit more specific shop floor conditions. For example, Kempf et al. [31] define a schedule as a set of start times and machine assignments for each operation of each job to be scheduled. Conway et al. [32] regard scheduling as the task of constructing an ordering of the operations associated with each machine.

    • Taking advantage of a diverse set of efficient production schedules: A two-step approach for scheduling with side concerns

      2013, Computers and Operations Research
      Citation Excerpt :

      Moreover, the implications of a schedule are not necessarily confined within the borders of a company. It is increasingly becoming common for companies to share their production schedules with their suppliers with the trend towards increasing collaboration between the elements of supply chains, as noted in [25]. In other words, the schedule of a shop floor has implications that are collectively experienced by a number of different persons with different responsibilities.

    • An empirical investigation of scheduling performance criteria

      2011, Journal of Operations Management
      Citation Excerpt :

      Interestingly, scheduling has a large effect on business performance, such as the efficiency and flexibility of a firm, by determining its order lead times, delivery flexibility, machine and material usage, and staff workload (Leung, 2004; Pinedo, 2008; Van Wezel et al., 2006b; Zwikael and Sadeh, 2007). However, performance measurement in terms of scheduling has received far less attention than other business functions (De Toni and Tonchia, 2001; Kempf et al., 2000; MacCarthy et al., 2001; McKay et al., 2002). As with all organizational functions, to measure and manage scheduling performance, appropriate performance criteria or metrics are needed.

    • Assessing the value of RFID in pharmaceutical production scheduling

      2009, IFAC Proceedings Volumes (IFAC-PapersOnline)
    View all citing articles on Scopus

    Karl Kempf is a Principal Scientist in the Knowledge Application Laboratory at the Intel Corp. in Phoenix, AZ. He was the founding co-chairman of the AAAI Special Interest Group in Manufacturing (SIGMAN), and serves on the editorial board of IEEE Expert. He receive his BS in Chemistry and BA in Physics from Otterbein College, and did graduate work at Stanford University and the University of Akron while earning his PhD in Computer Science. His research interests center on spatial and temporal reasoning systems applied to robots specifically and to manufacturing systems in general. In addition to presenting tutorials and workshops on these subjects at conferences and in invited presentations at universities and corporations, he also has published widely in these areas and has pursued these interests by designing, developing, and deploying artificially intelligent system in the fields of Grand Prix motor racing with Team Ferrari (intelligent suspension design programs and track-side data interpretation systems), cinematic special effects with the SuperMan series of movies (intelligent robots to create the “flying” scenes), at McDonell Douglas Corp. (intelligent robot programming systems), and at Intel Corp. (intelligent manufacturing scheduling systems).

    Reha Uzsoy is a professor in the School of Industrial Engineering at Purdue University. He holds BS degrees in Industrial Engineering and Mathematics and an MS in Industrial Engineering from Bogazici University, Istanbul, Turkey. He received his PhD in Industrial Engineering from the University of Florida in 1990 and joined the faculty at Purdue the same year. His research and teaching interests are in production planning and scheduling, particularly in semiconductor manufacturing. In 1997 he was named Outstanding Young Industrial Engineer in education by the Institute of Industrial Engineers. He has also worked as a visiting researcher at Intel Corp. and IC Delco.

    Stephen P. Smith received his BS, MS, and PhD. degrees in Computer Science from Michigan State University in 1977, 1979, and 1982, respectively. Since 1992, Dr. Smith has worked at Intel on various problems involved in the planning, scheduling and control of semiconductor manufacturing. He is currently the manager of the Factory Scheduling group in Intel's corporate automation department. His current focus is on next generation systems for 300-mm execution control. Prior to joining Intel, Dr. Smith was a research scientist at Northrop's Research and Technology Center. There he worked on a wide variety of advanced Al-based software systems, including those for manufacturing scheduling and planning, image understanding, pattern recognition, and computer-supported collaboration. Dr. Smith has authored more than a dozen technical publications and has served as a technical reviewer for the National Science Foundation, IEEE Transactions on PAMI and IEEE Transactions on SMC, IEEE Expert, and ACM Computer Reviews. He is a member of the IEEE, ACM, AAAI, and Phi Kappa Phi.

    Kevin Gary holds MS and PhD degrees in computer science from the Arizona State University. His research interests are in artificial intelligence and software engineering.

    View full text