Block approach to the cyclic flow shop scheduling

• We consider cyclic flow show problem with setups with minimization of cycle time.
• New elimination “block” properties are proposed.
• Block properties are used for neighborhood search acceleration.
• Implementation in tabu search algorithm and verification on benchmarks instances.

The cyclic flow show problem with machine setups is considered in this paper. It relies in producing of a set of certain elements in fixed intervals of time (cycle time). Process optimization is reduced to minimization of cycle time, i.e., the time after which the next batch of the same elements may be produced. Since the problem is strongly NP-hard, in order to solve it an approximate algorithm was used. There is presented a graph model of a problem and the so called block eliminating properties capable of reducing, in a significant way, neighborhood used in the tabu search algorithm. Conducted computational experiments confirm high efficiency of the proposed technique.