Total-Idle-Time Increment Based Hybrid GA for No-Wait Flowshops with Makespan Minimization

No-wait flowshops with makespan minimization has been proved to be a kind of NP-hard combinatorial optimization problem. To solve this problem, it is equivalently transferred into the problem on total-idle-time minimization in this paper. Different from traditional methods in which objectives are completely computed for a new generated schedule, total-idle-time increment methods are presented in this paper. Whether a new schedule is better or worse than the original one is judged just by the total-idle-time increment, which can reduce computational time considerably. Total-idle-time increment properties are analyzed for fundamental operations of heuristics and evolutional operators. Based on the properties, a fundamental method is introduced for fast evaluating schedules. IHGA (increment based hybrid genetic algorithm) is proposed for the considered problem. In IHGA, the different initialization methods and evolution operators are constructed. The dynamic upgrade strategy on evolution operators probability, the population convergence judgment and also regeneration mechanism are designed to improve the effectiveness of the algorithm. In addition, an iterative improvement procedure is integrated in IHGA as a local search method to further improve the eminent solution in population. IHGA is compared with the best-so-far algorithms RAJ, GR, SA2, TSM and FCH on 120 classical benchmark instances. Computational results show that IHGA outperforms the others in effectiveness. IHGA is better than SA2 and TSM while a little worse than GR, RAJ and FCH in efficiency.