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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.