Abstract: To deal with stack selection problem with the known item numbers and retrieval order during the loading process，in which the longest（and/or heaviest） incoming items are placed at the bottom in needed and the target is to occupy as few stacks as possible.This problem is reduced to an extension of bin packing problem named A-shaped bin packing problem with ordered constraint.This is a new combinatorial optimization problem which has many applications in practice，such as in warehousing stack entering in the yard management.A constraint satisfaction model is given，and a hybrid solving algorithm is designed based on constraint satisfaction technology embedding with Best-Fit approximation algorithm.Simulative examples illustrate the effectiveness of the proposed algorithm for large-scale storage yard problem with complex constraints over the existing bin packing heuristics.

Key words: stack selection problem, yard management, bin packing problem, constraint satisfaction, bin packing heuristics

摘要： 入库堆垛问题普遍存在于堆场作业管理中，是在货物数目和出库顺序已知的前提下，要求较长（重）的货物置于较短（轻）的货物下方，目标是实现占用垛位数最少。通过问题分析，将其归结为一类带顺序约束的A形装箱问题，并建立了约束满足模型，设计了嵌入经典装箱启发式的约束满足求解算法。实验表明，该算法对于求解复杂约束下的大规模堆场问题较现有的装箱启发式有一定程度的改善。

关键词: 堆垛问题, 堆场管理, 装箱问题, 约束满足, 装箱启发式