A computational evaluation of constructive heuristics for the parallel blocking flow shop problem with sequence-dependent setup times

Summary: This paper addresses the scheduling problem in a parallel flow shop environment without buffers between machines and with sequence-dependent setup times to minimize the maximum completion time of jobs. 36 heuristics were tested, with one designed specifically for considerable setup times showing good performance. A combined heuristic approach was also proposed for finding good solutions in a short CPU time.