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

JianChao Luo, ZhiQiang Liu, JiaLi Fan, Jun-Qiang Wang, YanXiang Feng and Jun Xu

International Journal of Production Research, 2025, vol. 63, issue 7, 2456-2482

Abstract: 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.

Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2024.2403766 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tprsxx:v:63:y:2025:i:7:p:2456-2482

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TPRS20

DOI: 10.1080/00207543.2024.2403766

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().