Two Schemes of the Branch and Bound Method for a Flow Shop Total Weighted Tardiness Minimization Problem

Two schemes of the branch and bound method for a flow shop total weighted tardiness minimization problem are suggested in this paper. The first scheme consists in the construction of the schedule in the common order (at the beginning the first work in the schedule is chosen, then the second work, etc.) and the second scheme presupposes the construction of the schedule in the inverse order (at the beginning the last work in the schedule is chosen, then the penultimate work, etc.). It is shown by numerical experiments that the efficiency of the methods strongly depends on the problem's parameters, which can be easily calculated from the initial data. Criteria for choosing the most efficient method for any particular problem are proposed.