ADME-JSP: AN EFFECTIVE MEMETIC ALGORITHM FOR JOB SHOP SCHEDULING PROBLEM

The Job Shop Scheduling Problem (JSP) is one of the most well known planning problems. We have considered the JSP with an objective of minimizing makespan. In this paper, an effective Memetic algorithm isdeveloped to find the minimal schedule. We called this algorithm ADME-JSP. In ADME-JSP, using the ShuffledFrog Leaping Algorithm the population is divided in several groups. Then each group uses the presented Memeticalgorithm to solve the Job Shop Scheduling Problem. Two local searches have been used to balance the exploration and exploitation. One of the local searches is based on the Simulated Annealing Algorithm and another one is based on the Pair Wise interchange heuristic. The best solution (schedule) to the whole population is chosen among thebest results of all groups. The proposed approach, ADME-JSP, have been compared with other algorithms for JobShop Scheduling and evaluated with satisfactory results on a set of JSPs derived from classical Job Shop Schedulingbenchmarks. We have solved 15 benchmark problems (LA01 - LA15) from Lawrence and compared results found with a number of algorithms established in the literature. The results indicate that in all cases ADME-JSP can find the Best Known Solution (BKS).

کلیدواژه ها:

Job Shop Schedulig ، Memetic Algorithm ، Simulated Annealing ، Pair Wise Selection