Abstract: Aiming at the two-Dimensional Variable-Sized Bin Packing Problem (2DVSBPP),a Relaxed Search Approach (RSA) which supported guillotine process constraints was proposed.By using multi-size bin oriented constructive algorithm,a series of feasible bin groups based on total area of all workpieces were created.The best fit bin group to packing was carried by sorting the created bin groups with their areas.Grouping policy and heuristic rules were applied widely to perform the packing of a single bin.During the packing process for select bin group,a bin-replacing solution would be activated to relax the feasible area of the surplus bins and create a new relaxed bin group once it failed to get a packing solution.The packing process would be continued based on relaxed bin group.Such a process would be executed until a whole solution was obtained.Computational experiments on benchmark problems showed that the proposed algorithm was better than these existing algorithms.

Key words: packing, variable-sized bin, guillotine, heuristic algorithms

摘要： 针对规格板材件的矩形工件排样问题,提出一种支持一刀切工艺约束的放宽式搜索算法,利用多规格板材组合的构造算法,依据工件的总面积形成多种可行的板材组合;根据组合的总面积大小排序,优先选择面积较少的组合进行排样,单片板材的排放采用组化策略和启发式的排样规则;在多规格板材的排样过程中如果排样失败,则针对组合中还未排样的板材所构成的组合进行放宽式替换,再重复上述排样过程,以此搜索最佳板材组合,从而使所有工件可以排放且板材利用率最高。实验结果显示：该算法行之有效,测试结果相对于文献报道的算法具有一定优势。

关键词: 排样优化, 多规格板材, 一刀切, 启发式