Three Hybrid Metaheuristic Algorithms for Stochastic Flexible Flow Shop Scheduling Problem with Preventive Maintenance and Budget Constraint
Subject Areas : Business and MarketingSadigh Raissi 1 , Ramtin Rooeinfar 2 , Vahid Reza Ghezavati 3
1 - School of Industrial Engineering, South Tehran Branch, Islamic Azad University, Tehran, Iran
2 - School of Industrial Engineering, South Tehran Branch, Islamic Azad University, Tehran, Iran
3 - School of Industrial Engineering, South Tehran Branch, Islamic Azad University, Tehran, Iran
Keywords: Genetic Algorithm, Budget constraint, Particle Swarm Optimization, Simulated Annealing, Preventive maintenance, Stochastic flexible flow shop,
Abstract :
Stochastic flexible flow shop scheduling problem (SFFSSP) is one the main focus of researchers due to the complexity arises from inherent uncertainties and also the difficulty of solving such NP-hard problems. Conventionally, in such problems each machine’s job process time may encounter uncertainty due to their relevant random behaviour. In order to examine such problems more realistically, fixed interval preventive maintenance (PM) and budget constraint are considered.PM activity is a crucial task to reduce the production efficiency. In the current research we focused on a scheduling problem which a job is processed at the upstream stage and all the downstream machines get busy or alternatively PM cost is significant, consequently the job waits inside the buffers and increases the associated holding cost. This paper proposes a new more realistic mathematical model which considers both the PM and holding cost of jobs inside the buffers in the stochastic flexible flow shop scheduling problem. The holding cost is controlled in the model via the budget constraint. In order to solve the proposedmodel, three hybrid metaheuristic algorithms are introduced. They include a couple of well-known metaheuristic algorithms which have efficient quality solutions in the literature. The two algorithms of them constructed byincorporationof the particle swarm optimization algorithm (PSO) and parallel simulated annealing (PSA) methods under different random generation policies. The third one enriched based on genetic algorithm (GA) with PSA. To evaluate the performance of the proposed algorithms, different numerical examples are presented. Computational experiments revealed that the proposed algorithms embedboth desirable accuracy and CPU time. Among them, the PSO-PSAП outperforms than other algorithms in terms of makespan and CPU time especially for large size problems.
Akrami, B., Karimi, B., Hosseini, S.M.M., (2006). Two metaheuristic methods for the common cycle economic lot sizing and scheduling in flexible flow shops with limited intermediate buffers: the finite horizon case.Applied Mathematics and Computation, 183, 634- 645.
Al-Hinai, N., ElMekkawy, T.Y., (2011). Robust and stable flexible job shop scheduling with random machine breakdowns using a hybrid genetic algorithm.International Journal of Production Economics, 132, 279-291.
Almeder, C., Hartl, R.F., (2013). A metaheuristic optimization approach for a real-world stochastic flexible flow shop problem with limited buffer.International Journal of Production Economics, 145, 88-95.
Arnaout, J.P., (2014). Rescheduling of parallel machines with stochastic processing and setup times.Journal of Manufacturing Systems, 33 (3), 376-384.
[5]Brucker, P., Kramer, B., (1995). Shop scheduling problems with multiprocessor tasks on dedicated processors. Annals of Operations Research, 50, 13–27.
Choi, S.H., Wang, K., (2012). Flexible flow shop scheduling with stochastic processing times: A decomposition-based approach.Computers & Industrial Engineering, 63, 362-373.
Fahmy, S.A., Sherif, A., Balakrishnan, S., ElMekkawy, T.Y., (2009). A generic deadlock-free reactive scheduling approach.International Journal of Production Research, 47 (20), 5657-5676.
González-Neira, E.M., García-Cáceres, R.G., Cabellero-Villalobos, J.P., Molina-Sánchez, L.P., Montoya-Torres, J.R., (2016). Stochastic flexible flow shop scheduling problem under quantitative and qualitative decision criteria.Computer and Industrial Engineering, 101, 128-144.
Gupta J.N.D., (1988). Two stage hybrid flow shop scheduling problem. Journal of Operational Research Society, 39(4), 359-64.
Hoogeveen, J.A., Lenstra, J.K., Veltman, B., (1996). Minimizing the makespan in a multiprocessor flow shop is strongly NP-hard. European Journal of Operational Research, 89, 172-175.
Kennedy, J., Eberhart,R.C.,(1995). Particle swarm optimization.Proceeding of IEEE International Conference on Neural Network, Piscataway: IEEE 4, 1942-1948.
Kianfar, K., Fatemi Ghomi, S.M.T., Oroojlooy Jadid, A., (2012). Study of stochastic sequence-dependent flexible flow shop via developing a dispatching rule and a hybrid GA.Engineering Applications of Artificial Intelligence, 25, 494-506.
Koulamas, C., Kyparisis, G.J., (2000). Scheduling on uniform parallel machines to minimize maximum lateness.Operations Research Letters, 24(6),175-179.
Li, J.Q., Pan, Q.K., (2015). Solving the large-scale hybrid flow shop scheduling problem with limited buffers by a hybrid artificial bee colony algorithm. Information Sciences, 316:487–502.
Lin, SW., Ying, K.C., (2013). Minimizing makespan in a blocking flowshop using a revised artificial immune system algorithm.Omega, 2 (4), 383-389.
Lin, J.T., Chen, C.M., (2015). Simulation optimization approach for hybrid flow shop scheduling problem in semiconductor back-end manufacturing.Simulation Modeling Practice and Theory, 51, 100-114.
Montgomery, D.C. (2005). Design and analysis of experiments. Arizona, John Wiley and Sons.
Norman, B.A., Bean, J.C., (1999). A genetic algorithm methodology for complex scheduling problems. Naval Research. Logistics, 46: 199-211.
Osman, I.H., Kelly, J.P., (1996). Metaheuristics: an overview. Metaheuristics: theory and applications. Boston: Kluwer Academic Publisher, 1-21.
Pinedo, M., Chao, X., (1999). Operations scheduling with applications inmanufacturing and services. New York: McGraw-Hill.
Pinedo, M., (2002). Scheduling theory, algorithms, and systems. Englewood Cliffs, New Jersey: Prentice-Hall. Chapter 2.
Poli, R., Kennedy, G., Blackwell, T., (2007). Particle swarm optimization: an overview. Swarm Intelligence, 1(3), 33-57.
Rabiee, M., Sadeghi Rad, R., Mazinani, M., Shafaei, R., (2014). An intelligent hybrid metaheuristic for solving a case of no-wait two-stage flexible flow shop scheduling problem with unrelated parallel machine.International Journal of Advanced Manufacturing Technology, 71: 1229-1245.
Rahmani, D., Heydari, M., (2014). Robust and stable flow shop scheduling with unexpected arrivals of new jobs and uncertain processing times. Original Research Article, 33 (1), 84-92.
Rahmani, D., Ramezanian, R., (2016). A stable reactive approach in dynamic flexible flow shop scheduling with unexpected disruptions: A case study. Computers & Industrial Engineering, 98, 360-372.
Sangsawang, C., Sethanan, K., Fujimoto, T., Gen, M., (2015). Metaheuristics optimization approaches for two-stage reentrant flexible flow shop with blocking constraint.Expert Systems with Applications, 42, 2395–2410.
Singh, M.R., Mahapatra, S.S., (2012). A swarm optimization approach for flexible flow shop scheduling with multiprocessor tasks.International Journal of Advanced Manufacturing Technology, 62: 267-277.
Sukkerd, W., Wuttipornpun, T., (2016). Hybrid genetic algorithm and tabu search for finite capacity material requirement planning system in flexible flow shop with assembly operations. Computers & Industrial Engineering, 97, 157- 169.
Tang, D., Dai, M., Salido, M.A, Giret, A., (2016). Energy-efficient dynamic scheduling for a flexible flow shop using an improved particle swarm optimization. Computers in Industry, 81, 82–95.
Tran, T.H., Ng, K.M. (2011). A water flow algorithm for flexible flow shop scheduling with intermediate buffers.Journal of Scheduling, 14, 483-500.
Villemeur, A., (1991). Reliability, availability, maintainability and safety assessment. USA: Wiley.
Wang, X., Tang, L., (2009). A Tabu search heuristic for the hybrid flowshop scheduling with finite intermediate buffers. Computers & Operations Research, 36 (3), 907–918.
Wang, K., Choi, S.H., (2014). A holonic approach to flexible flow shop scheduling under stochastic processing times.Computers & Operations Research, 43, 157-168.
Wardono, B., Fathi, Y., (2004). A Tabu search algorithm for multi-stage parallel machine problem with limited buffer capacities. European Journal of Operational Research, 155 (2), 380-401.
Zabihzadeh, S.R., Rezaeian, J., (2015). Two metaheuristic algorithms for flexible flow shop scheduling problem with robotic transportation and release time. Applied Soft Computing, 40, 319-330