APPLYING DIFFERENTIAL EVOLUTION ALGORITHM FOR MINIMIZING MAKESPAN IN JOB SHOP SCHEDULING PROBLEM

Abstract

Job shop scheduling problem can become complex when there are a set of different machines that perform several operations in job shop production system. Improper or wrong scheduling can affect the schedule because the job cannot be completed on time. Differential Evolution Algorithm can arrange the scheduling to solve job shop scheduling problem because this algorithm can produce the best solution easily with minimum time. Design of Experiment method will help to find the best parameters. The best combination parameter for Differential Evolution model to solve job shop scheduling problem are mutation factor 0.7, cross over rate 0.5, number of population 10 individuals and run with 15 iterations. Differential Evolution Algorithm is done through several steps, including initialization, mutation, crossover and selection process. By using combination of parameters that is calculated from Design of Experiment method and Differential Evolution Algorithm, it requires 34,200 seconds or 570 minutes to finish 6 jobs with 5 machines. Compared with Genetic Algorithm from previous research, Differential Evolution can reduce makespan around 5% from Genetic Algorithm schedule and reduce around 10% from current schedule.