In the one-dimensional packing problem with variable pattern processing time, we extend the classical packing definition by introducing a scheduling perspective: each item is provided with a due date, and a pattern-dependent time to process each bin is taken into account. In order to concurrently reduce the material waste and the delay costs, both not negligible in several real contexts, we require the minimization of a convex combination of the number of used bins and maximum lateness. In this paper we present a new extended pattern-based reformulation for this problem and a dynamic programming algorithm to solve the corresponding quadratic pricing problem. Preliminary computational results are given to analyze the quality of the continuous relaxation.

A pattern-based reformulation for the one-dimensional bin packing with variabile pattern processing time / Pizzuti, Andrea; Wei, W.; Marinelli, Fabrizio; Yagiura, M.; Hu, Y.. - STAMPA. - (2018), pp. 89-94. (Intervento presentato al convegno Scheduling Symposium 2018 tenutosi a Otaru, Japan nel September 20, 2018).

A pattern-based reformulation for the one-dimensional bin packing with variabile pattern processing time

Pizzuti Andrea
;
Fabrizio Marinelli;
2018-01-01

Abstract

In the one-dimensional packing problem with variable pattern processing time, we extend the classical packing definition by introducing a scheduling perspective: each item is provided with a due date, and a pattern-dependent time to process each bin is taken into account. In order to concurrently reduce the material waste and the delay costs, both not negligible in several real contexts, we require the minimization of a convex combination of the number of used bins and maximum lateness. In this paper we present a new extended pattern-based reformulation for this problem and a dynamic programming algorithm to solve the corresponding quadratic pricing problem. Preliminary computational results are given to analyze the quality of the continuous relaxation.
2018
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/265756
 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