论文部分内容阅读
This paper addresses the performance of scheduling algorithms for a two-stage no-wait hybrid flowshop environment with processing flexibility across stages,where each stage has one or more identical parallel machines.Each job,composed of two operations,must be processed from start to completion,without any interruption either on or between the two stages.At the completion time of a jobs stage-1 operation,if every stage-2 machine is busy,its stage-2 operation is allowed to be started on the stage-1 machine processing its stage-1 operation.Whenever there is a stage-2 machine available,the remaining part of its stage-2 operation must be moved to stage 2.The objective is to minimize the makespan.We first prove that even for the special case with only one machine at each stage,this problem is strongly NP-hard,then we provide approximation heuristics for various cases with different amount of machines at each stage and present instances to show that the worst case bounds are tight for all the algorithms except one.