.png){kind=icon}
.png){kind=icon}
Return
Dynamic programming-based exact and heuristic algorithms for single machine scheduling with sequence-dependent setups
.png){kind=icon}
PRE
AI
DOI：10.1016/j.eswa.2025.126866.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This study presents a novel algorithmic framework and an inventory flow mixed integer programming formulation designed to minimize total tardiness and the number of setups. The approach decomposes the problem into three stages: intra-family scheduling, family sequence optimization, and family-switch timing. We propose a specialized heuristic with O(n5 log n) complexity efficiently handles intra-family scheduling and is extended to accommodate subfamily groupings. Dynamic programming is employed for family-switch optimization, with state complexity constrained to 2n + 1. In the last stage of algorithmic framework, we propose a branch-and-bound method to handle family-switch timing, utilizing lower bounds derived from the results of previous stages. Our overall proposed branch-and-bound-regulated dynamic programming (B&B- DP) algorithm excels in solving large-scale scheduling problems, demonstrating superior performance against four benchmark methods across 150 test cases. This algorithmic framework extends the capabilities of single- machine scheduling with family setup times to handle a large number of jobs. In our experiments, we show that the proposed algorithm reduces total tardiness by 10%-25% compared to other methods. This research not only advances the state of the art in single-machine scheduling but also provides a scalable and effective framework for addressing complex production scheduling challenges.
Keywords:
Dynamic programming
Branch and bound
Heuristic
Scheduling
Journal
IF:
7.5
Papers:
2.9W
Citations:
10.2W