In the Bin Packing problem (BP), items of different sizes must be assigned to a minimum number of bins. In the k-dimensional problem (kBP), items and bins are closed k-intervals. 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 kBP objective is the minimization of the makespan. We generalize the kBP problem to Bin Packing and Scheduling (kBPS) by changing the objective to any (even non-regular) function of the completion time of the jobs. Interesting applications are those in which each part (= job) is to be produced within a specific due date. Typical examples of regular functions are maximum lateness, weighted sum of jobs tardiness, etc. In practice, a convex combination of such functions is often considered. When the scheduling term in the objective function is the weighted sum of jobs tardiness or of tardy jobs, one can specialize an exact formulation for the Cutting Stock Problem with Due Dates (Arbib and Marinelli, 2014). An alternative, more general and perhaps more effective approach is to use an ad-hoc time-indexed formulation. This approach, which can encompass Dantzig-Wolfe decomposition and, consequently, column generation, is close to that described by van den Akker et al. (2005) for general time-indexed formulations applied to parallel scheduling. When column generation is used, the difficulty of k-dimensional packing is relegated to the pricing problem. To find a lower bound for the 2BPS one can then solve a relaxed 2-dimensional pricing problem by the arc-flow formulation (Macedo, Alves and V. de Carvalho, 2010). In alternative, one can implement conservative scales (Belov et al., 2013) via a time-indexed formulation for 1BPS. In this talk we just discuss a preliminary computational experience carried out for 1BPS with Lmax as scheduling term of the objective function.

Bin Packing with due dates / Arbib, Claudio; Marinelli, Fabrizio. - ELETTRONICO. - (2015), pp. 19-19. (Intervento presentato al convegno 12th ESICUP Meeting tenutosi a Portsmouth, UK nel March 29-31, 2015).

Bin Packing with due dates

MARINELLI, Fabrizio
2015-01-01

Abstract

In the Bin Packing problem (BP), items of different sizes must be assigned to a minimum number of bins. In the k-dimensional problem (kBP), items and bins are closed k-intervals. 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 kBP objective is the minimization of the makespan. We generalize the kBP problem to Bin Packing and Scheduling (kBPS) by changing the objective to any (even non-regular) function of the completion time of the jobs. Interesting applications are those in which each part (= job) is to be produced within a specific due date. Typical examples of regular functions are maximum lateness, weighted sum of jobs tardiness, etc. In practice, a convex combination of such functions is often considered. When the scheduling term in the objective function is the weighted sum of jobs tardiness or of tardy jobs, one can specialize an exact formulation for the Cutting Stock Problem with Due Dates (Arbib and Marinelli, 2014). An alternative, more general and perhaps more effective approach is to use an ad-hoc time-indexed formulation. This approach, which can encompass Dantzig-Wolfe decomposition and, consequently, column generation, is close to that described by van den Akker et al. (2005) for general time-indexed formulations applied to parallel scheduling. When column generation is used, the difficulty of k-dimensional packing is relegated to the pricing problem. To find a lower bound for the 2BPS one can then solve a relaxed 2-dimensional pricing problem by the arc-flow formulation (Macedo, Alves and V. de Carvalho, 2010). In alternative, one can implement conservative scales (Belov et al., 2013) via a time-indexed formulation for 1BPS. In this talk we just discuss a preliminary computational experience carried out for 1BPS with Lmax as scheduling term of the objective function.
2015
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11566/229507
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact