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 proposed that differ in that a schedule in one scheme is constructed in a natural order (first, one chooses the first job in the schedule, then the second, etc.), whereas, in the second scheme, a schedule is constructed in the reverse order (first, one chooses the last job in the schedule, then the penultimate job, etc.). It is shown by numerical experiments that the efficiency of the methods essentially depends on the parameters of the problem, which can be easily calculated from the initial data. A criterion for choosing the most efficient method (from among the two) is proposed for any particular problem. © 2013 Pleiades Publishing, Ltd