A blocking flowshop scheduling problem with material handling constraint

We develop heuristic algorithms to solve a two-stage blocking flowshop scheduling problem with material handling constraint. Such problems are common in production system design, service facilities design, or specialty jobs such as petrochemical processing. The absence of intermediate buffers between the stages here causes the blocking of jobs when downstream machines are occupied. The objective is to minimize the makespan. We show that this problem is strongly NP-hard. We then explore the special structural features of this problem and develop two problem-specific solution construction heuristics for different job processing time scenarios. We show that these heuristics can speed up the solution evolution rate by providing good starting points for a method like a genetic algorithm, particularly when the problem is large and computational efficiency may be paramount.

A blocking flowshop scheduling problem with material handling constraint Academic Article