Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

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

  • Published:
Journal of Intelligent Manufacturing Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

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

    Article  Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. LIP2 Laboratory, Faculty of Science of Tunis, Tunis, Tunisia

    Maroua Nouiri & Abderezak Jemai

  2. MMA Laboratory, INSAT Institute, Carthage University, 1080, Tunis, Tunisia

    Ahmed Chiheb Ammari

  3. Renewable Energy Group, Department of Electrical and Computer Engineering, Faculty of Engineering, King Abdulaziz University, Jeddah, 21589, Saudi Arabia

    Ahmed Chiheb Ammari

  4. UVHC, LAMIH Laboratory, 59313, Valenciennes, France

    Abdelghani Bekrar & Smail Niar

  5. University of Lille Nord de France, 59000, Lille, France

    Abdelghani Bekrar & Smail Niar

Authors
  1. Maroua Nouiri
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Abdelghani Bekrar
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Abderezak Jemai
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Smail Niar
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Ahmed Chiheb Ammari
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Abdelghani Bekrar.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Nouiri, M., Bekrar, A., Jemai, A. et al. An effective and distributed particle swarm optimization algorithm for flexible job-shop scheduling problem. J Intell Manuf 29, 603–615 (2018). https://doi.org/10.1007/s10845-015-1039-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10845-015-1039-3

Keywords

Search

Navigation