Decomposition and hybrid simulated annealing heuristics for the parallel-machine total tardiness problem
Decomposition and hybrid simulated annealing heuristics for the parallel-machine total tardiness problem
复制标题
DOI：
10.1002/(sici)1520-6750(199702)44:1
复制
发表时间：
1997-02
影响因子：
2.3
通讯作者：
Christos Koulamas
中科院分区：
文献类型：
--
作者：
Christos Koulamas
通过将单机延迟问题 (1/T) 中嵌入的分解原理扩展到并行机设置，针对并行机延迟问题 (PsT) 开发了多项式分解启发式方法。分解产生的子问题通过有效的启发式解决，该启发式产生的解决方案使得任何单个机器上的调度都满足单机分解原则。还提出了针对 P/T 问题的混合模拟退火启发式方法。计算结果证明了分解启发式的效率和有效性。 © 1997 约翰威利父子公司。
A polynomial decomposition heuristic is developed for the parallel-machine tardiness problem (PsT) 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.