Decomposition and hybrid simulated annealing heuristics for the parallel-machine total tardiness problem Article

Koulamas, C. (1997). Decomposition and hybrid simulated annealing heuristics for the parallel-machine total tardiness problem . NAVAL RESEARCH LOGISTICS, 44(1), 109-125. 10.1002/(SICI)1520-6750(199702)44:1<109::AID-NAV7>3.0.CO;2-E

cited authors

  • Koulamas, C

authors

abstract

  • A polynomial decomposition heuristic is developed for the parallel-machine tardiness problem (P//T̄) by extending the decomposition principle embedded in the single-machine tardiness problem (1//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//T̄ problem is also presented. Computational results demonstrate the efficiency and effectiveness of the decomposition heuristic. © 1997 John Wiley & Sons, Inc.

publication date

  • January 1, 1997

published in

start page

  • 109

end page

  • 125

volume

  • 44

issue

  • 1