Two-machine hybrid flowshop scheduling with identical jobs: Solution algorithms and analysis of hybrid benefits

Abstract

We study two-machine hybrid flowshop scheduling with identical jobs. Each job consists of two tasks, namely a flexible task and a fixed task. The flexible task can be processed on either machine, while the fixed task must be processed on the second machine. The fixed task can only be processed after the flexible task is finished. Due to different technological capabilities of the two machines, the flexible task has different processing times on the two machines. Our goal is to find a schedule that minimises the makespan. We consider two variants of the problem, namely no buffer and infinite buffer capacity between the two machines. We present constant-time solution algorithms for both variants. In addition, analysing the relationship between the hybrid benefits and performance difference between the two machines, we find that, for the infinite-buffer case, increasing the technological level of the second machine does not necessarily increase the hybrid benefits.

Keywords:

• Hybrid flowshop
• optimal algorithm
• makespan

Acknowledgements

We thank the anonymous referees for their constructive comments, which help improve the quality of the paper significantly.

Notes

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported in part by the National Natural Science Foundation of China under [grant number 11571013]; the General Research Project of the Education Department of Zhejiang Province under [grant number Y201636738]; the Doctoral Foundation of Ningbo Dahongying University under [grant number 1320169007].