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

摘要

The problem of minimising the overall completion time for the two-machine flow shop problem with unit execution time (UET) tasks and arbitrary time delays is known to be unary N P-hard. Two heuristic algorithms to solve this problem along with their worst-case analyses are presented. We also discuss computational experiments we conducted to study the average-case performance of these two heuristics using simulation and statistical sampling methods.