Surrogate-assisted Backtracking Search Optimization for Two-Stage Hybrid Flow Shop Scheduling

Two-stage scheduling problems frequently arise in practical domains such as manufacturing, logistics, and service systems, where inter-stage coordination is crucial to overall performance. This work investigates a two-stage hybrid flow shop problem (TSHFSP) with non-identical parallel machines at each stage. Each machine’s processing capacity is determined by the number of processing environments it can provide, and each job requires two no-wait operations. Moreover, a sequence-dependent machine setup is needed when switching between different processing environments. The addressed TSHFSP is formulated as a lexicographic optimization model, where the primary objective is to minimize the makespan using a mixed-integer linear programming model, and the secondary objective is to minimize the total job waiting time using a linear programming model. By sequentially solving these two models using CPLEX, an optimal solution can be obtained for small-sized problems. For larger-sized problems, a designed backtracking search optimization algorithm (DBSA) is employed, which is a population-based metaheuristic. However, DBSA requires a large number of evaluations, making it computationally expensive when facing complex problems. To address this issue, a pairwise comparison-based surrogate model using extreme gradient boosting (XGBoost) is proposed, resulting in the development of an online XGBoost-assisted DBSA (OXGB-DBSA). The experimental results demonstrate that DBSA consistently achieves superior performance compared with the competing metaheuristics across all problem scales. Additionally, the OXGB-DBSA preserves solution quality while substantially reducing computational time, achieving approximately 46%–57% time savings on large-scale instances.