Single machine scheduling problems with sequence-dependent setup times and precedence delays

Abstract

Abstract Sequence-dependent setup times and precedence delays occur frequently in various production environments. This study investigates the single machine scheduling problem with setup times and precedence delays that occur in an amplifier assembly company. This study proposes a novel mixed-integer linear programming model and a lean iterated greedy algorithm to minimize the makespan for this problem. Based on the property of delayed precedence constraints, the lean iterated greedy (LIG) algorithm uses a simple but effective lean construction mechanism that can discard infeasible solutions to reduce the waste of unnecessary searches and quickly converge to the (near) global optimum. The computational results show that LIG significantly outperforms the state-of-the-art algorithm in terms of solution quality and computational efficiency. This study mainly contributes to providing a simple, effective, and efficient algorithm that can facilitate industrial applications and serve as a new benchmark approach for future research.