A hybrid genetic algorithm with a neighborhood function for flexible job shop scheduling

Abstract

One of the most important issues of manufacturing systems optimization is scheduling. In fact, it plays a great role in reducing the production time and minimizing the required resources for production. Recently, due to the furious competition between companies, manufacturers are pushed to ensure products of high quality with a minimum amount of resources. In addition to that, they should satisfy the deadline of theirs customers. The Flexible Job Shop Scheduling Problem (FJSSP) is a very popular pattern in the real manufacturing systems. This problem is a generalization of the Classical Job Shop problem (JSP). FJJSP is called flexible because a machine can perform many types of operations. Each job in FJSSP has its own production sequence, composed of a set of operations. However, each machine can execute one operation at the same time. The problem is how to ensure the achievement of all jobs in the shortest time (Makespan).

A hybrid genetic algorithm (HGA) to solve FJSSP is proposed. An Improved Tabu Search (ITS) algorithm with an original neighborhood function is designed, to improve the performance of GA. The approach was tested and validated using one of the most known benchmarks. The effectiveness of the proposed approach is proved by tests.

Keywords

Manufacturing optimization flexible job shop scheduling problem hybrid approach genetic algorithm improved Tabu search

Get full access to this article

View all access options for this article.

References

Talbi

E.-G.

Yalaoui

and Amodeo

, Metaheuristics for Production Systems, 1st ed., S.I. Publishing, Ed. London, United Kingdom: Springer, 2016.

Liangxiao

and Zhongjun

, An improved genetic algorithm for flexible job shop scheduling problem, in 2nd International Conference on Information Science and Control Engineering, Shanghai, China (2015), 127–131.

Mastrolilli

and Gambardella

L.M.

, Effective neighbourhood functions for the flexible job shop problem, Journal of Scheduling 3(1) (2000), 3–20.

Kacem

Hammadi

and Borne

, Approach by localization and mult-iobjective evolutionary optimization for flexible job-shop scheduling problems, IEEE Transactions on Systems, Man, and Cybernetics, Part C 32(1) (2002), 1–13.

Zribi

Kacem

Kamel

A.E.

and Borne

, Assignment and scheduling in flexible job-shops by hierarchical optimization, IEEE Transactions on Systems, Man, and Cybernetics 37(4) (2007), 652–661.

Zribi

El-Kamel

and Borne

, Minimizing the makespan for the MPM job-shop with availability constraints, International Journal of Production Economics 112(1) (2008), 151–160.

Raich

Nikumbh

P.J.

and Patil

, Flexible job–shop scheduling problem using simulated annealing, International Journal of Research & Reviewes in Computer Science 3(2) (2012), 1491–1501.

Sridhar

Victor Raj

and Chandra Sekar

, Minimizing manufacturing cost in flexible job-shop scheduling problems, International Journal of Artificial Intelligence and Mechatronics 1(5) (2013), 2320–5121.

Ziaee

, A heuristic algorithm for solving flexible job shop scheduling problem, The International Journal of Advanced Manufacturing Technology 71(1) (2014), 519–528.

10.

Yiyong

Wei

and Shigeru

, Improvements to genetic algorithm for flexible job shop scheduling with overlapping in operations, in 16th International Conference on Computer and Information Science (ICIS), Wuhan, China (2017), 791-796.

11.

Fattahi

, A hybrid multi objective algorithm for flexible job shop scheduling, International Journal of Mathematical and Statistical Sciences 1(1) (2009), 21–26.

12.

Xia

and Wu

, An effective hybrid optimization approach for multi-objective, Computers and Industrial Engineering 48(2) (2005), 409–425.

13.

El Khoukhi

Boukachour

and El Hilali Alaouic

, The dual-ants colony: A novel hybrid approach for the flexible job shop scheduling problem with preventive maintenance, Computers & Industrial Engineering 106 (2017), 236–255.

14.

Tang

Zhang

and Lin

, A hybrid algorithm for flexible job-shop scheduling problem, Procedia Engineering 15(1) (2011), 3678–3683.

15.

Trentesaux

Pach

and Bekrar

, Benchmarking flexible job-shop scheduling and control systems, Control Engineering Practice 21(9) (2013), 1204–1225.

16.

Eikelder

Aarts

Verhoeven

and Aarts

, Sequential and Parallel Local Search Algorithms for Job Shop Scheduling, B.M. Springer, Ed. Boston, USA: Springer Book Archive, 1999.

17.

Ennigrou

, Approche multiagents basee sur la recherche tabou pour le job shop flexible, in 14eme Congres Francophone AFRIF-AFIA de Reconnaissance des Formes et Intelligence Artificielle RFIA, Toulouse, France (2004), 28–30.

18.

Gen

Gao

and Lin

, Multistage-based genetic algorithm for flexible job-shop scheduling problem, in Studies in Computational Intelligence, B.H. Springer, Ed. Berlin, Germany: Springer 187 (2009), 183–196.

19.

Lee

K.-M.

Yamakawa

and Lee

K.-M.

, A genetic algorithm for general machine scheduling problems, in Knowledge-Based Intelligent Electronic Systems, Proceedings KES 98, Adelaide, SA, Australia, Australia (1998), 60–66.

20.

Ponnambalam

S.G.

Jawahar

and Girish

B.S.

, An ant colony optimization algorithm for flexible job shop scheduling problem, in New Advanced Technologies, A. Lazinica, Ed. InTech, Mar. March (2010), ch. 4, 74–95,https://www.intechopen.com/books/new-advanced-technologies/an-ant-colony-optimization-algorithm-for-flexible-job-shop-scheduling-problem.

21.

Raja

and Pugazhenthi

, Path planning for mobile robots in dynamic environments using particle swarm optimization, in Advances in Recent Technologies in Communication and Computing, 2009. ARTCom ’09. International Conference on, Kottayam, Kerala, India (2009), 27–28.

22.

Bekkar

et al., An iterative greedy insertion technique for flexible job shop scheduling problem, in 8th IFAC Conference on Manufacturing Modelling, Management and Control, Troyes, France (2016), 1956–1961.

23.

Pach

Berger

Bonte

and Trentesaux

, ORCA-FMS: A dynamic architecture for the optimized and reactive control of flexible manufacturing scheduling, Computers in Industry 65(4) (2014), 706–720.