AN EXACT BRANCH-AND-BOUND ALGORITHM FOR SERU SCHEDULING PROBLEM WITH SEQUENCE-DEPENDENT SETUP TIME AND RELEASE DATE

This paper concentrates on the scheduling problem in seru production system (SPS), which is a new-type advanced system with high manufacturing flexibility to response the volatile market. Motivated by practical scenarios, the seru scheduling problem in this paper considers the sequence dependent setup time and release date to minimize the total weighted tardiness. A mixed integer programming (MIP) model is formulated, and the branch and-bound (B&B) algorithm combining dominance propositions and the lower bound strategy is designed subsequently. Finally, computational experiments are conducted. A series of experimental results show that the proposed B&B algorithm performs very well in finding high-quality solutions, and it can find exact and near-exact solutions for 216 randomly generated instances quickly. Even when CPLEX is unable to solve the problems in five-hour, the B&B algorithm can return optimal solutions for as many as 5 serus and 22 products in a very short CPU time.

Automated summary

This paper focuses on the scheduling problem in Seru production system, considering sequence dependent setup time and release date. A mixed integer programming model and a branch and-bound algorithm are proposed, and computational experiments are conducted. The results show that the proposed algorithm performs well in finding high-quality solutions quickly.