Multi-objective optimization of integrated lot-sizing and scheduling problem in flexible job shops. (English) Zbl 1351.90100
Summary: This paper investigates a particular integrated lotsizing and scheduling problem in a multi-level multi-product, multi-machine and flexible routes environment that is called flexible job shop problem (FJSP). The considered problem involves making simultaneous decision in sequencing operations, sizing lots and assigning machines to operations in order to optimize a multi-objective function including minimizing sum of the system costs, total machines workload and makespan, while a given demand is fulfilled without backlogging. Due to the complexity of the problem, a hybrid meta-heuristic based on a combination of Genetic algorithm and particle swarm optimization algorithm is developed to solve it. Additionally, the Taguchi method is employed to calibrate the influential parameters of the meta-heuristic and boost its capabilities. Finally, the performance of the proposed algorithm is compared with some well-known multi-objective algorithms such as NSGAII, SPEA2 and VEGA. Regarding to the computational results, the hybrid algorithm surpasses the other algorithms in the closeness of solutions to pareto optimal front and diversity criteria.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90B30 | Production models |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | N. Absi and S. Kedad-Sidhoum, MIP-based heuristics for multi-item capacitated lot-sizing problem with setup times and shortage costs. RAIRO: OR41 (2007) 171-192. · Zbl 1190.90062 · doi:10.1051/ro:2007014 |
| [2] | B. Akrami, B. Karimi and Moattar S.M. Hosseini, Two metaheuristic methods for the common cycle economic lot sizing and scheduling in flexible flow shops with limited intermediate buffers: The finite horizon case. Appl. Math. Comput.183 (2006) 634-645. · Zbl 1127.90348 |
| [3] | S. Arabameri and N. Salmasi, Minimization of weighted earliness and tardiness for no-wait sequence-dependent setup times flowshop scheduling problem. Comput. Ind. Eng.64 (2013) 902-916. · doi:10.1016/j.cie.2012.12.023 |
| [4] | P. Beraldi, G. Ghiani, A. Grieco and E. Guerriero, Rolling-horizon and fix-and-relax heuristics for the parallel machine lot-sizing and scheduling problem with sequence-dependent set-up costs. Comput. Oper. Res.35 (2008) 3644-3656. · Zbl 1170.90386 · doi:10.1016/j.cor.2007.04.003 |
| [5] | K. Deb, Multi-objective Optimization Using Evolutionary Algorithms. Vol. 2012. John Wiley & Sons, Chichester (2001). · Zbl 0970.90091 |
| [6] | K. Deb, A. Pratap, S. Agarwal and T.A.M.T. Meyarivan, A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput.6 (2002) 182-197. · doi:10.1109/4235.996017 |
| [7] | S. Deleplanque, S. Kedad-Sidhoum and A. Quilliot, Lagrangean Heuristic for a Multi-Plant Lot-Sizing Problem with Transfer and Storage Capacities. RAIRO: OR47 (2013) 429-443. · Zbl 1282.90027 · doi:10.1051/ro/2013050 |
| [8] | C.Y. Dye and L.Y. Ouyang, A particle swarm optimization for solving joint pricing and lot-sizing problem with fluctuating demand and trade credit financing. Comput. Ind. Eng.60 (2011) 127-137. · doi:10.1016/j.cie.2010.10.010 |
| [9] | G. Fandel and C. Stammen-Hegene, Simultaneous lot sizing and scheduling for multi-product multi-level production. Int. J. Prod. Econ.104 (2006) 308-316. · doi:10.1016/j.ijpe.2005.04.011 |
| [10] | E.D. Gómez Urrutia, R. Aggoune and S. Dauzère-Pérès, Solving the integrated lot-sizing and job-shop scheduling problem. Int. J. Prod. Res.52 (2014) 5236-5254. · doi:10.1080/00207543.2014.902156 |
| [11] | K. Haase and A. Kimms, Lot sizing and scheduling with sequence-dependent setup costs and times and efficient rescheduling opportunities. Int. J. Prod. Econ.66 (2000) 159-169. · doi:10.1016/S0925-5273(99)00119-X |
| [12] | Y. Han, J. Tang, I. Kaku and L. Mu, Solving uncapacitated multilevel lot-sizing problems using a particle swarm optimization with flexible inertial weight. Comput. Math. Appl.57 (2009) 1748-1755. · Zbl 1186.90009 · doi:10.1016/j.camwa.2008.10.024 |
| [13] | C.L. Hwang and K. Yoon, Multiple Attributes Decision Making. Lect. Notes Econ. Math. Syst. Springer, Heidelberg (1981). |
| [14] | M. Jenabi, S.M.T. FatemiGhomi, S.A. Torabi and B. Karimi, Two hybrid meta-heuristics for the finite horizon ELSP in flexible flow lines with unrelated parallel machines. Appl. Math. Comput.186 (2007) 230-245. · Zbl 1127.90029 |
| [15] | W. Kaczmarczyk, Proportional lot-sizing and scheduling problem with identical parallel machines. Int. J. Prod. Res.49 (2011) 2605-2623. · doi:10.1080/00207543.2010.532929 |
| [16] | B. Karimi, S.M.T. Fatemi Ghomi and J.M. Wilson, The capacitated lot sizing problem: a review of models and algorithms. Omega31 (2003) 365-378. · doi:10.1016/S0305-0483(03)00059-8 |
| [17] | M. Karimi-Nasab, S.M. Seyedhoseini, M. Modarres and M. Heidari, Multi-period lot sizing and job shop scheduling with compressible process times for multilevel product structures. Int. J. Prod. Res.51 (2013) 6229-6246. · doi:10.1080/00207543.2013.825743 |
| [18] | U.S. Karmarkar and L. Schrage, The deterministic dynamic product cycling problem. Oper. Res.33 (1985) 326-345. · Zbl 0571.90038 · doi:10.1287/opre.33.2.326 |
| [19] | A.H. Kashan and B. Karimi, A discrete particle swarm optimization algorithm for scheduling parallel machines. Comput. Ind. Eng.56 (2009) 216-223. · doi:10.1016/j.cie.2008.05.007 |
| [20] | A. Kovács, K.N. Brown and S.A. Tarim, An efficient MIP model for the capacitated lot-sizing and scheduling problem with sequence-dependent setups. Int. J. Prod. Econ.118 (2009) 282-291. · doi:10.1016/j.ijpe.2008.08.033 |
| [21] | J. Maes, J.O. McClain and L.N. Van Wassenhove, Multilevel capacitated lot-sizing complexity and LP-based heuristics. Eur. J. Oper. Res.53 (1991) 131-148. · Zbl 0734.90036 · doi:10.1016/0377-2217(91)90130-N |
| [22] | M. Mahdieh, M. Bijari and A. Clark, Simultaneous Lot Sizing and Scheduling in a Flexible Flow Line. J. Ind. Syst. Eng.5 (2011) 107-119. |
| [23] | C. Oztürk and A.M. Ornek, Capacitated lot sizing with linked lots for general product structures in job shops. Comput. Ind. Eng.58 (2010) 151-164. · doi:10.1016/j.cie.2009.10.002 |
| [24] | S. Petrovic, C. Fayad, D. Petrovic, E. Burke and G. Kendall, Fuzzy job shop scheduling with lot-sizing. Ann. Oper. Res.159 (2008) 275-292. · Zbl 1152.90476 · doi:10.1007/s10479-007-0287-9 |
| [25] | R. Ramezanian and M. Saidi-Mehrabad, Hybrid simulated annealing and MIP-based heuristics for stochastic lot-sizing and scheduling problem in capacitated multi-stage production system. Appl. Math. Model.37 (2013) 5134-5147. · Zbl 1426.90132 · doi:10.1016/j.apm.2012.10.024 |
| [26] | R. Ramezanian, M. Saidi-Mehrabad and P. Fattahi, MIP formulation and heuristics for multi-stage capacitated lot-sizing and scheduling problem with availability constraints. J. Manufact. Syst.32 (2013) 392-401. · Zbl 1426.90132 · doi:10.1016/j.jmsy.2013.01.002 |
| [27] | R. Ramezanian, M. Saidi-Mehrabad and P. Fattahi, Integrated lot-sizing and scheduling with overlapping for multi-level capacitated production system. Int. J. Comput. Integr. Manufact.26 (2013) 681-695. · doi:10.1080/0951192X.2012.749534 |
| [28] | M. Rohaninejad, A. Kheirkhah, P. Fattahi and B. Vahedi-Nouri, A hybrid multi-objective genetic algorithm based on the ELECTRE method for a capacitated flexible job shop scheduling problem. Int. J. Adv. Manufact. Technol. (2014) 1-16. |
| [29] | M. Rohaninejad, A.S. Kheirkhah, B. Vahedi Nouri and P. Fattahi, Two hybrid tabu search-firefly algorithms for the capacitated job shop scheduling problem with sequence-dependent setup cost. Int. J. Comput. Integr. Manufact.28 (2015) 470-487. · doi:10.1080/0951192X.2014.880808 |
| [30] | J.D. Schaffer, Multiple objective optimization with vector evaluated genetic algorithms. In Proc. of the 1st international Conference on Genetic Algorithms. L. Erlbaum Associates Inc. (1985) 93-100. |
| [31] | F. Seeanner, B. Almada-Lobo and H. Meyr, Combining the principles of variable neighborhood decomposition search and the fix & optimize heuristic to solve multi-level lot-sizing and scheduling problems. Comput. Oper. Res.40 (2013) 303-317. · Zbl 1349.90046 · doi:10.1016/j.cor.2012.07.002 |
| [32] | R. Sikora, A genetic algorithm for integrating lot-sizing and sequencing in scheduling a capacitated flow line. Comput. Ind. Eng.30 (1996) 969-981. · doi:10.1016/0360-8352(96)00046-0 |
| [33] | H. Stadtler, Multi-level single machine lot-sizing and scheduling with zero lead times. Eur. J. Oper. Res., 209 (2011) 241-252. · Zbl 1205.90112 · doi:10.1016/j.ejor.2010.09.022 |
| [34] | A. Weidenhiller and H. Jodlbauer, Equivalence classes of problem instances for a continuous-time lot sizing and scheduling problem. Eur. J. Oper. Res.199 (2009) 139-149. · Zbl 1176.90251 · doi:10.1016/j.ejor.2008.11.006 |
| [35] | C.J. Wu and M.S. Hamada, Experiments: Planning, Analysis, and Optimization. Wiley (2011). · Zbl 0964.62065 |
| [36] | F. Zhao, J. Tang, J. Wang and J. Jonrinaldi, An improved particle swarm optimisation with a linearly decreasing disturbance term for flow shop scheduling with limited buffers. Int. J. Comput. Integr. Manufact.27 (2014) 488-499. · doi:10.1080/0951192X.2013.814165 |
| [37] | E. Zitzler, M. Laumanns and L. Theile, SPEA2: Improving the strength Pareto evolutionary algorithm. Technical Report (2001). |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
