Comparison of Genetic Algorithm and Particle Swarm Optimization for Bicriteria Permutation Flowshop Scheduling Problem
Serol BulkanAbstract: Flowshop scheduling is a well known research field for many years. As the problem size gets bigger, an analytical solution becomes impossible. Here, heuristic solutions come to the stage. In the literature, generally solutions regarding a single criterion are developed; and makespan is the most common objective used. There are some multi objective solutions for one or two machines; but, only one criterion is generally used for more than two machines. In this paper, makespan and maximum tardiness criteria are used concurrently, for big problem sizes like 50 jobs-20 machines. For this purpose, a Particle Swarm Optimization (PSO), and a Genetic Algorithm (GA) is developed and applied to standard test problems. Not only the pure versions of PSO and GA, but also their hybrid versions – i.e. with a local search called Variable Neighborhood Search (VNS) embedded - are tested; and the relative performances of the two algorithms are compared. As a result, PSO performed better for the situations where the weight of maximum tardiness criterion was greater, while GA surpassed PSO when the makespan objective was dominant. Regarding the CPU times, PSO found a solution more quickly for all occasions. The with-VNS versions of the algorithms found better solutions compared to the pure versions; but, it took them much longer.
Keywords:
scheduling, flowshop, heuristic optimization, PSO, GA, bicriteria
doi:10.5019/j.ijcir.2004.135
Full Text PDF
^ TOP