An optimisation model and algorithm for job scheduling with extra resource allocation in shipbuilding
针对船舶建造中因资源瓶颈导致延误的问题，建立数学模型优化工作调度，提出两阶段元启发式算法在考虑额外资源成本下最小化完工时间，并用实际数据验证。
The shipbuilding production process relies on modular manufacturing, where different sections of vessels are processed at separate workspaces in parallel. Bottlenecks often arise due to limited resources at these workspaces, increasing the risk of missing contracted completion dates and potentially leading to significant financial losses for shipbuilders. This paper examines a strategy to alleviate these bottlenecks by allocating additional resources to workspaces, despite the associated costs. We developed a mathematical program to optimise job scheduling across workspaces, minimising the makespan while accounting for the option of extra resources. As our model is a variant of the parallel machine scheduling problem, which is NP-hard, we propose a two-stage meta-heuristic algorithm that quickly finds an optimal or near-optimal solution. The first stage uses a genetic algorithm with a specialised reproduction strategy to generate a high-quality schedule without additional resources. The second stage employs a tabu search algorithm to enhance solutions with extra resources, further reducing the makespan while considering added costs. We validate our model and algorithm with data that shares the similar statistical characteristics of a real-world ship manufacturer. Sensitivity analyses on extra resource costs are conducted to provide practical insights into when additional resources are advantageous despite their expense.