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.