Open Access Open Access  Restricted Access Subscription or Fee Access

Minimising the Makespan of Job Shop Scheduling Problem by Using Genetic Algorithm (Ga)

Pardeep Kumar, Gyander Ghangas, Abhisak Sharma, Sunil Dhull

Abstract


The job-shop scheduling problem is a well-known problem in the field of production as well as combinational optimization. There is ‘k’ represent the operations number and ‘n’ represent no of jobs to be processed on ‘m’ no of machines with a definite objective function to be optimized makespan (total time to compilation of operations on a particular task)in job-shop scheduling problem. The particular work adopted a modified genetic algorithm approach is proposed with operating parameters i.e., size of population 50, operation chromosome based structure, selection scheme used as tournament selection, crossover two-point random with a probability 80% (Probc= 0.8),mutation two-point with a probability 20% (Probm= 0.2), elitism is also active, repairing of chromosomes and no. of iteration (termination) is 1000. Genetic algorithm is programmed for job shop environment create with the help of MATLAB 2009 a 7.8. The proposed Genetic Algorithm (GA) with certain operating parameters is applied to the two problems which are taken from literature. The results obtained from modified Genetic Algorithm show that the best optimization technique for solving the job shop scheduling problems in manufacturing systems is genetic algorithm with modified operating parameter selected in these research implications to more practical and integrated problems.

Keywords


Scheduling; Transportation Time; MATLAB, Genetic Algorithm.

Full Text:

PDF

References


Mattfeld DC, Bierwirth C. An efficient genetic algorithm for job shop scheduling with tardiness objectives. European journal of operational research. 2004 Jun 16; 155(3):616–30.

Gao J, Gen M, Sun L. Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm. Journal of Intelligent Manufacturing. 2006 Aug 1; 17(4):493–507.

Wang YM, Xiao NF, Yin HL, Hu EL, Zhao CG, Jiang YR. A two-stage genetic algorithm for large size job shop scheduling problems. The International Journal of Advanced Manufacturing Technology. 2008 Nov 1;39(7–8):813–20.

Zhang C, Rao Y, Li P. An effective hybrid genetic algorithm for the job shop scheduling problem. The International Journal of Advanced Manufacturing Technology. 2008 Nov 1; 39(9–10):965.

Haq AN, Balasubramanian K, Sashidharan B, Karthick RB. Parallel line job shop scheduling using genetic algorithm. The International Journal of Advanced Manufacturing Technology. 2008 Jan 1; 35(9– 10):1047–52.

Manikas A, Chang YL. Multi-criteria sequence-dependent job shop scheduling using genetic algorithms. Computers & Industrial Engineering. 2009 Feb 1; 56(1):179–85.

Manikas A, Chang YL. Multi-criteria sequence-dependent job shop scheduling using genetic algorithms. Computers & Industrial Engineering. 2009 Feb 1; 56(1):179–85.

Gu J, Gu X, Gu M. A novel parallel quantum genetic algorithm for stochastic job shop scheduling. Journal of Mathematical Analysis and Applications. 2009 Jul 1; 355(1):63–81.

Rossi A, Boschi E. A hybrid heuristic to solve the parallel machines job- shop scheduling problem. Advances in Engineering Software. 2009 Feb 1; 40(2):118–27.

Lei D. Solving fuzzy job shop scheduling problems using random key genetic algorithm. The International Journal of Advanced Manufacturing Technology. 2010 Jul 1; 49(1–4):253–62.

Defersha FM, Chen M. A parallel genetic algorithm for a flexible job- shop scheduling problem with sequence dependent setups. The international journal of advanced manufacturing technology. 2010 Jul 1; 49(1–4):263–79.

Bożejko W, Makuchowski M. Solving the no-wait job-shop problem by using genetic algorithm with automatic adjustment. The International Journal of Advanced Manufacturing Technology. 2011 Nov 1; 57(5–8):735–52.

Oddi A, Rasconi R, Cesta A, Smith SF. Solving job shop scheduling with setup times through constraint-based iterative sampling: an experimental analysis. Annals of Mathematics and Artificial Intelligence. 2011 Jul 1; 62(3–4):371–402.

Teekeng W, Thammano A. Modified genetic algorithm for flexible job- shop scheduling problems. Procedia Computer Science. 2012 Jan 1;12:122–8.

Wang L, Zhou G, Xu Y, Wang S, Liu M. An effective artificial bee colony algorithm for the flexible job-shop scheduling problem. The International Journal of Advanced Manufacturing Technology. 2012 Apr 1; 60(1–4):303–15.

Zhang R, Song S, Wu C. A dispatching rule-based hybrid genetic algorithm focusing on non-delay schedules for the job shop scheduling problem. The International Journal of Advanced Manufacturing Technology. 2013 Jul 1; 67(1–4):5–17.

Sastry K, Goldberg D, Kendall G, Burke EK. Search methodologies: Introductory tutorials in optimization and decision support techniques. ISBN Springer. 2005.

Jain AS, Meeran S. A state-of-the-art review of job-shop scheduling techniques. Technical report, Department of Applied Physics, Electronic and Mechanical Engineering, University of Dundee, Dundee, Scotland; 1998;113(2):390–434.

Phanden RK, Jain A, Verma R. An approach for integration of process planning and scheduling.

International Journal of Computer Integrated Manufacturing. 2013 Apr 1; 26(4):284–302.

Guizzi G, Revetria R, Vanacore G, Vespoli S. On the open job-shop scheduling problem: a decentralized multi-agent approach for the manufacturing system performance optimization. Procedia CIRP. 2019 Jan 1; 79:192–7.




DOI: https://doi.org/10.37628/ijpe.v6i1.1112

Refbacks

  • There are currently no refbacks.