A new constraint programming approach for the orthogonal packing problem

被引：54

作者：

Clautiaux, Francois ^{[1
]}

Jouglet, Antoine ^{[1
]}

Carlier, Jacques ^{[1
]}

Moukrim, Aziz ^{[1
]}

机构：

[1] Univ Technol Compiegne, CNRS, UMR 6599, F-60205 Compiegne, France

来源：

COMPUTERS & OPERATIONS RESEARCH | 2008年 / 35卷 / 03期

关键词：

two-dimensional orthogonal packing problem; constraint programming; scheduling; energetic reasoning;

D O I：

10.1016/j.cor.2006.05.012

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

The two-dimensional orthogonal packing problem (2OPP) consists in determining if a set of rectangles can be packed in a larger rectangle of fixed size. We propose an exact method for 2OPP, based on a new constraint-based scheduling model. We provide a generalization of energetic reasoning techniques for the problem under investigation. Feasibility tests requiring the solution of subset-sum problems are described. Computational results confirm the efficiency of our method compared to others in the literature. (c) 2006 Elsevier Ltd. All rights reserved.

引用

页码：944 / 959

页数：16

共 26 条

[1]

Baker KR., 1974, Introduction to Sequencing and Scheduling

[2] Satisfiability tests and time-bound adjustments for cumulative scheduling problems [J].

Baptiste, P ;

Le Pape, C ;

Nuijten, W .

ANNALS OF OPERATIONS RESEARCH, 1999, 92 (0) :305-333

[3]

BAPTISTE P, 2001, INT SERIES OPERATION, V39

[4] Sweep synchronization as a global propagation mechanism [J].

Beldiceanu, N ;

Carlsson, M ;

Thiel, S .

COMPUTERS & OPERATIONS RESEARCH, 2006, 33 (10) :2835-2851

[5]

BELDICEANU N, 2001, LECT NOTES COMPUTER, V2239, P377

[6] The two-dimensional finite bin packing problem. Part I: New lower bounds for the oriented case [J].

Boschetti, Marco A. ;

Mingozzi, Aristide .

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2003, 1 (01) :27-42

[7]

Caprara A, 2005, LECT NOTES COMPUT SC, V3509, P377

[8] On the two-dimensional knapsack problem [J].

Caprara, A ;

Monaci, M .

OPERATIONS RESEARCH LETTERS, 2004, 32 (01) :5-14

[9]

CARLIER J, 2005, IN PRESS COMPUTERS O

[10]

CARLIER J, 2005, IN PRESS EUROPEAN J

← 1 2 3 →