An Iterative Branch-and-bound Approach for Complex Product Assembly Station Scheduling Problem

This paper proposes an iterative branch-and-bound (IB&B) approach for complex product assembly station scheduling problems (CPASSP) to minimize the total weighted tardiness (TWT). First, an iterative adjusting mechanism for upper bounds is designed to improve the efficiency of the algorithm. The upper bound in the proposed algorithm is set directly without a method to obtain a feasible solution. If no feasible solution is found, the upper bound is adjusted and the branch-and-bound component is executed again. Second, a station-based branching strategy is developed to decompose the CPASSP problem, which is able to avoid the many-to-one situations typically encountered with task-based branching strategies. Moreover, a disjunctive graph for CPASSP is formulated to represent and evaluate a schedule. The proposed IB&B is compared with alternative branch-and-bound approaches and a mixed integer linear programming (MILP) model implemented by CPLEX solver on four test instances of different scales. Experimental results demonstrate that the proposed IB&B is more efficient and obtains optimal solutions with less computation time.