An ant colony optimization-based hyper-heuristic with genetic programming approach for a hybrid flow shop scheduling problem

Abstract

The problem of a k-stage hybrid flow shop (HFS) with one stage composed of non-identical batch processing machines and the others consisting of non-identical single processing machines is analyzed in the context of the equipment manufacturing industry. Due to the complexity of the addressed problem, a hyper-heuristic which combines heuristic generation and heuristic search is proposed to solve the problem. For each sub-problem, i.e., part assignment, part sequencing and batch formation, heuristic rules are first generated by genetic programming (GP) offline and then selected by ant colony optimization (ACO) correspondingly. Finally, the scheduling solutions are obtained through the above generated combinatorial heuristic rules. Aiming at minimizing the total weighted tardiness of parts, a comparison experiment with the other hyper-heuristic for the same HFS problem is conducted. The result has shown that the proposed algorithm has advantages over the other method with respect to the total weighted tardiness.