A knowledgeable simulated annealing scheme for the early/tardy flow shop scheduling problem

The present paper reports on a new approach to applying simulated annealing to the flow shop scheduling problem with early/tardy costs. This approach incorporates the simulated annealing methodology with problem-specific knowledge, which is given in a table called the ‘Backward-Forward Exchange Priority Table’. Performance of the proposed method is tested on randomly generated problems and is compared to those of two formal simulated annealing schemes. Finally, it is shown that solutions obtained by the proposed method are superior to those of formal annealing schemes.