Robust scheduling for a two-stage assembly shop with scenario-dependent processing times

Abstract

Recently, finding solutions to assembly flowshop scheduling problems is a topic of extensive discussion in research communities. While existing research assumes that job processing times are constant numbers, in several practical situations, due to several external factors like machine breakdowns, working environment changes, worker performance instabilities, and tool quality variations and unavailability, job processing times may vary. In this study, therefore, we address a two-stage assembly flowshop scheduling problem with two scenario-dependent jobs processing times to minimise the maximum makepsan among both scenarios (called robust makespan) In view of the NP-hard nature, we first derive a dominance property and a lower bound to propose a branch-and-bound algorithm to find a permutation schedule with minimum makespan. Following that, we use Johnson’s rule to propose eight polynomial heuristics for finding near-optimal solutions. Furthermore, we propose four cloud theory-based simulated annealing (CSA) hyper-heuristic algorithms incorporating seven low level heuristics to solve a robust two-stage assembly flowshop problem with scenario-dependent processing times. Finally, we empirically evaluate the effectiveness of all the proposed algorithms in minimising the robust makespan.

KEYWORDS:

• Robust assembly flowshop scheduling
• cloud simulated annealing
• hyper-heuristics
• low level heuristics
• scenario-dependent processing times

Acknowledgements

The authors thank editors and three reviewers for their useful suggestions and helpful comments on the earlier version of our paper.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This study was supported in part by the Ministry of Science and Technology of Taiwan [grant number MOST 108-2410-H-035-046].