Problema del cutting stock (CSP)

Catalogo dei problemi di ottimizzazione combinatoria · Problemi di packing · Catalogo (PDF)

Definizione 1: Problema del cutting stock

Dati:

1. un numero infinito di contenitori, ciascuno di capacità \(c \in \Z_{\ge 1}\),

2. un insieme \(\mathscr{I} = \{1,2,\dots,n\}\) di \(n\) oggetti,

3. per ogni oggetto \(j \in \mathscr{I}\), un peso \(w_j \in \Z_{\ge 1}\) e un numero di copie richieste \(d_j \in \Z_{\ge 1}\),

il problema del cutting stock (CSP) chiede di decidere in quale contenitore sistemare ogni copia di ogni oggetto, in modo che il peso totale delle copie in ogni contenitore non superi la capacità del contenitore, che il numero richiesto di copie di ogni oggetto sia sistemato nei contenitori e che il numero totale di contenitori usati sia minimo.

Ipotesi

• Facciamo le seguenti ipotesi:

  1. Il peso totale di tutte le copie richieste supera la capacità di un contenitore (altrimenti tutte le copie entrerebbero in un solo contenitore). Formalmente:

     \[ \sum_{j\in \mathscr{I}} d_j\, w_j \;>\; c. \]

  2. Ogni oggetto, da solo, entra in un contenitore (altrimenti nessuna copia di quell'oggetto può essere impaccata). Formalmente:

     \[ w_j \le c, \qquad \forall\, j\in \mathscr{I}. \]

Che cosa fa il corso su questo problema

Tecnica	Dove
Definizione	Cap. 3 «Problemi di packing»
Formulazioni	Cap. 10 «Formulazioni dei problemi di packing»
Esercizi	Esercizio 3.4; Esercizio 10.6