Khatami, M., Zegordi, H. (2015). Flow shop Scheduling Problem with Maintenance Coordination: a New Approach. Journal of Quality Engineering and Production Optimization, 1(1), 1-11. doi: 10.22070/jqepo.2015.184

Mostafa Khatami; Hessameddin Zegordi. "Flow shop Scheduling Problem with Maintenance Coordination: a New Approach". Journal of Quality Engineering and Production Optimization, 1, 1, 2015, 1-11. doi: 10.22070/jqepo.2015.184

Khatami, M., Zegordi, H. (2015). 'Flow shop Scheduling Problem with Maintenance Coordination: a New Approach', Journal of Quality Engineering and Production Optimization, 1(1), pp. 1-11. doi: 10.22070/jqepo.2015.184

Khatami, M., Zegordi, H. Flow shop Scheduling Problem with Maintenance Coordination: a New Approach. Journal of Quality Engineering and Production Optimization, 2015; 1(1): 1-11. doi: 10.22070/jqepo.2015.184

Flow shop Scheduling Problem with Maintenance Coordination: a New Approach

^{}Department of Industrial Engineering, Tarbiat Modares University, Tehran, Iran

Abstract

This study investigates the coordination of production scheduling and maintenance planning in the flow shop scheduling environment. The problem is considered in a bi-objective form, minimizing the makespan as the production scheduling criterion and minimizing the system unavailability as the maintenance planning criterion. The time interval between consecutive maintenance activities as well as the number of maintenance activities on each machine are assumed to be non-fixed. A mixed integer programming formulation of the problem is presented. A special case of the problem, named as single server maintenance is also studied. Then, a bi-objective ant colony system algorithm is presented to solve the problem in focus. To obtain the appropriate components of the proposed algorithm, two sets of experiments are provided. Firstly, experiments are carried out to select the suitable heuristic method to build the heuristic information part of the algorithm between CDS and NEH. Secondly, experiments are reported to select the local search algorithm between iterated local search and adjacent pair-wise interchange. At last, experiments are generated to evaluate the performance of the proposed algorithm, comparing it to the results of an exhaustive search algorithm.

1. Lee C.Y. (1997)."Minimizing the makespan in the two machine flowshop scheduling problem with an availability constraint",

Operations Research Letters, 20(3) pp. 129–139.

2. Ng C.T., & Kovalyov M.Y.( 2004). "An FPTAS for scheduling a two-machine flowshop with one unavailability interval",

Naval Research Logistics , 51(3) pp. 307-315.

3. Breit J.( 2004). "An improved approximation algorithm for two-machine flow shop scheduling with an availability constraint",Information Processing Letters, vol. 90(6) pp. 273-278.

4. Allaoui H., Artiba A., Elmaghraby S.E., Riane F. (2006)."Scheduling of a two-machine flowshop with availability constraints on the first machine", International Journal of Production Economics, 99(1-) pp. 16–27.

5. Blazewicz J., Breit J., Formanowicz P., Kubiak W., & Schmidt, G.( 2001). "Heuristic algorithms for the two-machine flowshop with limited machine availability". OMEGA, The International Journal of Management Science, 29(6) pp. 599-608.

6. Kubzin M.A., Potts C.N., and Strusevich V.A.( 2009). "Approximation results for flow shop scheduling problems with machine availability constraints", Computers & Operations Research, 36(2) pp. 379-390.

7. Yang D.-L, Hsu C.-J, and Kuo W.-H.( 2008). "A two-machine flowshop scheduling problem with a separated maintenance constraint", Computers & Operations Research, 35(3) pp. 876-883.

8. Lee C.-Y.( 1999). "Two-machine flowshop scheduling with availability constraints", European Journal of Operational Research,

114(2) pp. 420-429.

9. Aggoune R.( 2004). "Minimizing the makespan for the flow shop scheduling problem with availability constraints",

European Journal of Operational Research, 153(3) pp. 534-543.

10. Aggoune R., & Portmann M.-C.( 2006). "Flow shop scheduling problem with limited machine availability: A heuristic

approach", International Journal of Production Economics, 99(1-2) pp. 4-15.

11. Choi B.-C., Lee K., Leung J.Y.-T., Pinedo M.L.( 2010)."Flow shops with machine maintenance: Ordered and proportionate cases", European Journal of Operational Research, 207 (1) pp. 97-104.

12. Schmidt G.( 2000) "Scheduling with limited machine availability", European Journal of Operational Research, 121(1) pp. 1-15.

13. Ma Y., Chu C., and Zuo C.( 2010). "A survey of scheduling with deterministic machine availability constraints",

Computers & Industrial Engineering, 58(2) pp. 199–211.

14. Berrichi A., Amodeo L., Yalaoui F., Chatelet E., & Mezghiche M.( 2009). "Bi-objective optimization algorithms for joint

production and maintenance scheduling: application to the parallel machine problem", Journal of Intelligent Manufacturing, vol.

20, pp. 389–400.

7. Yang D.-L, Hsu C.-J, and Kuo W.-H.( 2008). "A two-machine flowshop scheduling problem with a separated maintenance constraint", Computers & Operations Research, 35(3) pp. 876-883.

8. Lee C.-Y.( 1999). "Two-machine flowshop scheduling with availability constraints", European Journal of Operational Research,

114(2) pp. 420-429.

9. Aggoune R.( 2004). "Minimizing the makespan for the flow shop scheduling problem with availability constraints",

European Journal of Operational Research , 153(3) pp. 534-543.

10. Aggoune R., & Portmann M.-C.( 2006). "Flow shop scheduling problem with limited machine availability: A heuristic

approach",International Journal of Production Economics, 99(1-2) pp. 4-15.

11. Choi B.-C., Lee K., Leung J.Y.-T., Pinedo M.L.( 2010)."Flow shops with machine maintenance: Ordered and proportionate cases", European Journal of Operational Research, 207 (1) pp. 97-104.

12. Schmidt G.( 2000) "Scheduling with limited machine availability", European Journal of Operational Research, 121(1) pp. 1-15.

13. Ma Y., Chu C., and Zuo C.( 2010). "A survey of scheduling with deterministic machine availability constraints",

Computers & Industrial Engineering, 58(2) pp. 199–211.

14. Berrichi A., Amodeo L., Yalaoui F., Chatelet E., & Mezghiche M.( 2009). "Bi-objective optimization algorithms for joint

production and maintenance scheduling: application to the parallel machine problem", Journal of Intelligent Manufacturing, vol.

20, pp. 389–400.

15. Moradi E., & Zandieh M.( 2010). "Minimizing the makespan and the system unavailability in parallel machine scheduling

problem: a similarity-based genetic algorithm",

Intelligent Journal of Advanced Manufacturing Technology, vol. 51, pp. 829–

840.

16. Berrichi A., Yalaoui F., Amodeo L., & Mezghiche M.( 2010). "Bi-objective ant colony optimization approach to optimize

production and maintenance scheduling",

Computers & Operations Research, 37(9) pp. 1584–1596.

17. Moradi E., Fatemi Ghomi S.M.T., and Zandieh M.( 2011). "Bi-objective optimization research on integrated fixed time interval

preventive maintenance and production for scheduling flexible job-shop problem",

Expert Systems with Applications, 38(6) pp.

7169–7178.

18. Berrichi A. and Yalaoui F.( 2013). "Efficient bi-objective ant colony approach to minimize total tardiness and system

unavailability for a parallel machine scheduling problem",

International Journal of Advanced Manufacturing Technology, vol.

68, pp. 2295–2310.

19. Mokhtari H., Mozdgir A. & Nakhai Kamal Abadi I.( 2012). "A reliability/availability approach to joint production and

maintenance scheduling with multiple preventive maintenance services",

International Journal of Production Research, 50(20)

pp. 5906–5925.

20. Wang S. & Liu M.(2014). "Two-stage hybrid flow shop scheduling with preventive maintenance using multi-objective tabusearch method", International Journal of Production Research, 52(5) pp. 1495-1508.

21. Cui, W.-W., Lu, Z., and Pan, E.( 2014). "Integrated production scheduling and maintenance policy for robustness in a single machine", Computers & Operations Research, 47, pp. 81–91.

22. Ebeling C.E., An Introduction to Reliability and Maintainability Engineering, McGraw-Hill: USA, 1997.

23. Wilson J.M.( 1989). "Alternative formulations of a flow-shop scheduling problem", Journal of the Operational Research Society,

40(4) pp. 395–9.

24. Tseng F.T., Stafford E.F. Jr., & Gupta J.N.D.( 2004) "An empirical analysis of integer programming formulations for the permutation flowshop", Omega, 32(4) pp. 285–293.

25. Dorigo M., Optimization, Learning and Natural Algorithm. Ph.D. Thesis, DEI: Politecnico di Milano, 1992.

26. Dorigo M., and Gambardella L.M.( 1997). "Ant colony system: a cooperative learning approach to the traveling salesman problem", IEEE Transactions on Evolutionary Computation, 1(1) pp. 53–66.

27. Ying K.C., and Liao C.J.( 2003). "An ant colony system approach for scheduling problems", Production Planning & Control,

14(1), pp. 68–75.

28. Ying K., and Lin S., "Multi-heuristic desirability ant colony system heuristic for non-permutation flowshop scheduling

problems", International Journal of Advanced Manufacturing Technology, vol. 33, pp. 793–802, 2007.

29. Yagmahan B., and Yenisey M.M.( 2008). "Ant colony optimization for multi-objective flow shop scheduling problem",

Computers & Industrial Engineering, 54(3) pp. 411–420.

30. Tavares Neto R.F., and Godinho Filho M.( 2012). "Literature review regarding ant colony optimization applied to scheduling problems: guidelines for implementation and directions for future research", Engineering Applications of Artificial Intelligence, 26(1) pp. 150–161.

31. Campbell H.G., Dudek R.A., and Smith M.L. ( 1970). "A heuristic algorithm for the n job, m machine sequencing problem",

Management Science ,61(3) pp. B630–B637.

32. Nawaz M., Enscore Jr.E.E., and Ham I. ( 1983) ."A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem", Omega , 11(1) pp. 91–95.

33. Ruiz R., and Maroto C.( 2005). "A comprehensive review and evaluation of permutation flowshop heuristics", European Journal of Operational Research , 165(2) pp. 479–94.

34. Taillard E. (1993). "Benchmarks for basic scheduling problems", European Journal of Operational Research, 64(2) pp. 278–85.

35. Zitzler E., Evolutionary Algorithms for Multi-Objective Optimization: Methods and Applications. Ph.D. Thesis, Swiss Federal Institute of Technology, 1999.