List-based threshold-accepting algorithm for zero-wait scheduling of multiproduct batch plants

Abstract

A novel list-based threshold-accepting (LBTA) algorithm is proposed for solving the zero-wait (ZW) scheduling problem. The LBTA algorithm belongs to the class of threshold-accepting algorithms, but the acceptance probability decreases based on a list that is rejuvenated and adapted according to the topology of the solution space of the problem. A probabilistic steepest optimization strategy was adapted to search the solution space effectively. The effectiveness of the LBTA method is illustrated through case studies from scheduling literature which were formulated as mixed-integer linear programming and mixed-integer nonlinear programming models. The performance of the LBTA algorithm is also compared with that of the simulated annealing (SA) algorithm for a large number of various problem sizes. The proposed algorithm gives optimal solutions for small- to moderate-size ZW scheduling problems within a very short time and shows much superior computational performance compared to SA for large-size problems.