One-machine rescheduling heuristics with efficiency and stability as criteria

https://doi.org/10.1016/0305-0548(93)90091-VGet rights and content

Abstract

Heuristics for the problem of rescheduling a machine on occurrence of an unforeseen disruption are developed. The criteria include minimization of the makespan (schedule efficiency) and the impact of the schedule change (schedule stability). The impact of schedule change is a non-regular performance measure defined in two ways:

(1) the starting time deviations between the new schedule and the original schedule, and

(2) a measure of the sequence difference between the two schedules. Three local search procedures are developed for the bicriterion problem and a set of experiments are conducted to test the efficacy of the heuristics. The heuristic solutions are shown to be effective in that the schedule stability can be increased significantly with little or no sacrifice in makespan.

References (15)

  • J. Carlier

    The one-machine sequencing problem

    Eur. J. Ops Res.

    (1982)
  • M.R. Garey et al.

    Computers and Intractability

    (1979)
  • M. Florian et al.

    An implicit enumeration algorithm for the machine sequencing problem

    Mgmt Sci.

    (1979)
  • G.B. McMahon et al.

    On scheduling with ready times and due dates to minimize lateness

    Ops Res.

    (1975)
  • E. Balas

    Machine sequencing via disjunctive graphs: an implicit enumeration algorithm

    Ops Res.

    (1975)
  • J. Adams et al.

    The shifting bottleneck procedure for job shop scheduling

    Mgmt Sci.

    (1988)
  • J. Carlier et al.

    An algorithm for solving the job-shop problem

    Mgmt Sci.

    (1989)
There are more references available in the full text version of this article.

Cited by (225)

  • A three-stage decomposition algorithm for decentralized multi-project scheduling under uncertainty

    2021, Computers and Industrial Engineering
    Citation Excerpt :

    The content of the information exchanges was then utilized to obtain a baseline schedule (cf. Confessore, Giordani, & Rismondo, 2007; Homberger, 2012; Adhau & Mittal, 2013). The baseline schedule served as a basis for planning external tasks such as preventive maintenance, procurement of materials, and committing to ship dates (Wu, Storer, & Chang, 1993). In multi-project environments, it is necessary to seek a schedule that can be agreed upon by all parties involved (e.g., clients and suppliers, as well as workers and other personnel) before execution (Herroelen & Leus, 2004).

  • Predictive-reactive strategy for identical parallel machine rescheduling

    2021, Computers and Operations Research
    Citation Excerpt :

    To the best of our knowledge, there is not any rescheduling problem in the literature that discussed this criterion. The efficiency usually measures the performance of a scheduling system, but, in dynamic environments, the impact of jobs deviation is also measured, referred to as stability measure (Wu et al., 1993; Pfeiffer et al., 2007; Zhang et al., 2013). The stability measure evaluates the impact of disruptions induced by moving job during a rescheduling event (Rangsaritratsamee et al., 2004; Tighazoui et al., 2021).

  • Modelling and comparison of stability metrics for a re-optimisation approach of the Inventory Routing Problem under demand uncertainty

    2021, EURO Journal on Transportation and Logistics
    Citation Excerpt :

    Within these fields, a special care is given to problems modelled over a rolling horizon: while they do not carry out re-optimisation as such, they often deal with uncertainty with a real concern for stability. Stability when re-optimising was first tackled in the scheduling field by Wu et al. (1993). In this work, heuristics are proposed to re-schedule jobs on one machine when a disruption occurs, e.g. a machine failure, with two objectives: efficiency (i.e. makespan) and stability.

View all citing articles on Scopus

S. David Wu is an Associate Professor of Industrial Engineering at Lehigh University. His primary research areas include production planning and scheduling, combinatorial optimization, and telecommunication. His recent work has been in the area of scheduling and control of failure-prone production systems. He holds a M.S. and a Ph.D. degrees, both in Industrial Engineering, from the Pennsylvania State University.

§

Robert H. Storer is an Assistant Professor of Industrial Engineering at Lehigh University. He holds a Ph.D. in Industrial and Systems Engineering and a M.S. in Operations Research from the Georgia Institute of Technology, and a B.S. in Industrial Engineering and Operations Research from the University of Michigan. His research interests involve the application of statistics and operations research to industrial problems. Research thrusts are in the areas of statistical methods for improvement of continuous processes, and heuristic approaches to combinatorial problems.

Pei-Chann Chang is an Associate Professor of Industrial Engineering at Yuan-Tze Institute of Technology, Tao-Yuan, Taiwan, Republic of China. His primary research area is in production scheduling and control. He holds an M.S. and a Ph.D. degrees in Industrial Engineering from Lehigh University.

View full text