A simulated annealing heuristic for scheduling to minimize mean weighted tardiness in a flowshop with sequence-dependent setup times of jobs–a case study

The problem of scheduling in a flowshop is considered, with the objective of minimizing the mean weighted tardiness. A case study is carried out in a drill-bit manufacturing industry. The problem encountered in the present study is different from the conventional flowshop scheduling problem in that the setup times are separated from process times and are sequence-dependent. A heuristic algorithm, based on simulated annealing (SA), is developed for scheduling in this flowshop. A method is presented for obtaining the initial seed sequence for the SA algorithm. A new exponential acceptance function and a new scheme for generating the neighbourhood, called the random insertion perturbation scheme (RIPS), are proposed. The stopping criteria make use of the temperature value and the value of freeze counter that is determined by the number of accepted and generated sequences. The SA heuristic is evaluated against existing heuristics and the results of computational evaluation reveal that the proposed heuristic performs much better. © 1997 Taylor & Francis Ltd.