带资源空窗期的资源投入型问题的建模与优化

Modeling and Optimization of Resource Investment Problem with Resource Window

摘要:

以飞机移动式装配线为背景，在基本资源投入型问题的基础上考虑资源空窗期约束，建立以最小化资源使用总成本为目标的数学模型.针对该模型设计了一种构造启发式算法，并提出了非关键任务优先级决策规则.考虑空窗期约束特点，以连续排入的两个非关键任务间结果最优的启发式规则来确定非关键任务位置，并提出以非关键任务优先级和关键任务开始时间为双链表编码的遗传算法，然后将启发式规则嵌套在遗传算法的解码和评估阶段.最后通过数值实验比较启发式算法和遗传算法与CPLEX在求解该问题时的优劣，证明了两种算法的有效性.

Abstract:

Resource investment problem with resource window constraint was considered in the context of aircraft mobile assembly line. A mathematical model was proposed to solve the problem with the objective of the total cost minimization of resource. Firstly, based on the characteristics of the resource window constraint, a constructive heuristic algorithm with non-critical activity priority decision rules was developed to solve small-scale problems. Secondly, a genetic algorithm, which was coded by a double-linked list including non-critical activity priority and critical activity start time and decoded by non-critical activity priority decision rules, was proposed for the large-scale problems. Finally, numerical experiments were carried out to compare the advantages and disadvantages between heuristic algorithm, genetic algorithm and CPLEX, and the effectiveness of the two proposed algorithms was proved.