Skip to main content

Advertisement

SpringerLink
Log in

Efficient bi-objective ant colony approach to minimize total tardiness and system unavailability for a parallel machine scheduling problem

  • ORIGINAL ARTICLE
  • Published:
The International Journal of Advanced Manufacturing Technology Aims and scope Submit manuscript

Abstract

In recent years, decision makers give more importance to the maintenance function, viewing its substantial contribution to business productivity. However, most literature on scheduling studies does not take into account maintenance planning when implementing production schedules. The achievement of production plan without taking into account maintenance activities increases the probability of machine breakdowns, and inversely, considering maintenance actions in production planning elongates the achievement dates of orders and affects deadlines. In this paper, we propose a bi-objective model to deal with production scheduling and maintenance planning problems simultaneously. The performance criteria considered for production and maintenance are, respectively, the total tardiness and the unavailability of the production system. The start times of preventive maintenance actions and their number are not fixed in advance but considered, with the execution dates of production tasks, as decisions variables of the problem. The solution of the integrated model is based on multi-objective ant colony optimization approach. The proposed algorithm (Pareto ant colony optimization) is compared, on the basis of several metrics, with well-known multi-objective genetic algorithms, namely NSGA-II and SPEA 2, and a hybrid particle swarm optimization algorithm. Interesting results are obtained via empirical study.

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

  1. Abido MA (2010) Multiobjective particle swarm optimization with nondominated local and global sets. Nat Comput 9(3):747–766

    Article  MathSciNet  MATH  Google Scholar 

  2. Berrichi A, Amodeo L, Yalaoui F, Châtelet E, Mezghiche M (2009) Bi-objective optimization algorithms for joint production and maintenance scheduling: application to the parallel machine problem. J Intell Manuf 20:389–400

    Article  Google Scholar 

  3. Berrichi A, Yalaoui F, Amodeo L, Mezghiche M (2010) Bi-objective ant colony optimization approach to optimize production and maintenance scheduling. Comput Oper Res 37:1584–1596

    Article  MathSciNet  MATH  Google Scholar 

  4. Cassady CR, Kutanoglu E (2003) Minimizing job tardiness using integrated preventive maintenance planning and production scheduling. IIE Trans 35:503–513

    Article  Google Scholar 

  5. Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197

    Article  Google Scholar 

  6. Dorigo M, Maniezzo V, Colorni A (1996) The ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics Part B 26(1):29–41

    Article  Google Scholar 

  7. Ebeling CE (1997) An introduction to reliability and maintainability engineering. McGraw-Hill, USA

    Google Scholar 

  8. Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W.H. Freeman and Company, San Francisco California

    MATH  Google Scholar 

  9. Garcıa-Martınez C, Cordon O, Herrera F (2007) A taxonomy and an empirical analysis of multiple objective ant colony optimization algorithms for the bi-criteria TSP. Eur J Oper Res 180:116–148

    Article  MATH  Google Scholar 

  10. Ishibuchi H, Yoshida T, Murata T (2003) Balance between genetic search and local search in mimetic algorithms for multiobjective permutation flowshop scheduling. IEEE Trans Evol Comput 7(2):204–223

    Article  Google Scholar 

  11. Kaabi J, Varnier C, Zerhouni N (2002) Heuristics for scheduling maintenance and production on a single machine. IEEE Conference on Systems, Man and Cybernetics. October 6–9 Hammamet, Tunisia

  12. Kaabi J, Varnier C, Zerhouni N (2003) Genetic algorithm for scheduling production and maintenance in a Flow Shop. Laboratory of automatic of Besançon, France (in French)

    Google Scholar 

  13. Kennedy J, Eberhart R (1995) Particle swarm optimization. IEEE International Conference on Neural Network 1942–1948

  14. Krichen S, Dahmani N (2010) A particle swarm optimization approach for the bi-objective load balancing problem. Electronic Notes in Discrete Mathematics 36(1):751–758

    Article  Google Scholar 

  15. Lee C-Y (1996) Machine scheduling with an availability constraint. J Glob Optim 9:395–416

    Article  MATH  Google Scholar 

  16. Lei D (2008) A Pareto archive particle swarm optimization for multi-objective job shop scheduling. Comput Ind Eng 54(4):960–971

    Article  Google Scholar 

  17. Liu DS, Tan KC, Huang SY, Goh CK, Ho WK (2008) On solving multiobjective bin packing problems using evolutionary particle swarm optimization. Eur J Oper Res 190(2):357–382

    Article  MathSciNet  MATH  Google Scholar 

  18. Niu K, Zhou T, Wang L (2010) A hybrid particle swarm optimization for parallel machine total tardiness scheduling. Int J Adv Manuf Technol 49(5–8):723–739

    Article  Google Scholar 

  19. Montalvo I, Izquierdo J, Schwarze S, Pérez-García R (2010) Multi-objective particle swarm optimization applied to water distribution systems design: an approach with human interaction. Math Comput Model 52(7–8):1219–1227

    Article  MATH  Google Scholar 

  20. Rabbani M, Aramoon Bajestani M, Baharian Khoshkhou G (2010) A multi-objective particle swarm optimization for project selection problem. Expert Syst Appl 37(1):315–321

    Article  Google Scholar 

  21. Raghavan NRS, Venkataramana M (2009) Parallel processor scheduling for minimizing total weighted tardiness using ant colony optimisation. Int J Adv Manuf Technol 41:986–996

    Article  Google Scholar 

  22. Rezaie H, Farhad Mardukhi N (2010) A multi-objective particle swarm optimization for web service composition. Communications in computer and information science1, volume 88. Networked Digital Technologies Part 2:112–122

    Article  Google Scholar 

  23. Poli R (2008) Analysis of the publications on the applications of particle swarm optimisation. Journal of Artificial Evolution and Applications. Hindawi Publishing Corp, New York

    Google Scholar 

  24. Ruiz R, García-Diaz JC, Maroto C (2007) Considering scheduling and preventive maintenance in the flowshop sequencing problem. Comput Oper Res 34(11):3314–3330

    Article  MATH  Google Scholar 

  25. Sarayloo F, Tavakkoli-Moghaddam R (2010) Multi objective particle swarm optimization for a dynamic cell formation problem, Proceedings of the World Congress on Engineering III WCE 2010, London, U.K

  26. Schmidt G (2000) Scheduling with limited machine availability. Eur J Oper Res 121:1–15

    Article  MATH  Google Scholar 

  27. Tasgetiren MF, Sevkli M, Liang Y-C, Gencyilmaz G (2004) Particle swarm optimization algorithm for single machine total weighted tardiness problem. Congress on Evolutionary Computation 2:1412–1419

    Google Scholar 

  28. Tsai C-Y, Yeh S-W (2008) A multiple objective particle swarm optimization approach for inventory classification. Int J Prod Econ 114(2):656–666

    Article  Google Scholar 

  29. Villemeur A (1991) Reliability, availability, maintainability and safety assessment. Wiley, USA

    Google Scholar 

  30. Zhang G, Shao X, Li P, Gao L (2009) An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem. Comput Ind Eng 56(4):1309–1318

    Article  Google Scholar 

  31. Zitzler E, Laumanns M, Thiele L (2002) SPEA2: improving the strength Pareto evolutionary algorithm for multiobjective optimization. In: Giannakoglou K, Tsahalis D, Periaux J, Papailou P, Fogarty T (eds) EUROGEN 2001, evolutionary methods for design, optimization, and control with applications to industrial problems. Barcelona, Spain, CIMNE, pp 95–100

    Google Scholar 

  32. Xu D, Sun K, Li H (2008) Parallel machine scheduling with almost periodic non-preemptive maintenance and jobs to minimize makespan. Comput Oper Res 35:1344–1349

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. LIMOSE, Computer Science Department, University of M’hamed Bougara of Boumerdes, Boumerdes, Algeria

    Ali Berrichi

  2. Charles Delaunay Institute, LOSI, UMR STMR 6279, University of Technology of Troyes, Troyes, France

    Farouk Yalaoui

Authors
  1. Ali Berrichi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Farouk Yalaoui
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ali Berrichi.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Berrichi, A., Yalaoui, F. Efficient bi-objective ant colony approach to minimize total tardiness and system unavailability for a parallel machine scheduling problem. Int J Adv Manuf Technol 68, 2295–2310 (2013). https://doi.org/10.1007/s00170-013-4841-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00170-013-4841-0

Keywords

Search

Navigation