Abstract: The Airplane Refueling Problem(ARP)is a nonlinear combinatorial optimization problem with a fractional objective function and its complexity is still open. We use a permutation to model the precedence relations between pairwise jobs. One kind of this problem is called “Completely Reverse Order Class”. The Completely Reverse Order Class of the N-Vehicle Explore Problem(NVEP)is considered is considered one of the most difficult scenarios that consume exponential time in Dynamic Programming algorithm. In this paper, we analyze data structure of this problem and find two kinds of special structure in the “Completely Reverse Order Class”. Theorem 1 describes a kind of special structure, and states that there is a unique solution that satisfies the necessary condition of this kind of special structure, and it is optimal as well. Theorem 2 describes a kind of structure which can be solved in polynomial time. When relationship between fuel loading and fuel consumption rate satisfies the conditions of theorem 2, the corresponding instance can be solved in polynomial time.

Key words: airplane refueling problem, necessary condition of optimal solution, unique solution, scheduling problem

摘要： 航空器供油问题是一类非线性组合优化问题,其目标函数为分式形式,该问题目前不存在多项式时间算法,也未被证明是NP完全问题。一般可以用置换来刻画n架飞机的一个供油顺序。该问题中有一类实例被称为“完全逆序类”,“完全逆序类”用动态规划算法求解计算时间为O(n2ⁿ),具有指数时间复杂度。本文通过对该“完全逆序类”问题做进一步分析,发现在“完全逆序类”中也存在着多项式时间可解的情况。定理1研究一类一次可解的情况,若问题满足定理1的条件,则求解一次即可找到其最优解;定理2研究一类多项式时间可解的情况,当问题满足定理2的条件时,其最优解可在多项式时间内获得。

关键词: 航空器供油问题, 最优解必要条件, 唯一解类, 排序