Dominance-based heuristics for one-machine total cost scheduling problems |
| |
Authors: | Antoine Jouglet David Savourey Jacques Carlier Philippe Baptiste |
| |
Institution: | 1. Heudiasyc, UMR CNRS 6599, Université de Technologie de Compiègne, BP 20 529, 60205 Compiègne, France;2. Ecole Polytechnique, CNRS LIX, 91128 Palaiseau, France |
| |
Abstract: | We study the one-machine scheduling problem with release dates and we look at several objective functions including total (weighted) tardiness and total (weighted) completion time. We describe dominance rules for these criteria, as well as techniques for using these dominance rules to build heuristic solutions. We use them to improve certain well-known greedy heuristic algorithms from the literature. Finally, we introduce a Tabu Search method with a neighborhood based on our dominance rules. Experiments show the effectiveness of our techniques in obtaining very good solutions for all studied criteria. |
| |
Keywords: | Scheduling Heuristics Single machine |
本文献已被 ScienceDirect 等数据库收录! |
|