Improved repair-based constraint satisfaction method for flow shop scheduling

Repair-based constraint satisfaction method is one of the two main categories of constraint satisfaction (CS) algorithms. It starts with an arbitrary completed solution, and then resolves conflicts by local repair. An improved repair-based constraint satisfaction (1RCS_WT) method for flow shop scheduling is proposed. In IRCS_WT, a heuristic rule of largest weighted tardiness priority (LWT) is proposed for variables ordering procedure, and a new heuristic of largest tardy and early variables exchanging (LTEE) is designed to escape from local optima. Computational experiments of 31 flow shop scheduling problems are conducted to compare the IRCS_WT with other two heuristic methods, extended NEH and filtered beam search (FBS), as well as genetic algorithm (GA). The results show that IRCS_WT significantly outperforms the competitors with the same running time.