Analysis of Classes of Heuristics for Scheduling a Two-Stage Flow Shop with Parallel Machines at One Stage
Analysis of Classes of Heuristics for Scheduling a Two-Stage Flow Shop with Parallel Machines at One Stage
复制标题
DOI：
10.1057/jors.1995.28
复制
发表时间：
1995-02
影响因子：
3.6
通讯作者：
Bo Chen
中科院分区：
文献类型：
--
作者：
Bo Chen
本文研究了一阶并行机器的两阶流水车间调度问题。对于求解强np困难的最小完工时间计划，已有文献提出了一些有效的启发式方法。本文通过引入几类启发式来丰富启发式集，并证明了现有的启发式可以被纳入该分类方案。此外，我们还对该类的最坏情况性能进行了完整的理论分析。本文还对几种典型启发式算法的平均性能进行了一些经验评估和比较。
This paper addresses two-stage flow shop scheduling with parallel machines at one stage. For finding a minimum makespan schedule, which is strongly NP-hard, some efficient heuristics have been proposed in the literature. In this paper we enrich the set of heuristics by introducing a few classes of heuristics, and show that the existing heuristics can be put into this classification scheme. Furthermore, we give a complete theoretical analysis of the worst-case performance of the classes. Some empirical evaluations and comparisons for the average-case performance of a few typical heuristics in the classes are also performed.