Decomposition and hybrid simulated annealing heuristics for the parallel-machine total tardiness problem
✍ Scribed by Christos Koulamas
- Publisher
- John Wiley and Sons
- Year
- 1997
- Tongue
- English
- Weight
- 93 KB
- Volume
- 44
- Category
- Article
- ISSN
- 0894-069X
No coin nor oath required. For personal study only.
✦ Synopsis
A polynomial decomposition heuristic is developed for the parallel-machine tardiness problem (P//T V ) by extending the decomposition principle embedded in the single-machine tardiness problem (1//T V ) to a parallel-machine setting. The subproblems generated by the decomposition are solved by an effective heuristic that yields solutions such that the schedule on any individual machine satisfies the single-machine decomposition principle. A hybrid simulated annealing heuristic tailored to the P/ /T V problem is also presented. Computational results demonstrate the efficiency and effectiveness of the decomposition heuristic.