Scheduling a two-stage assembly problem with separated setup time to minimise total tardiness

The two-stage assembly scheduling problem (TASP) is widely existed in our real-life. Minimising the total tardiness of all jobs is important for increasing customers’ satisfaction. Although a few researchers have focused on such optimisation criterion, the performance of proposed algorithms 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 and a variable neighbourhood search (VNS) are proposed to minimise the total tardiness of all jobs. Both of them contain only one parameter, i.e. maximum CPU time, which needs no turning. In order to guide the search of the branch and bound algorithm, lower and upper bounds and dominance rules are proposed. In order to avoid VNS falling into local optima, three neighbourhoods and a novel shaking subroutine are proposed. Experimental results show that the proposed VNS outperforms all existing algorithms on thousands of large scale TASPs generated randomly. Branch and bound algorithm can not only ensure the optimal schedule for small scale TASPs but also enhance the search ability of the proposed VNS to some extent.