A Lower Bound Guided Hierarchical Approach for a Two-Stage Scheduling Problem

Motivated by a challenging and common production scenario in the discrete manufacturing industry, we study a two-stage scheduling problem where sub-components are processed in the first stage and then grouped together to complete the final products. Our goal is to minimize the completion time of the last product, i.e., the makespan. We first propose a novel Mixed Integer Linear Programming (MILP) model to formally define the problem, which is capable of finding optimum solutions for small-scale problems. To tackle the practical challenge of large-scale problems, we design an efficient lower-bound guided hierarchical heuristic (LBGH) to produce high-quality solutions within a reasonable amount of time. Numerical experiments demonstrate that the LBGH outperforms state-of-the-art meta-heuristics in terms of solution quality and computational efficiency.