A hybrid algorithm for flexible job-shop scheduling problem with setup times

Ameni Azzouz; Meriem Ennigrou; Lamjed Ben Said

doi:10.4995/ijpme.2017.6618

Authors

Ameni Azzouz Université de Tunis
Meriem Ennigrou Université de Tunis
Lamjed Ben Said Université de Tunis

DOI:

https://doi.org/10.4995/ijpme.2017.6618

Keywords:

Job-shop scheduling problem, Flexible manufacturing systems, sequence-dependent setup times, Genetic algorithms, local search

Abstract

Job-shop scheduling problem is one of the most important fields in manufacturing optimization where a set of n jobs must be processed on a set of m specified machines. Each job consists of a specific set of operations, which have to be processed according to a given order. The Flexible Job Shop problem (FJSP) is a generalization of the above-mentioned problem, where each operation can be processed by a set of resources and has a processing time depending on the resource used. The FJSP problems cover two difficulties, namely, machine assignment problem and operation sequencing problem. This paper addresses the flexible job-shop scheduling problem with sequence-dependent setup times to minimize two kinds of objectives function: makespan and bi-criteria objective function. For that, we propose a hybrid algorithm based on genetic algorithm (GA) and variable neighbourhood search (VNS) to solve this problem. To evaluate the performance of our algorithm, we compare our results with other methods existing in literature. All the results show the superiority of our algorithm against the available ones in terms of solution quality.

Downloads

Download data is not yet available.

Author Biographies

Ameni Azzouz, Université de Tunis

Lab. SOIE. Stratégies d’Optimisation et Informatique IntelligentE, ISG, Institut Supérieur de Gestion

Meriem Ennigrou, Université de Tunis

Lab. SOIE. Stratégies d’Optimisation et Informatique IntelligentE, ISG, Institut Supérieur de Gestion

Lamjed Ben Said, Université de Tunis

Lab. SOIE. Stratégies d’Optimisation et Informatique IntelligentE, ISG, Institut Supérieur de Gestion

References

Allahverdi, A. (2015). The third comprehensive survey on scheduling problems with setup times/costs. European Journal of Operational Research, 246(2), 345-378. https://doi.org/10.1016/j.ejor.2015.04.004

Azzouz, A., Ennigrou, M., Jlifi, B. (2015). Diversifying TS using GA in Multi-Agent System for solving Flexible Job Shop Problem. In Proceedings of the 12th International Conference on Informatics in Control, Automation and Robotics, 94-101. https://doi.org/10.5220/0005511000940101

Azzouz, A., Ennigrou, M., Jlifi, B., Ghedira, K. (2012). Combining Tabu Search and Genetic Algorithm in a Multi-agent System for Solving Flexible Job Shop Problem. In Artificial Intelligence (MICAI), 2012, 11th Mexican International Conference on, pp. 83-88. IEEE.https://doi.org/10.1109/micai.2012.12

Bagheri, A., Zandieh, M. (2011). Bi-criteria flexible job-shop scheduling with sequence-dependent setup times Variable neighborhood search approach. Journal of Manufacturing Systems, 30(1), 8-15. https://doi.org/10.1016/j.jmsy.2011.02.004

Brandimarte, P. (1993). Routing and scheduling in a flexible job shop by tabu search. Journal Annals of Operations Research, 41(3), 157-183. https://doi.org/10.1007/bf02023073

Cheung, W., Zhou, H. (2001). Using genetic algorithms and heuristics for job shop scheduling with sequence-dependent setup times. Annals of Operations Research, 107(1), 65-81. https://doi.org/10.1023/A:1014990729837

Fattahi, P., Saidi-Meradbad, M., Jolai, F. (2007). Mathematical Modeling and heuristic approaches to flexible job shop scheduling problems. Journal of intelligent manufacturing,18(3), 331-342. https://doi.org/10.1007/s10845-007-0026-8

González, M. A., Rodriguez Vela, C., Varela, R. (2013). An efficient memetic algorithm for the flexible job shop with setup times. In Twenty-Third International Conference on Automated, pp. 91-99.

Hurink, J., Jurisch, B., Thole, M. (1994). Tabu search for the job-shop scheduling problem with multi-purpose machines. Operations-Research-Spektrum, 15(4), 205-215. https://doi.org/10.1007/BF01719451

Imanipour, N. (2006). Modeling solving flexible job shop problem with sequence dependent setup times. International Conference on Service Systems and Service Management. IEEE,2, 1205-1210. https://doi.org/10.1109/icsssm.2006.320680

Kim, S.C., Bobrowski, P.M. (1994). Impact of sequence-dependent setup time on job shop scheduling performance. The International Journal of Production Research,32(7), 1503-1520. https://doi.org/10.1080/00207549408957019

Moghaddas, R., Houshmand, M. (2008). Job-shop scheduling problem with sequence dependent setup times. Proceedings of the International MultiConference of Engineers and Computer Scientists,2, 978-988.

Mousakhani, M. (2013). Sequence-dependent setup time flexible job shop scheduling problem to minimise total tardiness. International Journal of Production Research,51(12), 3476-3487. https://doi.org/10.1080/00207543.2012.746480

Naderi, B., Zandieh, M., Ghomi, S.F. (2009). Scheduling sequence-dependent setup time job shops with preventive maintenance. The International Journal of Advanced Manufacturing Technology,43, 170-181. https://doi.org/10.1007/s00170-008-1693-0

Najid, N.M., Dauzere-Peres, S., Zaidat, A. (2002). A modified simulated annealing method for flexible job shop scheduling problem. In proceedings of the IEEE International Conference on Systems, Man and Cybernetics,5, 6-9. https://doi.org/10.1109/icsmc.2002.1176334

Nouiri, M., Bekrar, A., Jemai, A., Niar, S., Ammari, A. C. (2015). An effective and distributed particle swarm optimization algorithm for flexible job-shop scheduling problem. Journal of Intelligent Manufacturing, 1-13. https://doi.org/10.1007/s10845-015-1039-3

Oddi, A., Rasconi, R., Cesta, A., & Smith, S. (2011). Applying iterative flattening search to the job shop scheduling problem with alternative resources and sequence dependent setup times. In COPLAS 2011 Proceedings of the Workshopon Constraint Satisfaction Techniques for Planning and Scheduling Problems, pp. 15-22.

Pezzella, F., Morganti, G., Ciaschetti, G. (2008). A genetic algorithm for the flexible job-shop scheduling problem. Computers & Operations Research,35(10), 3202-3212. https://doi.org/10.1016/j.cor.2007.02.014R

ossi, A. (2014). Flexible job shop scheduling with sequence-dependent setup and transportation times by ant colony with reinforced pheromone relationships. International Journal of Production Economics,153, 253-267. https://doi.org/10.1016/j.ijpe.2014.03.006

Sadrzadeh, A. (2013). Development of both the AIS and PSO for solving the flexible job shop scheduling problem. Arabian Journal for Science and Engineering,38(12), 3593-3604. https://doi.org/10.1007/s13369-013-0625-y

Saidi-Mehrabad, M., Fattahi, P. (2007). Flexible job shop scheduling with tabu search algorithms. The International Journal of Advanced Manufacturing Technology,32(5), 563-570. https://doi.org/10.1007/s00170-005-0375-4

Vilcot, G., Billaut, J.C. (2011). A tabu search algorithm for solving a multicriteria flexible job shop scheduling problem. International Journal of Production Research,49(23), 6963-6980. https://doi.org/10.1080/00207543.2010.526016

Wang, S.J., Zhou, B.H., Xi, L.F. (2008). A filtered-beam-search-based algorithm for flexible job-shop scheduling problem. International Journal of Production Research,46(11), 3027-3058. https://doi.org/10.1080/00207540600988105

Wang, S., Yu, J. (2010). An effective heuristic for flexible job-shop scheduling problem with maintenance activities. Computers and Industrial Engineering, 59(3), 436-447. https://doi.org/10.1016/j.cie.2010.05.016

Yazdani, M., Gholami, M., Zandieh, M., Mousakhani, M. (2009). A Simulated Annealing Algorithm for Flexible Job-Shop Scheduling Problem. Journal of Applied Sciences,9(4), 662-670. https://doi.org/10.3923/jas.2009.662.670

Zambrano Rey, G., Bekrar, A., Prabhu, V., Trentesaux, D. (2014). Coupling a genetic algorithm with the distributed arrival-time control for the JIT dynamic scheduling of flexible job-shops. International Journal of Production Research,52(12), 3688-3709. https://doi.org/10.1080/00207543.2014.881575

Zhang, G., Gao, L., Shi, Y. (2011). An effective genetic algorithm for the flexible job-shop scheduling problem. Expert Systems with Applications, 38(4), 3563-3573. https://doi.org/10.1016/j.eswa.2010.08.145

Zhang, G., Shao, X., Li, P., Gao, L. (2009). An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem. Computers and Industrial Engineering,56(4), 1309-1318. https://doi.org/10.1016/j.cie.2008.07.021

Zhou, Y., Beizhi, L., Yang, J. (2006). Study on job shop scheduling with sequence-dependent setup times using biological immune algorithm. The International Journal of Advanced Manufacturing Technology,30(1), 105-111. https://doi.org/10.1007/s00170-005-0022-0

Ziaee, M. (2014). A heuristic algorithm for solving flexible job shop scheduling problem. The International Journal of Advanced Manufacturing Technology,71(1), 519-528 https://doi.org/10.1007/s00170-013-5510-z

Zribi, N., Kacem, I., El Kamel, A., Borne, P. (2007). Assignment and scheduling in flexible job-shops by hierarchical optimization. In Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE (4), 652-661. https://doi.org/10.1109/TSMCC.2007.897494