A heuristic method for two-stage hybrid flow shop with dedicated machines
A heuristic method for two-stage hybrid flow shop with dedicated machines
复制标题
DOI：
10.1016/j.cor.2012.07.015
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Shijin Wang;Ming Liu
中科院分区：
文献类型：
--
作者：
Shijin Wang;Ming Liu
研究了一个两阶段的带专用机的混合流水车间调度问题，其中第一阶段包含一台公共关键机，第二阶段包含多台专用机。每个作业必须首先在第一阶段的关键机器上进行处理，然后根据作业类型，在第二阶段，作业将在其类型的专用机器上进一步处理。目标是最小化最大完工时间。针对该问题，提出了一种基于分支定界（B&B）算法的启发式求解方法。几个下界的推导和四个建设性的启发式来获得初始上界。然后，三个优势性质，以提高所提出的启发式方法的性能。两个不同的问题类别，每个问题配置进行了广泛的计算实验。结果表明，所提出的启发式方法可以产生非常接近最优的问题，多达100个工件和5个专用机器在60秒内。与其他两种元启发式方法的解的比较也证明了所提出的启发式方法的更好的性能。
This paper considers a two-stage hybrid flow shop scheduling problem with dedicated machines, in which the first stage contains a single common critical machine, and the second stage contains several dedicated machines. Each job must be first processed on the critical machine in stage one and depending on the job type, the job will be further processed on the dedicated machine of its type in stage two. The objective is to minimize the makespan. To solve the problem, a heuristic method based on branch and bound (B&B) algorithm is proposed. Several lower bounds are derived and four constructive heuristics are used to obtain initial upper bounds. Then, three dominance properties are employed to enhance the performance of the proposed heuristic method. Extensive computational experiments on two different problem categories each with various problem configurations are conducted. The results show that the proposed heuristic method can produce very close-to-optimal schedules for problems up to 100 jobs and five dedicated machines within 60s. The comparisons with solutions of two other meta-heuristic methods also prove the better performance of the proposed heuristic method.