Maximum lateness minimization in one-dimensional bin packing

Claudio Arbib and Fabrizio Marinelli

Omega, 2017, vol. 68, issue C, 76-84

Abstract: In the One-dimensional Bin Packing problem (1-BP) items of different lengths must be assigned to a minimum number of bins of unit length. Regarding each item as a job that requires unit time and some resource amount, and each bin as the total (discrete) resource available per time unit, the 1-BP objective is the minimization of the makespan Cmax=maxj{Cj}. We here generalize the problem to the case in which each item j is due by some date dj: our objective is to minimize a convex combination of Cmax and Lmax=maxj{Cj−dj}. For this problem we propose a time-indexed Mixed Integer Linear Programming formulation. The formulation can be decomposed and solved by column generation relegating single-bin packing to a pricing problem to be solved dynamically. We use bounds to (individual terms of) the objective function to address the oddity of activation constraints. In this way, we get very good gaps for instances that are considered difficult for the 1-BP.

Keywords: One-dimensional bin packing; Scheduling; Mixed Integer programming; Integer reformulation (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S030504831630305X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jomega:v:68:y:2017:i:c:p:76-84

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.omega.2016.06.003

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().