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

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