An evolutionary algorithm for no-wait flowshop problems with flowtime minimization

In this paper, no-wait flow shop scheduling problem with flowtime minimization is considered. Objective increment properties are analyzed and proved for fundamental operations of heuristics. With these properties, whether a new generated schedule is better or worse than the original one is only evaluated by objective increments, instead of completely calculating objective values as the traditional algorithms do, so that the computational time can be considerably reduced. An evolutionary algorithm (EA) is proposed for the considered problem. The initial population with two members is generated by different heuristics. After crossover, the disturb cycles which consist of a mutation operator and strengthen approaches are conducted to the offspring. EA is compared with the best-so-far algorithms SRTS, PH1p and DPSO_vnd on 110 benchmark instances. Experimental results show that EA outperforms the others on effectiveness but is a little worse than DPSO_vnd on efficiency.