Skip to main content

Advertisement

SpringerLink
Log in

A hybrid genetic algorithm for an identical parallel-machine problem with maintenance activity

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

Abstract

The scheduling of maintenance activities has been extensively studied, with most studies focusing on single-machine problems. In real-world applications, however, multiple machines or assembly lines process numerous jobs simultaneously. In this paper, we study a parallel-machine scheduling problem in which the objective is to minimize the total tardiness given that there is a maintenance activity on each machine. We develop a branch-and-bound algorithm to solve the problem with a small problem size. In addition, we propose a hybrid genetic algorithm to obtain the approximate solutions when the number of jobs is large. The performance of the proposed algorithms is evaluated based mainly on computational results.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Instant access to the full article PDF.

Institutional subscriptions

Figure 1
Figure 2
Figure 3

Similar content being viewed by others

References

  • Adiri I, Frostig E and Rinnooy Kan AHG (1991). Scheduling on a single machine with a single breakdown to minimize stochastically the number of tardy jobs. Naval Research Logistics 38 (2): 261–271.

    Article  Google Scholar 

  • Azizoglu M and Kirca O (1998). Tardiness minimization on parallel machines. International Journal of Production Economics 55 (2): 163–168.

    Article  Google Scholar 

  • Chen WJ (2009). Minimizing number of tardy jobs on a single machine subject to periodic maintenance. Omega 37 (3): 591–599.

    Article  Google Scholar 

  • Chen CC (2014). TOYOTA: Let’s Go Places, http://www.toyota.com.tw/, accessed on 1 December 2014.

  • Cheng TCE, Hsu CJ and Yang DL (2011). Unrelated parallel-machine scheduling with deteriorating maintenance activities. Computers & Industrial Engineering 60 (4): 602–605.

    Article  Google Scholar 

  • Du J and Leung JYT (1990). Minimizing total tardiness on one machine is NP-hard. Mathematics of Operations Research 15 (3): 483–495.

    Article  Google Scholar 

  • Ghodratnama A, Rabbani M, Tavakkoli-Moghaddam R and Baboli A (2010). Solving a single-machine scheduling problem with maintenance, job deterioration and learning effect by simulated annealing. Journal of Manufacturing Systems 29 (1): 1–9.

    Article  Google Scholar 

  • Goldberg DE and Lingle R (1985). Alleles, loci and the traveling salesman problem. In: Proceedings of an International Conference on Genetic Algorithms and Their Application. Lawrence Erlbaum Associates: Hillsdale, NJ, pp 154-159.

  • Gustavsson E, Patriksson M, Stromberg AB, Wojciechowski A and Onnheim M (2014). Preventive maintenance scheduling of multi-component systems with interval costs. Computers & Industrial Engineering 76: 390–400.

    Article  Google Scholar 

  • Huang TB (2014). Cheng Drong Aluminium Co., Ltd., http://www.cdal.com.tw/, accessed on 1 December 2014.

  • Joo CM and Kim BS (2013). Genetic algorithms for single machine scheduling with time-dependent deterioration and rate-modifying activities. Expert Systems with Applications 40 (8): 3036–3043.

    Article  Google Scholar 

  • Lee JY and Kim YD (2012). Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance. Computers & Operations Research 39 (9): 2196–2205.

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Lopez EG and O’Neill M (2009). On the effects of locality in a permutation problem: The Sudoku puzzle. In: IEEE Symposium on Computational Intelligence and Games. 7–10 September, IEEE: Milano, Italy, pp 80–87.

    Google Scholar 

  • Luo W, Cheng TCE and Ji M (2015). Single-machine scheduling with a variable maintenance activity. Computers & Industrial Engineering 79: 168–174.

    Article  Google Scholar 

  • Ma Y, Chu C and Zuo C (2010). A survey of scheduling with deterministic machine availability constraints. Computers & Industrial Engineering 58 (2): 199–211.

    Article  Google Scholar 

  • Madhushini N, Rajendran C and Deepa Y (2009). Branch-and-bound algorithms for scheduling in permutation flowshops to minimize the sum of weighted flowtime/sum of weighted tardiness/sum of weighted flowtime and weighted tardiness/sum of weighted flowtime, weighted tardiness and weighted earliness of jobs. Journal of the Operational Research Society 60 (7): 991–1004.

    Article  Google Scholar 

  • Pinedo ML (2008). Scheduling: Theory, Algorithms, and System. 3rd edn, Prentice-Hall: New Jersey.

    Google Scholar 

  • Qi X, Chen T and Tu F (1999). Scheduling the maintenance on a single machine. Journal of the Operational Research Society 50 (10): 1071–1078.

    Article  Google Scholar 

  • Sbihi M and Varnier C (2008). Single-machine scheduling with periodic and flexible periodic maintenance to minimize maximum tardiness. Computers & Industrial Engineering 55 (4): 830–840.

    Article  Google Scholar 

  • Schaller J and Valente JMS (2012). An evaluation of heuristics for scheduling a non-delay permutation flow shop with family setups to minimize total earliness and tardiness. Journal of the Operational Research Society 64 (6): 805–816.

    Article  Google Scholar 

  • Schmidt G (2000). Scheduling with limited machine availability. European Journal of Operational Research 121 (1): 1–15.

    Article  Google Scholar 

  • Shen L, Wang D and Wang XY (2013). Parallel-machine scheduling with non-simultaneous machine available time. Applied Mathematical Modelling 37 (7): 5227–5232.

    Article  Google Scholar 

  • Shim SO and Kim YD (2007). Scheduling on parallel identical machines to minimize total tardiness. European Journal of Operational Research 177 (1): 135–146.

    Article  Google Scholar 

  • Wang JB and Wei CM (2011). Parallel machine scheduling with a deteriorating maintenance activity and total absolute differences penalties. Applied Mathematics and Computation 217 (20): 8093–8099.

    Article  Google Scholar 

  • Xu D and Xiong S (2012). Minimizing total flow time in the single-machine scheduling problem with periodic maintenance. Journal of the Operational Research Society 63 (4): 567–567.

    Article  Google Scholar 

  • Yang SJ (2010). Single-machine scheduling problems with both start-time dependent learning and position dependent aging effects under deteriorating maintenance consideration. Applied Mathematics and Computation 217 (7): 3321–3329.

    Article  Google Scholar 

  • Yang SJ (2012). Single-machine scheduling problems simultaneously with deterioration and learning effects under deteriorating multi-maintenance activities consideration. Computers & Industrial Engineering 62 (1): 271–275.

    Article  Google Scholar 

  • Yang SJ (2013). Unrelated parallel-machine scheduling with deterioration effects and deteriorating multi-maintenance activities for minimizing the total completion time. Applied Mathematical Modelling 37 (5): 2995–3005.

    Article  Google Scholar 

  • Yang SL, Ma Y, Xu DL and Yang JB (2011). Minimizing total completion time on a single machine with a flexible maintenance activity. Computers & Operations Research 38 (4): 755–770.

    Article  Google Scholar 

  • Yin YQ, Wu WH, Wu WH and Wu CC (2014). A branch-and-bound algorithm for a single machine sequencing to minimize the total tardiness with arbitrary release dates and position-dependent learning effects. Information Sciences 256: 91–108.

    Article  Google Scholar 

  • Yu X, Zhang Y, Xu D and Yin Y (2013). Single machine scheduling problem with two synergetic agents and piece-rate maintenance. Applied Mathematical Modelling 37 (3): 1390–1399.

    Article  Google Scholar 

Download references

Acknowledgements

The authors are grateful to the editor and the referees, whose constructive comments have led to a substantial improvement in the presentation of the paper. We would also thank T.B. Huang for giving us the real-world application. The first author was supported under NSC 100-2221-E-035-029-MY3 and the second author was supported under NSC 102-2221-E-241 -018.

Author information

Authors and Affiliations

  1. Feng Chia University, Taichung, Taiwan (R.O.C.)

    Wen-Chiung Lee & Lin-Yo Lee

  2. Hungkuang University, Taichung, Taiwan (R.O.C.)

    Jen-Ya Wang

Authors
  1. Wen-Chiung Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jen-Ya Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Lin-Yo Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jen-Ya Wang.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Lee, WC., Wang, JY. & Lee, LY. A hybrid genetic algorithm for an identical parallel-machine problem with maintenance activity. J Oper Res Soc 66, 1906–1918 (2015). https://doi.org/10.1057/jors.2015.19

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

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

Keywords

Search

Navigation