Scheduling coupled tasks with flexible gap for minimisation of makespan

The surface coating process for spacecraft is a critical step in aerospace manufacturing, where successive coating layers require curing intervals to prevent defects. This manufacturing process motivates the study of the coupled-task scheduling problem with flexible gaps, aiming to minimise the makespan to enhance productivity. The strong NP-hardness of the problem is proved, which confirms the infeasibility of finding an optimal solution in polynomial time (unless P=NP). Exact and metaheuristic algorithms are designed to handle cases of different scales. For small-scale cases, we propose a tailored branch-and-bound (B&B) method to obtain optimal solutions. Two feasibility tests, problem-specific lower and upper bounds, and a block-combination pruning rule are incorporated to effectively narrow the search space. For large-scale instances, an improved simulated annealing algorithm is proposed with a job-swap-based local search strategy. Computational experiments compare the proposed methods with CPLEX and existing approaches. The results show that the proposed B&B algorithm substantially improves exact-solution capability, while the improved simulated annealing algorithm provides competitive solutions with shorter computational times for large instances. Sensitivity analyses further show that appropriately extending flexible gaps and classifying components according to their time characteristics can provide useful guidance for improving practical scheduling decisions.