Skip to main content
SpringerLink
Log in

Rescheduling unrelated parallel machines with total flow time and total disruption cost criteria

  • Theoretical Paper
  • Published:
Journal of the Operational Research Society

Abstract

In this paper, we consider a rescheduling problem where a set of jobs has already been assigned to unrelated parallel machines. When a disruption occurs on one of the machines, the affected jobs are rescheduled, considering the efficiency and the schedule deviation measures. The efficiency measure is the total flow time, and the schedule deviation measure is the total disruption cost caused by the differences between the initial and current schedules. We provide polynomial-time solution methods to the following hierarchical optimization problems: minimizing total disruption cost among the minimum total flow time schedules and minimizing total flow time among the minimum total disruption cost schedules. We propose exponential-time algorithms to generate all efficient solutions and to minimize a specified function of the measures. Our extensive computational tests on large size problem instances have revealed that our optimization algorithm finds the best solution by generating only a small portion of all efficient solutions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Abumaizar RJ and Svestka JA (1997). Rescheduling job shops under random disruptions . Int J Prod Res 35: 2065–2082.

    Article  Google Scholar 

  • Aggarwal V (1985). A Lagrangean-relaxation method for the constrained assignment problem . Comput Opns Res 12: 97–106.

    Article  Google Scholar 

  • Aktürk MS and Görgülü E (1999). Match-up scheduling under a machine breakdown . Eur J Opl Res 112: 81–97.

    Article  Google Scholar 

  • Alagöz O and Azizoğlu M (2003). Rescheduling of identical parallel machines under machine eligibility constraints . Eur J Opl Res 149: 523–532.

    Article  Google Scholar 

  • Aytug H, Lawley MA, McKay K, Mohan S and Uzsoy R (2005). Executing production schedules in the face of uncertainties: A review and some future directions . Eur J Opl Res 161: 86–110.

    Article  Google Scholar 

  • Azizoğlu M and Alagöz O (2005). Parallel machine rescheduling with machine disruptions . IIE Trans 37: 1113–1118.

    Article  Google Scholar 

  • Bean JC, Birge JR, Mittenthal J and Noon CE (1991). Matchup scheduling with multiple resources, release dates and disruptions . Opns Res 39: 470–483.

    Article  Google Scholar 

  • Church LK and Uzsoy R (1992). Analysis of periodic and event-driven rescheduling policies in dynamic shops . Int J Comp Integ M 5: 153–163.

    Article  Google Scholar 

  • Clausen J, Hansen J, Larsen J and Larsen A (2001). Disruption management . ORMS Today 28: 40–43.

    Google Scholar 

  • Curry J and Peters B (2005). Rescheduling parallel machines with stepwise increasing tardiness and machine assignment stability objectives . Int J Prod Res 43: 3231–3246.

    Article  Google Scholar 

  • Daniels RL and Kouvelis P (1995). Robust scheduling to hedge against processing time uncertainty in single stage production . Mngt Sci 41: 363–376.

    Article  Google Scholar 

  • Hall NG and Potts CN (2004). Rescheduling for new orders . Opns Res 52: 440–453.

    Article  Google Scholar 

  • Kaspi M and Montreuil B (1988). On the scheduling of identical parallel processes with arbitrary initial processor available time. Research Report 88–12, School of Industrial Engineering, Purdue University.

  • Kondakci S, Azizoğlu M and Koksalan M (1996). Note: Bicriteria scheduling for minimizing flow time and maximum tardiness . Nav Res Log 43: 929–936.

    Article  Google Scholar 

  • Lawler EL, Lenstra JK, Rinnooy Kan AHG and Shmoys DB (1989). Sequencing and scheduling: algorithms and complexity. Reports BS-R8909, Centre for Mathematics and Computers Science, Amsterdam.

  • Lee CY (1996). Machine scheduling with an availability constraint . J Glob Opin 9: 395–416.

    Article  Google Scholar 

  • Lee CY and Chen ZL (2000). Scheduling jobs and maintenance activities on parallel machines . Nav Res Log 47: 929–936.

    Article  Google Scholar 

  • Lee CY and Liman SD (1992). Single-machine flow-time scheduling with scheduled maintenance . Acta Inform 29: 375–382.

    Article  Google Scholar 

  • Leung JY-T and Pinedo M (2004). A note on scheduling parallel machines subject to breakdown and repair . Nav Res Log 51: 60–71.

    Article  Google Scholar 

  • Li E and Shaw W (1996). Flow-time performance of modified-scheduling heuristics in a dynamic rescheduling environment . Comput Ind Eng 31: 213–216.

    Article  Google Scholar 

  • Lim A and Xu Z (2009). Searching optimal resequencing and feature assignment on an automated assembly line . J Opl Res Soc 60: 361–371.

    Article  Google Scholar 

  • Logendran R and Subur F (2004). Unrelated parallel machine scheduling with job splitting . IIE Trans 36: 359–372.

    Article  Google Scholar 

  • Logendran R, McDonell B, Smucker B (2007). Scheduling unrelated parallel machines with sequence-dependent set-ups. Comput Opns Res 34: 3420–3438.

  • Mason SJ, Jin S and Wessels CM (2004). Rescheduling strategies for minimizing total weighted tardiness in complex job shops . Int J Prod Res 42: 613–628.

    Article  Google Scholar 

  • Mosheiov G (1994). Minimizing the sum of job completion times on capacitated parallel machines . Math Comp Mod 20: 91–99.

    Article  Google Scholar 

  • O'Donovan R, Uzsoy R and McKay KN (1999). Predictable scheduling of a single machine with breakdowns and sensitive jobs . Int J Prod Res 18: 4217–4233.

    Article  Google Scholar 

  • Olumolade MO and Norrie DH (1996). Reactive scheduling system for cellular manufacturing with failure-prone machines . Int J Comput Integ M 9: 131–144.

    Article  Google Scholar 

  • Ozlen M and Azizoğlu M (2009). Generating all efficient solutions of a rescheduling problem on unrelated parallel machines. Int J Prod Res 47: 5245–5270.

  • Qi XT, Bard JR and Yu G (2006). Disruption management for machine scheduling: the case of SPT schedules . Int J Prod Econ 103: 166–184.

    Article  Google Scholar 

  • Raheja AS and Subramaniam V (2002). Reactive recovery of job shop schedules—A review . Int J Adv Man Tech 19: 756–763.

    Article  Google Scholar 

  • Suresh V and Chaudhuri D (1996). Scheduling of unrelated parallel machines when machine availability is specified . Prod Plan Control 7: 393–400.

    Article  Google Scholar 

  • Ünal AT, Uzsoy R and Kiran AS (1997). Rescheduling on a single machine with part-type dependent setup times and deadlines . Ann Oper Res 70: 93–113.

    Article  Google Scholar 

  • Vieira GE, Herrmann JW and Edward L (2003). Rescheduling manufacturing systems: A framework of strategies, policies and methods . J Sched 6: 39–62.

    Article  Google Scholar 

  • Wu SD, Storer RH and Chang PC (1993). One-machine rescheduling heuristics with efficiency and stability as criteria . Comput Opns Res 20: 1–14.

    Article  Google Scholar 

  • Yaghubian AR, Hodgson TJ, Joines JA, Culbreth CT and Huang JC (1999). Dry kiln scheduling in furniture production . IIE Trans 31: 733–738.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. RMIT University, Melbourne, Australia

    M Ozlen

  2. Middle East Technical University, Ankara, Turkey

    M Azizoğlu

Authors
  1. M Ozlen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M Azizoğlu
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ozlen, M., Azizoğlu, M. Rescheduling unrelated parallel machines with total flow time and total disruption cost criteria. J Oper Res Soc 62, 152–164 (2011). https://doi.org/10.1057/jors.2009.157

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1057/jors.2009.157

Keywords

Search

Navigation