Article ID: | iaor20063332 |
Country: | United States |
Volume: | 10 |
Issue: | 3 |
Publication Date: | Sep 2003 |
Journal: | International Journal of Industrial Engineering |
Authors: | Cochran Jeffery K., Fowler John W., Horng Shwu-Min |
Keywords: | heuristics |
Reducing setups in a single machine scheduling problem with sequence dependent setups is an NP-hard problem for most performance measures. Adding factors such as release times, process times, due dates, weights, and parallel machines further complicates the problem. Therefore, heuristics are often used to solve parallel machine problems. Genetic Algorithms (GAs) are widely used for scheduling problems. In this paper, test problems are characterized by the following factors, 1) range of weights, 2) range of due dates, 3) percentage of jobs ready at the beginning, and 4) ratio of average processing times to average setup times. A GA is used to assign jobs to machines and then a dispatching rule is used to schedule the individual machines. This approach is compared with commonly used strategies and shows better results in most test cases. Three performance measures of scheduling, makespan, total weighted completion time, and total weighted tardiness, are studied.