A Bi-objective Model for a Flowshop Scheduling Problem with Availability Constraint of Machines

Document Type : Research Paper

Authors

Abstract

 This paper presents a new bi-objective mathematical model for a permutation flowshop scheduling problem with availability constraint in case of preventive maintenance operations on machines. In this paper, preventive maintenance is flexible and there is not a certain time for the maintenance operation; however, time between two consecutive maintenance operations for each machine should not be greater than a given time. The model has two objectives; (1) minimizing the makespan (i.e., Cmax) and, (2) minimizing the sum of earliness and tardiness simultaneously. This study reports the results obtained by the Reservation Level Tchebycheff Procedure (RLTP) and the ε-constraint method for solving a case study problem. The results show high quality of reached solutions from RLTP in comparison with the ε-constraint method.

Keywords


1. Pinedo, M. (2008). Scheduling: Theory, Algorithms, and Systems. 3rd. Ed. Springer, New York.
2. Ma, Y., Chu, C., and Zuo, C. (2010). “A survey of scheduling with deterministic machine availability constraints.” Computers & Industrial Engineering, Vol 58, No. 2, 199–211.
3. Lee, C.- Y. (1997). “Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint.” Operations Research Letters, Vol. 20, No. 3, 129–139.
4. Allaoui, H., Artiba, A., Elmaghrabyb, S. E., and Rianea, F. (2006). “Scheduling of a two-machine flowshop with availability constraints on the first machine.” International Journal of Production Economics, Vol. 99, No. (1–2), 16–27.
5. Breit, J. (2004). “An improved approximation algorithm for two-machine flow shop scheduling with an availability constraint.” Information Processing Letters, Vol. 90, No. 6, 273–278.
6. Ng, C. T. and Kovalyov, M. Y. (2004). “An FPTAS for scheduling a two-machine flowshop with one unavailability interval.” Naval Research Logistics (NRL), Vol. 51, No. 3, 307–315.
7. Wang, X. and Edwin Cheng, T. C. (2007). “Heuristics for two-machine flowshop scheduling with setup times and an availability constraint.” Computers & Operations Research, Vol. 34, No. 1, 152–162.
8. Lee, C.- Y. (1999). “Two-machine flowshop scheduling with availability constraints.” European Journal of Operational Research, Vol. 114, No. 2, 420–429.
9. Cheng, T. C. E. and Liu, Z. (2003). “Approximability of two-machine no-wait flowshop scheduling with availability constraints.” Operations Research Letters, Vol. 31, No. 4, 319–322.
10. Allaoui, H. and Artiba, A. (2014). “Hybrid Flow Shop Scheduling with Availability Constraints.” International Series in Operations Research & Management Science, Vol. 200, 277–299.
11. Espinouse, M. L., Formanowicz, P., and Penz, B. (1999). “Minimizing the makespan in the two-machine no-wait flow-shop with limited machine availability.” Computers & Industrial Engineering, Vol. 37, No. (1–2), 497–500.
12. Espinouse, M. L., Formanowicz, P., and Penz, B. (2001). “Complexity Results and Approximation Algorithms for the Two Machine No-Wait Flow-Shop with Limited Machine Availability.” The Journal of the Operational Research Society, Vol. 52, No. 1, 116–121.
13. Wang, G. and Cheng, T. C. E. (2001). “Heuristics for two-machine no-wait flowshop scheduling with an availability constraint.” Information Processing Letters, Vol. 80, No. 6, 305–309.
14. Kubzin, M. A. and Strusevich, V. A. (2004). “Two-machine flow shop no-wait scheduling with a nonavailability interval.” Naval Research Logistics (NRL), Vol. 51, No. 4, 613–631.
15. Aggoune, R. (2004). “Minimizing the makespan for the flow shop scheduling problem with availability constraints.” European Journal of Operational Research, Vol. 153, No. 3, 534–543.
16. Aggoune, R. and Portmann, M. -C. (2006). “Flow shop scheduling problem with limited machine availability: A heuristic approach.” International Journal of Production Economics, Vol. 99, No. (1–2), 4–15.
17. Minella, G.,  Ruiz, R., and Ciavotta, M. (2008). “A review and evaluation of multiobjective algorithms for the flowshop scheduling problem.” INFORMS Journal on Computing, Vol. 20, No. 3, 451–471.
18. Mokhtaria, H., Nakhai Kamal Abadia, I., and Cheraghalikhanib, A. (2011). “A multi-objective flow shop scheduling with resource-dependent processing times: trade-off between makespan and cost of resources.” International Journal of Production Research, Vol. 49, No. 19, 5851–5875.
19. Frosolinia, M., Bragliaa, M., and Zammoria, F. A. (2011). “A modified harmony search algorithm for the multi-objective flowshop scheduling problem with due dates.” International Journal of Production Research, Vol. 49, No. 20, 5957–5985.
20. Khalili, M. and Tavakkoli-Moghaddam, R. (2012). “A multi-objective electromagnetism algorithm for a bi-objective flowshop scheduling problem.” Journal of Manufacturing Systems, Vol. 31, No. 2, 232–239.
21. Reeves, G. R. and MacLeod, K. R. (1999). “Some experiments in Tchebycheff-based approaches for interactive multiple objective decision making.” Computers and Operations Research, Vol. 26, No. 13, 1311–1321.
22. Steuer, R. E. (1986). Multiple criteria optimization: theory, computation, and application. Wiley, New York.
23. Haimes, Y. Y., Wismer, D. A., and Lasdon, D. S. (1971). “On bicriterion formulation of the integrated systems identification and system optimization.” IEEE Transactions on Systems, Man and Cybernetics, Vol. SMC-1, No. 3, 296–97.