Abstract: To solve flow shop scheduling problem with the makespan minimization criterion，a bottleneck focused heuristic algorithm was proposed according to the characteristics of workpiece time.Different machines generally had different load，to construct initial workpiece sequence，this characteristic was fully used.The workpieces with shorter processing time before bottleneck stage and with longer processing time after bottleneck stage were processed priority.At every stage before or after bottleneck，the workpiece sequence was adjusted according to features of workpiece processing time before or after bottleneck if there were workpieces waiting to be processed.Finally，workpiece adjacent pairwise interchanges and insertion operation were used to improve the initial scheduling.The proposed heuristic algorithm was performed well when bottleneck tends to middle stage or workpiece processing time at bottleneck tends to increase.The data experimental results indicated the effectiveness of the proposed approach.

Key words: flow shop, scheduling, bottleneck, heuristic algorithms, makespan

摘要： 针对最小化时间表长的流水车间调度问题，提出一种根据工件加工时间特征构建工件调度的瓶颈指向启发式算法。首先，为构建初始工件排序，充分利用各机器负荷一般不相等的特点，瓶颈阶段前加工时间较短而之后加工时间相对较长的工件优先开始加工；其次，当有工件等待加工时，根据工件在瓶颈机器前或后加工时间的特征调整工件加工顺序；最后，采用邻近工件成对交换和插入的方式改进初始调度。当瓶颈机器趋于中间阶段，或瓶颈机器上工件的加工时间趋于增加时，求解效果较好。数据实验表明算法是有效的。

关键词: 流水车间, 调度, 瓶颈, 启发式算法