Hybrid Flow Shop Sequence Dependent Group Scheduling (HFSDGS) problems gathered much attention from researchers in recent years. But, the combination of blocking constraints and Group Technology (GT) principles in the Hybrid Flow Shop (HFS) configuration has not been extensively treated by academics as it must. In the present work, we aim to contribute to the HFSDGS literature through two new Mixed Integer Linear Programming (MILP) models for minimizing makespan of the blocking HFSDGS problem. Also we define two new constraint programming (CP) based models. Experimental studies are conducted in our studies to compare the performances of the new models with other models dealing with the same problem. When dealing with problems with small sizes, the CP models show some promising results so we intend to extend the studies to medium and large sizes instances.

Whenever grouping technologies GT principles are applied in scheduling activities, a Group Scheduling (GS) problem arises. So we consider both sub-problems: arrangement of groups and the arrangement of jobs within the group. Jobs belonging to the same group are processed on the same machine sequentially with no interruption by jobs of other groups. A setup is required each time we switch from one group to the next one. Since the flow shop has no intermediate buffers, the blocking constraints arise:  a job, which is completed the processing of its operation on one machine, cannot leave it until the next machine belonging to the next stage is idle. The objective is to minimize the completion time of the last job belonging to the last group of the sequence.

Key words:

Hybrid flow shop group scheduling problem, blocking, Mixed integer linear programming, Constraint programming, makespan