article

Scheduling Position-Dependent Maintenance Operations

Authors:

Maciej Drozdowski,

Radosław PaszkowskiAuthors Info & Claims

Operations Research, Volume 65, Issue 6

Pages 1657 - 1677

https://doi.org/10.1287/opre.2017.1659

Published: 01 December 2017 Publication History

Abstract

This paper addresses one-machine scheduling with maintenance restrictions. A maintenance operation is position dependent in a sequence of normal jobs if the maintenance has to be performed after at most some defined number of job changes on the machine. We show that several problems with objective functions C_max and L_max are still solvable in polynomial time if position-dependent maintenance is considered. We then consider the problem of preemptive scheduling with ready times and due dates on one machine with the L_max criterion. We show that this problem is computationally hard and present the characteristics of this problem-for example, the fact that optimum schedules may be nonactive. After determining a set of dominance properties, branch-and-bound and local search algorithms are proposed. The performance of the algorithms is evaluated using a series of computational experiments.

References

[1]

Bachman A, Janiak A (2004) Scheduling jobs with position-dependent processing times. J. Oper. Res. Soc. 55(3):257-264.

[2]

Baker KR, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1983) Preemptive scheduling of a single machine to minimize maximum cost subject to release dates and precedence constraints. Oper. Res. 31(2):381-386.

Digital Library

[3]

Blazewicz J, Dell'Olmo P, Drozdowski M, Maczka P (2003) Scheduling multiprocessor tasks on parallel processors with limited availability. Eur. J. Oper. Res. 149(2):377-389.

[4]

Blazewicz J, Ecker K, Pesch E, Schmidt G, Weglarz J (2007) Handbook on Scheduling (Springer, Berlin).

[5]

Birkler J, Large J, Smith G, Timson F (1993) Reconstructing a production capability: Past experience, restart criteria, and suggested policies. Report MR-273-ACQ, RAND Corporation, Santa Monica, CA.

[6]

Biskup D (1999) Single-machine scheduling with learning considerations. Eur. J. Oper. Res. 115(1):173-178.

[7]

Biskup D (2008) A state-of-the-art review on scheduling with learning effects. Eur. J. Oper. Res. 188(2):315-329.

[8]

Chen J-S (2008) Optimization models for the tool change scheduling problem. Omega 36(5):888-894.

[9]

Costa A, Cappadonna FA, Fichera S (2016) Minimizing the total completion time on a parallel machine system with tool changes. Comput. Indust. Engrg. 91(January):290-301.

Digital Library

[10]

Drozdowski M, Jaehn F, Paszkowski R (2016) Instances for position-dependent maintenance scheduling. Accessed on September 28, 2017, http://www.cs.put.poznan.pl/mdrozdowski/maintenance-scheduling/.

[11]

Formanowicz P (2000) Szeregowanie zadan w systemach z ograniczona dostepnoscia procesorów. Ph.D. thesis, Poznan University of Technology, Poznan, Poland.

[12]

Garey MR, Johnson DS (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman, San Francisco).

[13]

Graves GH, Lee C-Y (1999) Scheduling maintenance and semiresumable jobs on a single machine. Naval Res. Logist. 46(7):845-863.

[14]

Kubzin MA, Strusevich VA (2006) Planning machine maintenance in two-machine shop scheduling. Oper. Res. 54(4):789-800.

[15]

Lageweg BJ, Lenstra JK, Rinnooy Kan AHG (1976) Minimizing maximum lateness on one machine: Computational experience and some applications. Stat. Neerlandica 30(1):25-41.

[16]

Lee C-Y (1996) Machine scheduling with an availability constraint. J. Global Optim. 9(3-4):395-416.

[17]

Lee C-Y (2004) Machine scheduling with availability constraints. Leung JY-T, ed. Handbook of Scheduling (Chapman & Hall/CRC, Boca Raton, FL), 22.1-22.13.

[18]

Lee W-C, Wu C-C (2009) A note on single-machine group scheduling problems with position-based learning effect. Appl. Math. Model. 33(4):2159-2163.

[19]

Lenstra JK, Rinnooy Kan AHG, Brucker P (1977) Complexity of machine scheduling problems. Ann. Discrete Math. 1:343-362.

[20]

Low C, Ji M, Hsu C-J, Su C-T (2010) Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance. Appl. Math. Model. 34(2):334-342.

[21]

Low C, Li R-K, Wu G-H, Huang C-L (2015) Minimizing the sum of absolute deviations under a common due date for a single-machine scheduling problem with availability constraints. J. Indust. Production Engrg. 32(3):204-217.

[22]

Reisch A (2014) Ablaufplanung bei positionsfixen Wartungsmaßnahmen. Master's thesis, University of Augsburg, Augsburg, Germany.

[23]

Rustogi K, Strusevich VA (2012) Simple matching vs. linear assignment in scheduling models with positional effects: A critical review. Eur. J. Oper. Res. 222(3):393-407.

[24]

Rustogi K, Strusevich VA (2014) Combining time and position dependent effects on a single machine subject to rate-modifying activities. Omega 42(1):166-178.

[25]

Ruther S (2013) Integrated aircraft routing, crew pairing, and tail assignment. PhD thesis, University of Newcastle, Callaghan, NSW, Australia.

[26]

Yang S, Ma Y, Xu D, Yang J (2011) Minimizing total completion time on a single machine with a flexible maintenance activity. Comput. Oper. Res. 38(4):755-770.

Digital Library

[27]

Yao X, Fernández-Gaucherand E, Fu MC, Marcus SI (2004) Optimal preventive maintenance scheduling in semiconductor manufacturing. IEEE Trans. Semiconductor Manuf. 17(3):345-356.

[28]

Wang J-B (2005) Flow shop scheduling jobs with position-dependent processing times. J. Appl. Math. Comput. 18(1-2):383-391.

Cited By

Drozdowski MShakhlevich N(2021)Scheduling divisible loads with time and cost constraintsJournal of Scheduling10.1007/s10951-019-00626-624:5(507-521)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s10951-019-00626-6
Nadarajah SCire A(2020)Network-Based Approximate Linear Programming for Discrete OptimizationOperations Research10.1287/opre.2019.195368:6(1767-1786)Online publication date: 1-Nov-2020
https://dl.acm.org/doi/10.1287/opre.2019.1953
Bülbül KKedad-Sidhoum SŞen H(2019)Single-machine common due date total earliness/tardiness scheduling with machine unavailabilityJournal of Scheduling10.1007/s10951-018-0585-x22:5(543-565)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1007/s10951-018-0585-x

Scheduling Position-Dependent Maintenance Operations
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

Machine scheduling with deteriorating and resource-dependent maintenance activity

Concept of deteriorating and resource-dependent maintenance is introduced.Four single-machine scheduling problems are analyzed.Measures are makespan, flowtime, maximum tardiness and due-date related.Solving algorithms are proposed for the considered ...
Plant shutdown maintenance workforce team assignment and job scheduling
Abstract
An important and challenging real-life problem is considered, involving workforce assignment and job scheduling for shutdown maintenance in a large oil refinery. A limited number of maintenance employees must be divided into several teams that ...
Two-machine scheduling with aging effects and variable maintenance activities
Highlights
- Two-machine job scheduling is considered with aging and maintenance effects.
- ILP models are formulated to represent the problem and optimally solve smaller sizes.
- Six heuristic methods are developed to efficiently solve larger ...
Abstract
This paper presents models and solution algorithms for a two-machine scheduling problem with position-dependent job processing times subject to both aging and maintenance effects. Aiming to minimize the overall makespan for two identical parallel ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Operations Research

Operations Research Volume 65, Issue 6

December 2017

307 pages

ISSN:0030-364X

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 December 2017

Accepted: 03 May 2017

Received: 23 February 2016

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
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

Drozdowski MShakhlevich N(2021)Scheduling divisible loads with time and cost constraintsJournal of Scheduling10.1007/s10951-019-00626-624:5(507-521)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s10951-019-00626-6
Nadarajah SCire A(2020)Network-Based Approximate Linear Programming for Discrete OptimizationOperations Research10.1287/opre.2019.195368:6(1767-1786)Online publication date: 1-Nov-2020
https://dl.acm.org/doi/10.1287/opre.2019.1953
Bülbül KKedad-Sidhoum SŞen H(2019)Single-machine common due date total earliness/tardiness scheduling with machine unavailabilityJournal of Scheduling10.1007/s10951-018-0585-x22:5(543-565)Online publication date: 1-Oct-2019
https://dl.acm.org/doi/10.1007/s10951-018-0585-x

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