A Branch and Bound Algorithm for Minimizing Total Tardiness of a Two-Stage Assembly Problem

Existing algorithms for the two-stage assembly scheduling problem (TASP) ignores the setup time and depends on four or more fine-tuned parameters. This work focuses on TASPs with separated setup time. There are multiple and one machine at stages one and two, respectively. A branch and bound algorithm which contains only one parameter is proposed to minimize the total tardiness of all jobs. In order to guide the search of the branch and bound algorithm, lower and upper bounds and dominance rules are proposed. Experimental results show that the proposed branch and bound algorithm outperforms the state-of-the-art method.