Artificial Immune System Applied to Job Shop Scheduling
Abstract—Job Shop Scheduling is a problem to schedule n number of jobs in m number of machines with a different order of processing. Each machine processes exactly one job at a time. Each job will be processed in every machine once. When a machine is processing one particular job then the other machine can’t process the same job. Different schedule’s order might produce different total processing time. The result of this scheduling problem will be total processing time and schedule’s order. This paper uses clonal selection as the algorithm to solve this problem. The clonal selection algorithm comes from the concept of an artificial immune system. It's developed by copying a human’s immune system behavior. A human’s immune system can differentiate foreign objects and eliminate the objects by creating an antibody. An antibody will go to a cloning process and will mutate to further enhance itself. Clonal selection algorithm applies this cloning and mutation principle to find the most optimal solution. The goal is to find the best schedule’s order and makespan. Taillard’s benchmark is used to verify the quality of the result. To compare the result, we use two values: the upper bound and the lower bound. The upper bound is used to describe the best result of a scheduling problem that has been conducted using a certain environment. On the contrary, the lower bound shows the worst. Experiments on changing the algorithm's parameters are also conducted to measure the quality of the program. The parameters are the number of iterations, mutations, and clone numbers. According to the experiment's results, the higher the number of iteration, mutation rate, and clone number, the better solution for the problem. Clonal selection algorithm has not been able to keep up with upper bound or lower bound values from Taillard’s case. Therefore, parameters need to be increased significantly to increase the chance to produce the optimum result. The higher number of parameters used means the longer time needed to produce the result.
Index Terms—job shop scheduling, artificial immune system, clonal selection, Tailard's benchmark
Copyright © 2021 by the authors. This is an open access article distributed under the Creative Commons Attribution License (CC BY-NC-ND 4.0), which permits use, distribution and reproduction in any medium, provided that the article is properly cited, the use is non-commercial and no modifications or adaptations are made.