Abstract: Based on a background to the shops in the mould manufacturers, It considers a two-stage flexible flow shop scheduling problem subject to release dates, where the first stage is made up of unrelated machines and tasks have group constraint. Based on defining two-stage flexible flow shop with head group constraint and giving its mathematical description systematically, a mathematic model is formulated where the objective is to find a schedule that minimizes makespan. Because this problem is NP-hard, a constructive heuristic algorithm H′ is proposed and its lower bound(LB) is proved. In addition, some classical heuristics are developed. In order to test the efficiency of the algorithm, sets of examples are designed. Compared to the classical developed heuristics, the performance of algorithm H′ is more superior than other three heuristics, and algorithm H′ solves large sized problems in a reasonable solution time, which is significant to the application in the shops of mould makers.

Key words: Flexible flow shop, Head group constraint, Heuristic