Minimizing total completion time in two-stage hybrid flow shop with dedicated machines
Minimizing total completion time in two-stage hybrid flow shop with dedicated machines
复制标题
DOI：
10.1016/j.cor.2010.10.009
复制
发表时间：
2011-07
期刊：
影响因子：
--
通讯作者：
Jaehwan Yang
中科院分区：
文献类型：
--
作者：
Jaehwan Yang
研究了一类两阶段混合流水车间调度问题的总完工时间最小化问题。在阶段1有一台机器，在阶段2有两台机器。每个作业必须在阶段1的单台机器上处理，并且根据作业类型，作业在阶段2的两台机器中的任何一台上处理。首先，我们介绍了问题，并建立了问题的几个变体的复杂性。对于一般情况，我们引入了两种启发式方法，并为每一种启发式方法找到了相对误差的最坏情况界。然后，我们找到了一些特殊情况下的最优解过程。我们还为机器1上的处理时间相同的特殊情况开发了一种启发式方法，并找到了相对误差的最坏情况边界。最后，我们对启发式进行了实证评价。
We consider the problem of minimizing total completion time in a two-stage hybrid flow shop scheduling problem with dedicated machines at stage 2. There exist one machine at stage 1 and two machines at stage 2. Each job must be processed on the single machine at stage 1 and depending upon the job type, the job is processed on either of the two machines at stage 2. First, we introduce the problem and establish complexity of several variations of the problem. For the general case, we introduce two heuristics and find a worst case bound on relative error for each of the heuristics. Then, we find optimal solution procedures for some special cases. We also develop a heuristic for a special case where processing times on machine 1 are identical and find a worst case bound on relative error. Finally, we empirically evaluate the heuristics.