集装箱装船问题是评价一个港口业务能力的重要指标,关系到港口的工作效率和工作能力。为了减少集装箱装船时间,必须得减少集装箱装船时翻倒的次数。预翻倒问题正是为了减少集装箱装船的翻倒次数,提高装船效率而提出来的。集装箱装船的过程中,依据较高的权重或者更远的目的地来划分集装箱的优先级;优先级高的集装箱通常要比优先级低的集装箱优先装船。因此,在堆场中临时存放箱子时,更偏好于高优先级的集装箱放置在低优先级的集装箱之上。然而,在实际运作中,堆场接收到集装箱之后,高优先级的集装箱很可能会埋在低优先级的集装箱之下。为了提高装船的效率,在装船之前就需要一个准备工作,把高优先级的集装箱预先翻倒在低优先级的集装箱之上,这个准备工作就是集装箱预翻倒,本文所研究的问题就是集装箱预翻倒问题。基于集装箱在贝位内的分布状况,对集装箱进行分类标记并指明各个分类的意义和用途,与此同时对于集装箱翻倒的类型也进一步细化。在此基础上,提出了一种两阶段循环的启发式方法。第一阶段:在当前的集装箱分布状况下,首先,EmptyOneStack过程是一个以二次规划为核心的模拟过程,模拟选择一个堆,并将该堆内的全部集装箱清空翻倒至其他堆。需要注意的是,EmptyOneStack过程只是一个模拟过程,在第一阶段并不会执行该过程。其次,IntegalOneStack是一个0-1规划,旨在选择一个堆,将该堆内的“坏”集装箱翻倒至其他健康堆,并保持健康堆的状态不变。经过一次IntegalOneStack过程后,集装箱翻倒会被执行,贝内集装箱分布也会被更新。在上述集装箱分布下,循环EmptyOneStack过程和IntegalOneStack过程,直到没有IntegalOneStack过程可以执行。在第二阶段:在EmptyOneStack过程产生的模拟清空堆中选择一个能够使得未来集装箱翻倒更加容易的堆,并将贝内的集装箱分布更新至被选择的状态。重复第一阶段和第二阶段,直到贝内分布满足预翻倒问题的要求。本文用一个案例展示了算法的执行过程并且通过大量的数据实验验证了算法的有效性。首先,本文算法在处理较大规模的翻倒时,翻倒次数远小于Bortfeldt算法;并且在中小规模的翻倒中,本文翻倒次数接近Bortfeldt算法最后,本文在Bortfeldt and Forster(2012)的基础上,提升了预翻倒问题的下界。