American Institute of Mathematical Sciences

• Previous Article
Continuous-time mean-variance asset-liability management with stochastic interest rates and inflation risks
• JIMO Home
• This Issue
• Next Article
A zero-forcing beamforming based time switching protocol for wireless powered internet of things system
doi: 10.3934/jimo.2019088

An enhanced Genetic Algorithm with an innovative encoding strategy for flexible job-shop scheduling with operation and processing flexibility

 1 Faculty of Management and Economics, Dalian University of Technology, Dalian, Liaoning 116023, China 2 ISILC, Victoria University, Melbourne, Australia 3 Operations & Supply Chain Management Research Group, Universidad de La Sabana, Bogotá, Colombia

* Corresponding author: Sardar M. N. Islam

Received  November 2017 Revised  March 2019 Published  July 2019

Fund Project: Xuewen Huang is supported by the National Science and Technology Plan of China under Grant No. 2015BAF09B01 and the China Scholarship under Grant No. 201606060170

This paper considers the Flexible Job-shop Scheduling Problem with Operation and Processing flexibility (FJSP-OP) with the objective of minimizing the makespan. A Genetic Algorithm based approach is presented to solve the FJSP-OP. For the performance improvement, a new and concise Four-Tuple Scheme (FTS) is proposed for modeling a job with operation and processing flexibility. Then, with the FTS, an enhanced Genetic Algorithm employing a more efficient encoding strategy is developed. The use of this encoding strategy ensures that the classic genetic operators can be adopted to the utmost extent without generating infeasible offspring. Experiments have validated the proposed approach, and the results have shown the effectiveness and high performance of the proposed approach.

Citation: Xuewen Huang, Xiaotong Zhang, Sardar M. N. Islam, Carlos A. Vega-Mejía. An enhanced Genetic Algorithm with an innovative encoding strategy for flexible job-shop scheduling with operation and processing flexibility. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2019088
References:

show all references

References:
Alternative process plans networks
An illustrative chromosome applying the hierarchical encoding approach
Illustrative chromosomes applying the integrated encoding approach
Algorithm GENERATE-PROCESS-PLAN
A chromosome of the FJSP-OP
Algorithm GENERATE-SCHEDULING
Decoding a chromosome
Crossover operations
Mutation operations
The Gantt chart of Experiment 1
The Gantt chart of Experiment 3
The Gantt chart of Experiment 4
The Gantt chart of problem mk06 in Experiment 5
The Gantt chart of Experiment 6(b)
Performance curve of Experiment 4
The data of Experiment 3
Comparison of results for Experiment 1
 Solution approach EA Modified GA PBHA GA-OP Makespan 16 14 14 14 Mean CPU time (ms) N/A N/A N/A 191 1 N/A means the result was not given by the author.
 Solution approach EA Modified GA PBHA GA-OP Makespan 16 14 14 14 Mean CPU time (ms) N/A N/A N/A 191 1 N/A means the result was not given by the author.
Parameters and comparison of results on Experiment 3
 Solution approach ALO Modified GA GA-OP Parameters N/A $PopSize=500$ $PopSize=50$ $P_c=0.8,P_m=0.1,IterNo=100$ Makespan 161 162 145 Mean CPU time (ms) N/A N/A 309
 Solution approach ALO Modified GA GA-OP Parameters N/A $PopSize=500$ $PopSize=50$ $P_c=0.8,P_m=0.1,IterNo=100$ Makespan 161 162 145 Mean CPU time (ms) N/A N/A 309
Parameters and comparison of results on Experiment 4
 Solution approach ALGA GA-OP Parameters $PopSize=400$ $PopSize=200$ $P_c=0.8$, $P_m=0.1$, $IterNo=100$ Makespan 188 181 Mean CPU time (ms) N/A 2,907
 Solution approach ALGA GA-OP Parameters $PopSize=400$ $PopSize=200$ $P_c=0.8$, $P_m=0.1$, $IterNo=100$ Makespan 188 181 Mean CPU time (ms) N/A 2,907
Comparison of results for Experiment 5
 Problem $n \times m$ TABC HGTS MA2 HA PSO VNSGA GA-OP mk01 10x6 40 40 40 40 41 40 40 mk02 10x6 26 26 26 26 26 26 26 mk03 15x8 204 204 204 204 207 204 204 mk04 15x8 60 60 60 60 65 60 60 mk05 15x4 173 172 172 172 171 173 172 mk06 10x15 60 57 59 57 61 58 57 mk07 20x5 139 139 139 139 173 144 139 mk08 20x10 523 523 523 523 523 523 523 mk09 20x10 307 307 307 307 307 307 307 mk10 20x15 202 198 202 197 312 198 198
 Problem $n \times m$ TABC HGTS MA2 HA PSO VNSGA GA-OP mk01 10x6 40 40 40 40 41 40 40 mk02 10x6 26 26 26 26 26 26 26 mk03 15x8 204 204 204 204 207 204 204 mk04 15x8 60 60 60 60 65 60 60 mk05 15x4 173 172 172 172 171 173 172 mk06 10x15 60 57 59 57 61 58 57 mk07 20x5 139 139 139 139 173 144 139 mk08 20x10 523 523 523 523 523 523 523 mk09 20x10 307 307 307 307 307 307 307 mk10 20x15 202 198 202 197 312 198 198
The experimental results (computational time in terms of seconds) of experiment 5
 Problem n x m TABC HGTS MA2 HA PSO VNSGA GA-OP mk01 10x6 3.36 5 20.16 0.06 N/A N/A 0.27 mk02 10x6 3.72 15 28.21 0.59 N/A N/A 3.75 mk03 15x8 1.56 2 53.76 0.16 N/A N/A 0.12 mk04 15x8 66.58 10 30.53 0.49 N/A N/A 3.41 mk05 15x4 78.45 18 36.36 4.57 N/A N/A 6.23 mk06 10x15 173.98 63 80.61 53.82 N/A N/A 65.14 mk07 20x5 66.19 33 37.74 20.01 N/A N/A 25.4 mk08 20x10 2.15 3 77.71 0.02 N/A N/A 0.2 mk09 20x10 304.43 24 75.23 0.86 N/A N/A 4.1 mk10 20x15 418.19 104 90.75 33.21 N/A N/A 73.12
 Problem n x m TABC HGTS MA2 HA PSO VNSGA GA-OP mk01 10x6 3.36 5 20.16 0.06 N/A N/A 0.27 mk02 10x6 3.72 15 28.21 0.59 N/A N/A 3.75 mk03 15x8 1.56 2 53.76 0.16 N/A N/A 0.12 mk04 15x8 66.58 10 30.53 0.49 N/A N/A 3.41 mk05 15x4 78.45 18 36.36 4.57 N/A N/A 6.23 mk06 10x15 173.98 63 80.61 53.82 N/A N/A 65.14 mk07 20x5 66.19 33 37.74 20.01 N/A N/A 25.4 mk08 20x10 2.15 3 77.71 0.02 N/A N/A 0.2 mk09 20x10 304.43 24 75.23 0.86 N/A N/A 4.1 mk10 20x15 418.19 104 90.75 33.21 N/A N/A 73.12
Comparison of results on Experiment 6
 Solution approach Experiment 6(a) Experiment 6(b) ACO GA-OP Enhanced ACO GA-OP Makespan 589 522 484 482 Mean CPU time (ms) 128,700 12,056 120534 12063
 Solution approach Experiment 6(a) Experiment 6(b) ACO GA-OP Enhanced ACO GA-OP Makespan 589 522 484 482 Mean CPU time (ms) 128,700 12,056 120534 12063
Alternative machines of each operation performed for each job
 Operation Job 1 2 3 4 5 6 1 2, 4 2, 4 3, 5 3, 5 2, 4 2, 4 2 7, 8 7, 8 4, 6 4, 6 3, 5 3, 5 3 1, 2 1, 2 2, 3, 5 2, 3, 5 1, 2, 6 1, 2, 6 4 8, 6 8, 6 6, 7 6, 7 6, 8 6, 8 5 3, 5 3, 5 1, 8 1, 8 1, 7 1, 7 6 1, 2, 4 1, 2, 4 1, 4 1, 4 1, 3 1, 3 7 5, 6 5, 6 6, 7 6, 7 6, 7 6, 7 8 1, 7 1, 7 5, 8 5, 8 5, 8 5, 8 9 3, 8 3, 8 4, 2 4, 2 4, 3 4, 3
 Operation Job 1 2 3 4 5 6 1 2, 4 2, 4 3, 5 3, 5 2, 4 2, 4 2 7, 8 7, 8 4, 6 4, 6 3, 5 3, 5 3 1, 2 1, 2 2, 3, 5 2, 3, 5 1, 2, 6 1, 2, 6 4 8, 6 8, 6 6, 7 6, 7 6, 8 6, 8 5 3, 5 3, 5 1, 8 1, 8 1, 7 1, 7 6 1, 2, 4 1, 2, 4 1, 4 1, 4 1, 3 1, 3 7 5, 6 5, 6 6, 7 6, 7 6, 7 6, 7 8 1, 7 1, 7 5, 8 5, 8 5, 8 5, 8 9 3, 8 3, 8 4, 2 4, 2 4, 3 4, 3
Processing times on the alternative machines of each operation
 Operation Job 1 2 3 4 5 6 1 18, 22 18, 22 12, 15 12, 15 18, 22 18, 22 2 39, 36 39, 36 24, 23 24, 23 12, 15 12, 15 3 11, 10 37, 39 30, 31, 29 30, 31, 29 50, 52, 54 50, 52, 54 4 31, 34 20, 21 21, 22 21, 22 19, 21 53, 51 5 21, 23 21, 23 32, 30 32, 30 32, 31 22, 24 6 10, 12, 15 10, 12, 15 22, 25 22, 25 22, 25 22, 25 7 32, 30 36, 38 24, 22 42, 44 24, 22 24, 22 8 45, 44 45, 44 20, 19 41, 43 20, 18 20, 18 9 26, 24 26, 24 27, 22 27, 22 27, 22 27, 22
 Operation Job 1 2 3 4 5 6 1 18, 22 18, 22 12, 15 12, 15 18, 22 18, 22 2 39, 36 39, 36 24, 23 24, 23 12, 15 12, 15 3 11, 10 37, 39 30, 31, 29 30, 31, 29 50, 52, 54 50, 52, 54 4 31, 34 20, 21 21, 22 21, 22 19, 21 53, 51 5 21, 23 21, 23 32, 30 32, 30 32, 31 22, 24 6 10, 12, 15 10, 12, 15 22, 25 22, 25 22, 25 22, 25 7 32, 30 36, 38 24, 22 42, 44 24, 22 24, 22 8 45, 44 45, 44 20, 19 41, 43 20, 18 20, 18 9 26, 24 26, 24 27, 22 27, 22 27, 22 27, 22
Transportation times between the machines
 Machine number 1 2 3 4 5 6 7 8 1 0 3 7 10 3 5 8 12 2 3 0 4 7 5 3 5 8 3 7 4 0 3 8 5 3 5 4 10 7 3 0 10 8 5 3 5 3 5 8 10 0 3 7 10 6 5 3 5 8 3 0 4 7 7 8 5 3 5 7 4 0 3 8 12 8 5 3 10 7 3 0
 Machine number 1 2 3 4 5 6 7 8 1 0 3 7 10 3 5 8 12 2 3 0 4 7 5 3 5 8 3 7 4 0 3 8 5 3 5 4 10 7 3 0 10 8 5 3 5 3 5 8 10 0 3 7 10 6 5 3 5 8 3 0 4 7 7 8 5 3 5 7 4 0 3 8 12 8 5 3 10 7 3 0
 [1] Didem Cinar, José António Oliveira, Y. Ilker Topcu, Panos M. Pardalos. A priority-based genetic algorithm for a flexible job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1391-1415. doi: 10.3934/jimo.2016.12.1391 [2] Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2017, 13 (5) : 0-0. doi: 10.3934/jimo.2019122 [3] Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703 [4] Behrad Erfani, Sadoullah Ebrahimnejad, Amirhossein Moosavi. An integrated dynamic facility layout and job shop scheduling problem: A hybrid NSGA-II and local search algorithm. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-34. doi: 10.3934/jimo.2019030 [5] Adel Dabah, Ahcene Bendjoudi, Abdelhakim AitZai. An efficient Tabu Search neighborhood based on reconstruction strategy to solve the blocking job shop scheduling problem. Journal of Industrial & Management Optimization, 2017, 13 (4) : 2015-2031. doi: 10.3934/jimo.2017029 [6] Alena Erchenko. Flexibility of Lyapunov exponents for expanding circle maps. Discrete & Continuous Dynamical Systems - A, 2019, 39 (5) : 2325-2342. doi: 10.3934/dcds.2019098 [7] Ji-Bo Wang, Mengqi Liu, Na Yin, Ping Ji. Scheduling jobs with controllable processing time, truncated job-dependent learning and deterioration effects. Journal of Industrial & Management Optimization, 2017, 13 (2) : 1025-1039. doi: 10.3934/jimo.2016060 [8] F. Zeyenp Sargut, H. Edwin Romeijn. Capacitated requirements planning with pricing flexibility and general cost and revenue functions. Journal of Industrial & Management Optimization, 2007, 3 (1) : 87-98. doi: 10.3934/jimo.2007.3.87 [9] Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial & Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269 [10] Ethel Mokotoff. Algorithms for bicriteria minimization in the permutation flow shop scheduling problem. Journal of Industrial & Management Optimization, 2011, 7 (1) : 253-282. doi: 10.3934/jimo.2011.7.253 [11] M. Ramasubramaniam, M. Mathirajan. A solution framework for scheduling a BPM with non-identical job dimensions. Journal of Industrial & Management Optimization, 2007, 3 (3) : 445-456. doi: 10.3934/jimo.2007.3.445 [12] Min-Fan He, Li-Ning Xing, Wen Li, Shang Xiang, Xu Tan. Double layer programming model to the scheduling of remote sensing data processing tasks. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1515-1526. doi: 10.3934/dcdss.2019104 [13] Yaw Chang, Lin Chen. Solve the vehicle routing problem with time windows via a genetic algorithm. Conference Publications, 2007, 2007 (Special) : 240-249. doi: 10.3934/proc.2007.2007.240 [14] Abdel-Rahman Hedar, Alaa Fahim. Filter-based genetic algorithm for mixed variable programming. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 99-116. doi: 10.3934/naco.2011.1.99 [15] Jiping Tao, Ronghuan Huang, Tundong Liu. A $2.28$-competitive algorithm for online scheduling on identical machines. Journal of Industrial & Management Optimization, 2015, 11 (1) : 185-198. doi: 10.3934/jimo.2015.11.185 [16] Mostafa Abouei Ardakan, A. Kourank Beheshti, S. Hamid Mirmohammadi, Hamed Davari Ardakani. A hybrid meta-heuristic algorithm to minimize the number of tardy jobs in a dynamic two-machine flow shop problem. Numerical Algebra, Control & Optimization, 2017, 7 (4) : 465-480. doi: 10.3934/naco.2017029 [17] Yuanjia Ma. The optimization algorithm for blind processing of high frequency signal of capacitive sensor. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1399-1412. doi: 10.3934/dcdss.2019096 [18] Bin Zheng, Min Fan, Mengqi Liu, Shang-Chia Liu, Yunqiang Yin. Parallel-machine scheduling with potential disruption and positional-dependent processing times. Journal of Industrial & Management Optimization, 2017, 13 (2) : 697-711. doi: 10.3934/jimo.2016041 [19] Chengxin Luo. Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 71-77. doi: 10.3934/naco.2015.5.71 [20] Chuanli Zhao, Yunqiang Yin, T. C. E. Cheng, Chin-Chia Wu. Single-machine scheduling and due date assignment with rejection and position-dependent processing times. Journal of Industrial & Management Optimization, 2014, 10 (3) : 691-700. doi: 10.3934/jimo.2014.10.691

2018 Impact Factor: 1.025