Optimization of schedule robustness and stability under random machine breakdowns and processing time variability
Authors:
- 19 December 2009
- journal article
- Published by Taylor & Francis in IIE Transactions
- Vol. 42 (3) , 203-220
Abstract
In practice, scheduling systems are subject to considerable uncertainty in highly dynamic operating environments. The ability to cope with uncertainty in the scheduling process is becoming an increasingly important issue. This paper takes a proactive scheduling approach to study scheduling problems with two sources of uncertainty: processing time variability and machine breakdowns. Two robustness (expected total flow time and expected total tardiness) and three stability (the sum of the squared and absolute differences of the job completion times and the sum of the variances of the realized completion times) measures are defined. Special cases for which the measures can be easily optimized are identified. A dominance rule and two lower bounds for one of the robustness measures are developed and subseqently used in a branch-and-bound algorithm to solve the problem exactly. A beam search heuristic is also proposed to solve large problems for all five measures. The computational results show that the beam search heuristic is capable of generating robust schedules with little average deviation from the optimal objective function value (obtained via the branch-and-bound algorithm) and it performs significantly better than a number of heuristics available in the literature for all five measures. © 2010 "IIE"Keywords
This publication has 22 references indexed in Scilit:
- Robustness and stability measures for scheduling: single-machine environmentIIE Transactions, 2008
- A note on scheduling parallel machines subject to breakdown and repairNaval Research Logistics (NRL), 2003
- Predictable scheduling of a single machine with breakdowns and sensitive jobsInternational Journal of Production Research, 1999
- Predictable scheduling of a single machine subject to breakdownsInternational Journal of Computer Integrated Manufacturing, 1999
- Stochastic scheduling on a repairable machine with Erlang uptime distributionAdvances in Applied Probability, 1998
- A new decomposition approach for the single machine total tardiness scheduling problemJournal of the Operational Research Society, 1998
- A beam search-based algorithm and evaluation of scheduling approaches for flexible manufacturing systemsIIE Transactions, 1998
- β-Robust scheduling for single-machine systems with uncertain processing timesIIE Transactions, 1997
- Stability of an optimal schedule in a job shopOmega, 1997
- ROBUSTNESS MEASURES AND ROBUST SCHEDULING FOR JOB SHOPSIIE Transactions, 1994