Multi-objective optimization of integrated lot-sizing and scheduling problem in flexible job shops

Rohaninejad, Mohammad; Sahraeian, Rashed; Nouri, Behdin Vahedi

doi:10.1051/ro/2015049

Rohaninejad, Mohammad ¹ ; Sahraeian, Rashed ¹ ; Nouri, Behdin Vahedi ²

¹ Department of Industrial Engineering, Faculty of Engineering, Shahed University, Tehran, Iran.
² Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran.

RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 3, pp. 587-609.

Résumé

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.

Reçu le : 2015-03-31
Accepté le : 2015-10-21

MR Zbl

DOI : 10.1051/ro/2015049

Classification : 90B30, 90B05, 68T20, 90B50
Mots clés : Lot-sizing, scheduling, flexible job shop, genetic algorithm, particle swarm optimization algorithm, TOPSIS

Affiliations des auteurs :

Rohaninejad, Mohammad ¹ ; Sahraeian, Rashed ¹ ; Nouri, Behdin Vahedi ²

@article{RO_2016__50_3_587_0,
     author = {Rohaninejad, Mohammad and Sahraeian, Rashed and Nouri, Behdin Vahedi},
     title = {Multi-objective optimization of integrated lot-sizing and scheduling problem in flexible job shops},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {587--609},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {3},
     year = {2016},
     doi = {10.1051/ro/2015049},
     mrnumber = {3538842},
     zbl = {1351.90100},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2015049/}
}

TY  - JOUR
AU  - Rohaninejad, Mohammad
AU  - Sahraeian, Rashed
AU  - Nouri, Behdin Vahedi
TI  - Multi-objective optimization of integrated lot-sizing and scheduling problem in flexible job shops
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2016
SP  - 587
EP  - 609
VL  - 50
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2015049/
DO  - 10.1051/ro/2015049
LA  - en
ID  - RO_2016__50_3_587_0
ER  -

%0 Journal Article
%A Rohaninejad, Mohammad
%A Sahraeian, Rashed
%A Nouri, Behdin Vahedi
%T Multi-objective optimization of integrated lot-sizing and scheduling problem in flexible job shops
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2016
%P 587-609
%V 50
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2015049/
%R 10.1051/ro/2015049
%G en
%F RO_2016__50_3_587_0

Rohaninejad, Mohammad; Sahraeian, Rashed; Nouri, Behdin Vahedi. Multi-objective optimization of integrated lot-sizing and scheduling problem in flexible job shops. RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 3, pp. 587-609. doi : 10.1051/ro/2015049. http://www.numdam.org/articles/10.1051/ro/2015049/

Bibliographie
Cité par

N. Absi and S. Kedad-Sidhoum, MIP-based heuristics for multi-item capacitated lot-sizing problem with setup times and shortage costs. RAIRO: OR 41 (2007) 171–192. | DOI | Numdam | MR | Zbl

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. | DOI | MR | Zbl

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

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. | DOI | Zbl

K. Deb, Multi-objective Optimization Using Evolutionary Algorithms. Vol. 2012. John Wiley & Sons, Chichester (2001). | MR | Zbl

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

S. Deleplanque, S. Kedad-Sidhoum and A. Quilliot, Lagrangean Heuristic for a Multi–Plant Lot–Sizing Problem with Transfer and Storage Capacities. RAIRO: OR 47 (2013) 429–443. | DOI | Numdam | MR | Zbl

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

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

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

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

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. | DOI | MR | Zbl

C.L. Hwang and K. Yoon, Multiple Attributes Decision Making. Lect. Notes Econ. Math. Syst. Springer, Heidelberg (1981). | MR | Zbl

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. | DOI | MR | Zbl

W. Kaczmarczyk, Proportional lot-sizing and scheduling problem with identical parallel machines. Int. J. Prod. Res. 49 (2011) 2605–2623. | DOI

B. Karimi, S.M.T. Fatemi Ghomi and J.M. Wilson, The capacitated lot sizing problem: a review of models and algorithms. Omega 31 (2003) 365–378. | DOI

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

U.S. Karmarkar and L. Schrage, The deterministic dynamic product cycling problem. Oper. Res. 33 (1985) 326–345. | DOI | Zbl

A.H. Kashan and B. Karimi, A discrete particle swarm optimization algorithm for scheduling parallel machines. Comput. Ind. Eng. 56 (2009) 216–223. | DOI

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

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. | DOI | Zbl

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.

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

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. | DOI | MR | Zbl

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. | DOI | MR | Zbl

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. | DOI

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

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.

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

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. | Zbl

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. | DOI | MR | Zbl

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

H. Stadtler, Multi-level single machine lot-sizing and scheduling with zero lead times. Eur. J. Oper. Res., 209 (2011) 241–252. | DOI | MR | Zbl

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. | DOI | MR | Zbl

C.J. Wu and M.S. Hamada, Experiments: Planning, Analysis, and Optimization. Wiley (2011). | Zbl

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

E. Zitzler, M. Laumanns and L. Theile, SPEA2: Improving the strength Pareto evolutionary algorithm. Technical Report (2001).

Cité par Sources :