Premium
Decomposition and hybrid simulated annealing heuristics for the parallel‐machine total tardiness problem
Author(s) -
Koulamas Christos
Publication year - 1997
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/(sici)1520-6750(199702)44:1<109::aid-nav7>3.0.co;2-e
Subject(s) - tardiness , heuristics , simulated annealing , decomposition , mathematical optimization , computer science , heuristic , benders' decomposition , schedule , scheduling (production processes) , job shop scheduling , algorithm , mathematics , ecology , biology , operating system
A polynomial decomposition heuristic is developed for the parallel‐machine tardiness problem ( P&sol& sol;T ) by extending the decomposition principle embedded in the single‐machine tardiness problem ( 1&sol/T ) 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&sol/T problem is also presented. Computational results demonstrate the efficiency and effectiveness of the decomposition heuristic. © 1997 John Wiley & Sons, Inc.