| |
Record |
Links |
|
Author |
Pereira, J. |
|
| |
Title |
Procedures for the bin packing problem with precedence constraints |
Type |
|
| |
Year |
2016 |
Publication |
European Journal Of Operational Research |
Abbreviated Journal |
Eur. J. Oper. Res. |
|
| |
Volume |
250 |
Issue |
3 |
Pages |
794-806 |
|
| |
Keywords |
Bin packing; Precedence constraints; Lower bounds; Dynamic programming; Branch-and-bound |
|
| |
Abstract |
The bin packing problem with precedence constraints (BPP-P) is a recently proposed variation of the classical bin packing problem (BPP), which corresponds to a basic model featuring many underlying characteristics of several scheduling and assembly line balancing problems. The formulation builds upon the BPP by incorporating precedence constraints among items, which force successor items to be packed into later bins than their predecessors. In this paper we propose a dynamic programming based heuristic, and a modified exact enumeration procedure to solve the problem. These methods make use of several new lower bounds and dominance rules tailored for the problem in hand. The results of a computational experiment show the effectiveness of the proposed methods, which are able to close all of the previous open instances from the benchmark instance set within very reduced running times. (C) 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved. |
|
| |
Address |
[Pereira, Jordi] Univ Adolfo Ibanez, Fac Sci & Engn, Ave Padre Hurtado 750,Off C216, Vina Del Mar, Chile, Email: jorge.pereira@uai.cl |
|
| |
Corporate Author |
|
Thesis |
|
|
| |
Publisher |
Elsevier Science Bv |
Place of Publication |
|
Editor |
|
|
| |
Language |
English |
Summary Language |
|
Original Title |
|
|
| |
Series Editor |
|
Series Title |
|
Abbreviated Series Title |
|
|
| |
Series Volume |
|
Series Issue |
|
Edition |
|
|
| |
ISSN |
0377-2217 |
ISBN |
|
Medium |
|
|
| |
Area |
|
Expedition |
|
Conference |
|
|
| |
Notes |
WOS:000369192500011 |
Approved |
|
|
| |
Call Number |
UAI @ eduardo.moreno @ |
Serial |
581 |
|
| Permanent link to this record |
