Maximum lateness minimization in one-dimensional bin packing. (April 2017)

• Record Type: Journal Article
• Authors: Arbib, Claudio; Marinelli, Fabrizio
• Is Part Of: Omega. Volume 68(2017:Apr.)
• Page Start: 76
• Page End: 84
• Publication Date: 2017-04
• Subjects: One-dimensional bin packing -- Scheduling -- Mixed Integer programming -- Integer reformulation; Management -- Periodicals; 658.4005
• DOI: 10.1016/j.omega.2016.06.003
• Languages: English
• ISSNs: 0305-0483

Abstract

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 C max = max j { C j } . We here generalize the problem to the case in which each item j is due by some date d j : our objective is to minimize a convex combination of C max and L max = max j { C j − d j } . 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. Abstract : Highlights: We analyze a generalization of the one-dimensional bin packing problem where a convex combination of scheduling terms, i.e., completion time and lateness, have to be minimized. We propose a time-indexed Mixed Integer Linear Programming formulation and solve it by column generation. We use bounds to (individual terms of) the objective function to address the oddity of activation constraints and get stronger dual bounds. We propose a Sequential Value Correction heuristic that provides good primal solutions.