Top

Journal of Intelligent Manufacturing

Published in:

05-02-2015

An effective and distributed particle swarm optimization algorithm for flexible job-shop scheduling problem

Authors: Maroua Nouiri, Abdelghani Bekrar, Abderezak Jemai, Smail Niar, Ahmed Chiheb Ammari

Published in: Journal of Intelligent Manufacturing | Issue 3/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Flexible job-shop scheduling problem (FJSP) is very important in many research fields such as production management and combinatorial optimization. The FJSP problems cover two difficulties namely machine assignment problem and operation sequencing problem. In this paper, we apply particle swarm optimization (PSO) algorithm to solve this FJSP problem aiming to minimize the maximum completion time criterion. Various benchmark data taken from literature, varying from Partial FJSP and Total FJSP, are tested. Experimental results proved that the developed PSO is enough effective and efficient to solve the FJSP. Our other objective in this paper, is to study the distribution of the PSO-solving method for future implementation on embedded systems that can make decisions in real time according to the state of resources and any unplanned or unforeseen events. For this aim, two multi-agent based approaches are proposed and compared using different benchmark instances.

previous article Integrated process planning and scheduling: an enhanced ant colony optimization heuristic with parameter tuning

next article Matheuristic algorithms for minimizing total tardiness in the m-machine flow-shop scheduling problem

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Asadzadeh, L., & Zamanifar, K. (2010). An agent-based parallel approach for the job shop scheduling problem with genetic algorithms. Mathematical and Computer Modelling, 52, 1957–1965.

Azzouz, A., Ennigrou, M., Jlifi, B., & Ghédira, K. (2012). Combining tabu search and genetic algorithm in a multi-agent system for solving flexible job shop problem. In Eleventh Mexican international conference on artificial intelligence, pp. 83–88.

Brandimarte, P. (1993). Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research., 41, 157–183.CrossRef

Binh, H., & Cing, T. (2008). Solving multiple-objective flexible job shop problems by evolution and local search. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 38(5), 674–685.CrossRef

Bastos-Filho, C., Carvalho, D., Figueiredo, E., & Miranda, P. (2009). Dynamic clan particle swarm optimization. In Ninth international conference on intelligent systems design and applications, pp. 249–254.

Clerc, M., & Kennedy, J. (2002). The particle swarm explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 6(1), 58–73.CrossRef

Clerc, M. (2004). Discrete particle swarm optimization, illustrated by the traveling salesman problem. In New optimization techniques in engineering (pp. 219–239). Berlin: Springer.

Chen, Y., Li, Z., & Wang, Z. (2004). Multi-agent-based genetic algorithm for JSSP. In Proceedings of the third international conference on machine learning and cybernetics 2004, pp. 267–270.

Ennigrou, M., & Ghédira, K. (2004). Approche multi-agents basée sur la recherche tabou pour le job shop flexible. In 14ème congrès francophone de reconnaissance des formes et intelligence artificielle, Toulouse, France.

Ennigrou, M., & Ghédira, K. (2008). New local diversification techniques for the flexible job shop problem with a multi-agent approach. Journal of Autonomous Agents and Multi- Agent Systems, 17(2), 270–287.CrossRef

Emin, M. (2012). Coordinating metaheuristic agents with swarm intelligence. Journal of Intelligent Manufacturing, 23(4), 991–999. doi:10.1007/s10845-010-0435-y.CrossRef

Fernández, M., & Raupp, F. (2014). A Newton-based heuristic algorithm for multi-objective flexible job-shop scheduling problem. Journal of Intelligent Manufacturing, pp. 1–8. doi:10.1007/s10845-014-0872-0.

Girish, B., & Jawahar, N. (2009). A particle swarm optimization algorithm for flexible job shop scheduling problem. In 5th annual IEEE conference on automation science and engineering, Bangalore, India, pp. 298–303.

Gao, K. Z., Suganthan, P. N., Pan, Q. K., Chua, T. J., Cai, T. X., & Chong, C. S. (2014). Discrete harmony search algorithm for flexible job shop scheduling problem with multiple objectives. Journal of Intelligent Manufacturing, pp. 1–12.

Gen, M., & Lin, L. (2014). Multi-objective evolutionary algorithm for manufacturing scheduling problems: state-of-the-art survey. Journal of Intelligent Manufacturing, 25(5), 849–866. doi:10.1007/s5-013-0804-4.

Henchiri, A., & Enngirou, M. (2013). Particle swarm optimization combined with tabu search in a multi-agent model for flexible job shop problem. Computer Science, 7929, 385–394.

Jia, Z., Chen, Z., & Tang, J. (2007). An improved particle swarm optimization for multi-objective flexible job-shop scheduling problem. In: Proceedings of 2007 IEEE international conference on grey systems and intelligent services, Nanjing, China, pp. 1587–1592.

Jun-jie, B., Yi-guang, G., Ning-sheng, W., & Dun-bing, T. (2009). An improved PSO algorithm for flexible job shop scheduling with lot-splitting. In Intelligent systems and applications, 2009. ISA 2009. International workshop on. IEEE, 2009. pp. 1–5.

Jalilvand-Nejad, A., & Fattahi, P. (2013). A mathematical model and genetic algorithm to cyclic flexible job shop scheduling problem. Journal of Intelligent Manufacturing, 1–14, 1–14. doi:10.1007/s10845-013-0841-z.

Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. In Proceedings of IEEE international conference on neural networks, pp. 1942–1948.

Kennedy, J. (1999). Small worlds and mega-minds: Effects of neighborhood topology on particle swarm performance. In Evolutionary computation, vol. 3.

Kacem, I., Hammadi, S., & Borne, P. (2002). Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. IEEE Transactions Systems, Man, and Cybernetics, Part C: Applications and Reviews, 32(1), 1–13.CrossRef

Kennedy, J., & Mendes, R. (2003). Neighborhood topologies in fully-informed and best-of-neighborhood particle swarms. In IEEE workshop on soft computing in industrial applications, pp. 45–50.

Liu, H., Abraham, A., & Grosan, C. (2007). A novel variable neighborhood particle swarm optimization for multi-objective flexible job-shop scheduling problems. Digital Information Management, 1, 138–145.

Li, J., Pan, Q., Xie, S., Jia, B., & Wang, Y. (2010). A hybrid particle swarm optimization and tabu search algorithm for flexible job-shop scheduling problem. International Journal of Computer Theory and Engineering, 2(2), 1793–8201.

Lai, P., & Wu, H. (2013). Using heuristic algorithms to solve the scheduling problems with job-dependent and machine-dependent learning effects. Journal of Intelligent Manufacturing. doi:10.1007/s10845-010-0435-y.

Motaghedi-larijani, A., Sabri-laghaie, K., & Heydari, M. (2010). Solving flexible job shop scheduling with multi objective approach. International Journal of Industrial Engineering & Production Research, 21(4), 197–209.

Meeran, S., & Morshed, M. S. (2012). A hybrid genetic tabu search algorithm for solving job shop scheduling problems: A case study. Journal of Intelligent Manufacturing, 23, 1063–1078. doi:10.1007/s10845-011-0520-x.CrossRef

Nouiri, M., Jemai, A., Bekrar, A., Niar, S., & Ammari, A. C. (2013). An effective particle swarm optimization to solve flexible job shop scheduling problem. In Presented at the 5th IESM conference. Morocco: Rabat.

Pezzellaa, F., Morgantia, G., & Ciaschettib, G. (2008). Genetic algorithm for the flexible job-shop scheduling. Computers & Operations Research, 35, 3202–3212.CrossRef

Trelea, I. (2003). The particle swarm optimization algorithm: convergence analysis and parameter selection. Information Processing Letters, 85, 317–325.CrossRef

Tanga, J., Zhanga, G., Lina, B., & Zhang, B. (2011). A hybrid algorithm for flexible job-shop scheduling problem. Procedia Engineering, 15, 3678–3683.CrossRef

Venter, G., & Sobieszczanski-Sobieski, J. (2006). Parallel particle swarm optimization algorithm accelerated by asynchronous evaluations. Journal of Aerospace Computing, Information, and Communication, 3(3), 123–137.CrossRef

Wang, Y., & Xiang, Q. (2008). Particle swarms with dynamic ring topology. Evolutionary Computation, 3, 419–423.

Wei, X., & Dongmei, F. (2012). Multi-agent system for flexible job-shop scheduling problem based on human immune system. In Proceedings of the 31st Chinese control conference, Hefei, China, pp. 2476–2480.

Xia, W., & Wu, Z. (2005). An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering, 48, 409–425.CrossRef

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.

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 & Industrial Engineering, 56, 1309–1318.CrossRef

Zhang, G., Gao, L., & Shi, Y. (2011). An effective genetic algorithm for the flexible job-shop scheduling problem. Expert Systems with Applications, 38, 3563–3573.CrossRef

Title: An effective and distributed particle swarm optimization algorithm for flexible job-shop scheduling problem
Authors: Maroua Nouiri
Abdelghani Bekrar
Abderezak Jemai
Smail Niar
Ahmed Chiheb Ammari
Publication date: 05-02-2015
Publisher: Springer US
Published in: Journal of Intelligent Manufacturing / Issue 3/2018
Print ISSN: 0956-5515
Electronic ISSN: 1572-8145
DOI: https://doi.org/10.1007/s10845-015-1039-3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Other articles of this Issue 3/2018

Fault isolation by test scheduling for embedded systems using a probabilistic approach

Prediction of angular distortion in the fiber laser keyhole welding process based on a variable-fidelity approximation modeling approach

A hybrid particle swarm optimization with local search for stochastic resource allocation problem

Design of informatics-based services in manufacturing industries: case studies using large vehicle-related databases

Performance evaluation of candidate appointment schedules using clearing functions

Maintenance optimization in failure-prone systems under imperfect preventive maintenance