| Minimizing the Make Span of Unrelated Parallel Machines (2003) | |||||||||
Abstract | |||||||||
| Abstract In this project, we study a unrelated parallel machine scheduling problem for minimizing the makespan: R||Cmax. This problem has been shown to be NP-hard. We tried Simulated Annealing (SA) and Tabu Search (TS) with Efficient Neighborhood Search, which is based on the structure of the problem. We also tried a modified SA algorithm, which does better than the raditional SA in both result quality and running time. From the extensive experimentation, we also developed an effective combination of heuristics for the problem: Squeaky Wheel optimization (SWO) with TS. Performance improves significantly. Experimental results are good with solutions coming well within 1% of the lower bound within acceptable time. Subject Descriptors: F.2.2 Nonnumerical Algorithms and Problems G.1.6 Optimization I.2.8 Problem Solving, Control Methods, and Search Keywords: Makespan, Unrelated parallel machine scheduling, Simulated Annealing, Tabu Search, Squeaky Wheel Optimization. Implementation Software and Hardware: JDK1.4.0, Microsoft Windows, Desktop PC with Intel Pentium 2 Processor (300 MHz), SD-RAM 192MB. | |||||||||
Details der Publikation | |||||||||
| |||||||||