Analysis of heuristics for the UET two-machine flow shop problem with time delays (Q2482380)

This paper considers a two-machine flow-shop problem with unit processing times and arbitrary change-over times (denoted as time delays by the authors) of the jobs from the first to the second machine. The objective is to minimizie the makespan. Two heuristic algorithms are considered: one algorithm uses an arbitrary ordering of the jobs on machine 1, and the other algorithm processes the jobs on machine 1 according to a non-increasing order of the change-over times. On machine 2, jobs are processed as early as possible according to the chosen job permutation. For both algorithms, a worst-case analysis is presented. Moreover, computational experiments have been done in order to study the average-case performance of the heuristics using simulation and statistical sampling methods.