Abstract: On the background of aircraft moving assembly line,the resource investment problem based on the activities splitting was researched,and a mathematical model with objective function of minimizing the resource usage cost was built.Through the determination that whether to split and where to split the scheduling job,a heuristic algorithm with an improved serial schedule generation mechanism was designed to obtain the upper and lower bounds of resource requirements.A genetic algorithm was designed to code resource requirements and assignments priority list at the same time.By solving sub-problem Resource Constrained Project Scheduling Problem (RCPSP),the feasibility of resource requirements at a given time limit could be judged,and the optimal combination of resources was selected as final objective.Numerical experiments showed that for small instances,approximate exact solutions could be obtained;while for large-scale instances compared with the existing literature,the algorithm could improve on the accuracy of 5.57%.

Key words: resource investment problem, activity split, genetic algorithms, scheduling, model

摘要： 为了研究飞机移动装配线中基于作业可拆分的资源投入问题,建立以最小化资源使用成本为目标的作业调度数学模型。通过对作业调度过程中拆分与否及拆分位置的决策,在改进传统串行调度生成机制的基础上,设计了启发式算法求取资源需求上下界。针对所建立模型,提出以资源需求及作业优先级列表为编码的遗传算法,通过求解资源受限项目调度问题的子问题来评判对应资源需求在给定工期下的可行性,从而评估与优化项目不同资源的投入组合。数值实验表明,对于小规模问题,该算法可以求得近似精确解;对于大规模问题,相比现有文献,在算法求解精度上可提升5.57%。

关键词: 资源投入问题, 作业可拆分, 遗传算法, 调度, 模型