Dynamic set-up rules for hybrid flow shop scheduling with parallel batching machines

Abstract

An S-stage hybrid (or flexible) flow shop, with sequence-independent uniform set-up times, parallel batching machines with compatible parallel batch families (like in casting or heat treatments in furnaces, chemical or galvanic baths, painting in autoclave, etc.) has been analysed with the purpose of reducing the number of tardy jobs (and the makespan); in Graham’s notation: FPB(m₁, m₂, …, m_S)|p-batch, . Jobs are sorted dynamically (at each new delivery); batches are closed within sliding (or rolling) time windows and processed in parallel by multiple identical machines. Computation experiments have shown the better performance on benchmarks of the two proposed heuristics based on new formulations of the critical ratio (CR_setup) considering the ratio of allowance set-up and processing time in the scheduling horizon, which improves the weighted modified operation due date rule.

Keywords:

• batch scheduling
• parallel batches
• dispatching rules
• critical ratio
• time window

Acknowledgements

The authors would like to thank the anonymous referees for the in-depth observations.