| Parallel machine scheduling problems that consider the factors of release times, process times, due dates, weights, and sequence dependent setups, are NP-hard for the objectives of makespan, total weighted completion time, or total weighted tardiness. In this research, a new methodology that hybridizes genetic algorithms with dispatching rules is developed. The hybridized genetic algorithm (HGA) uses a new encoding scheme for assigning jobs to parallel machines, and a dispatching rule to schedule the single machines. Initially, a simple dispatching rule (FIFO) is considered. After extensive study, two dispatching rules, setup avoidance, and the Apparent Tardiness Cost with Setups (ATCS) rule, are used to schedule the single machines. The performance of HGA shows better results than that of the benchmark methods for a wide range of parallel machine assignments.; In this research, we also develop a method to consider multiple objectives simultaneously, a two-stage Multi-Population Genetic Algorithm (MPGA). Assuming N objectives are to be satisfied, at the first stage MPGA evolves by using a combined objective function. At the second stage, the population is divided into N sub-populations that each evolve based on an individual objective and one sub-population that evolves based on the combined objective. An elitist strategy preserves the best individual of each objective, and a best individual of the combined objective. This approach is validated on a parallel machine scheduling problem in ion implantation of semiconductor manufacturing with all three objectives considered simultaneously. Even though the problem is NP-hard, we achieve good results in reasonable CPU time. |
