The two-machine flow shop problem with arbitrary precedence relations (Q2366083)

The 2-machine flow shop scheduling problem with arbitrary precedence constraints is considered. The objective is to minimize the makespan. The problem is known to be NP-hard in the strong sense. A branch-and-bound algorithm is proposed for the solution. Lower bounds are computed by solving relaxed problems in which precedence constraints are reduced to a series-parallel form. The problem with series-parallel precedence constraints is \(O(n \log n)\) solvable. Here \(n\) is the number of jobs to be processed. Results of computational experiments with up to 100 jobs are included.