8.6 Varianti¶

Parte 1 · Problemi di ottimizzazione combinatoria · Capitolo 8 · Capitolo 8: Problemi di lot sizing · Dispensa, volume 1 (PDF) · Slide · Esercizi: Problemi di lot sizing

Ogni variante mantiene i dati del CLS (periodi, domande, costi) e cambia una caratteristica del problema. Le definizioni qui sotto riportano solo ciò che cambia.

8.6.1 Il problema del lot sizing senza capacità¶

Definizione 8.3: problema del lot sizing senza capacità

Il problema del lot sizing senza capacità (ULS) è il CLS in cui le capacità non sono vincolanti, per esempio \(cap_t \ge \sum_{u \in T} d_u\) per ogni \(t \in T\).

Il ULS si risolve in tempo polinomiale con la programmazione dinamica.

8.6.2 Più prodotti e tempi di setup¶

Definizione 8.4: lot sizing con più prodotti e tempi di setup

Nel problema del lot sizing con più prodotti e tempi di setup (MLS) un insieme \(P\) di prodotti condivide la risorsa di ogni periodo: \(d_{pt}\) è la domanda del prodotto \(p \in P\) nel periodo \(t\), e \(cap_t\) è il tempo disponibile nel periodo \(t\). Produrre un'unità di \(p\) richiede \(vt_{pt}\) unità di tempo, e un setup di \(p\) costa \(sc_{pt}\) e richiede \(st_{pt}\) unità di tempo.

8.6.3 Scorta iniziale¶

Definizione 8.5: lot sizing con scorta iniziale

Nel problema del lot sizing con scorta iniziale (LS-SI) la quantità \(si_p\) del prodotto \(p\) disponibile all'inizio dell'orizzonte è una decisione, acquistata al costo \(fc_p\) per unità.

8.6.4 Straordinario¶

Definizione 8.6: lot sizing con straordinario

Nel problema del lot sizing con straordinario (LS-OT) la capacità non è fissa: il tempo di lavoro in orario normale costa \(cw_t\) per unità fino a \(cap^{N}_t\), e lo straordinario costa \(co_t\) per unità fino a \(cap^{O}_t\).

8.6.5 Domanda non soddisfatta¶

Definizione 8.7: lot sizing con domanda non soddisfatta

Nel problema del lot sizing con domanda non soddisfatta (LS-UD) una parte della domanda può restare non soddisfatta, con una penalità \(cu_{pt}\) per unità.

8.7 Osservazioni¶

Nel 1958 Wagner e Whitin proposero un algoritmo di programmazione dinamica per il caso senza capacità e con domanda variabile nel tempo. L'algoritmo si basa su una proprietà dei piani ottimi: si produce solo quando la scorta è vuota.
Con le capacità la proprietà non vale più, e il problema è NP-difficile (Capitolo 1 «Problemi di ottimizzazione combinatoria»).

8.8 Errori tipici¶

Attenzione

Produrre in ritardo. La produzione di un periodo non può servire la domanda di un periodo precedente: la scorta \(s_t(\vet{x})\) deve essere non negativa in ogni periodo.
Addebitare un setup quando non si produce nulla. Un costo di setup si paga solo nei periodi con \(x_t > 0\).
Dimenticare la scorta degli ultimi periodi. Il costo di mantenimento si paga sulla scorta alla fine di ogni periodo, compresi i periodi in cui il piano non produce nulla.
Credere che si produca solo con scorta vuota. La proprietà di Wagner e Whitin vale senza capacità; con le capacità il piano ottimo dell'Esempio 8.1 la viola.
Contare \(2^m\) piani ammissibili. I \(2^m\) sottoinsiemi di periodi sono le scelte di setup: alcune sono inammissibili, e a ciascuna ammissibile corrispondono uno o più piani.

8.9 In sintesi¶

In sintesi

Il problema del lot sizing capacitato chiede le quantità da produrre in ogni periodo, con capacità, setup e scorte, al minimo costo totale; una soluzione è un piano di produzione.
La parte combinatoria è la scelta dei periodi con un setup: ci sono \(2^m\) scelte, solo alcune ammissibili, e a ciascuna corrispondono uno o più piani.
Il lot-for-lot dà rapidamente un piano, accorpare le domande lo migliora; il numero di setup richiesto dalla domanda totale dà un lower bound.
Con le capacità, i piani ottimi possono produrre mentre la scorta è positiva; senza capacità non lo fanno mai.
Le varianti aggiungono prodotti, tempi di setup, scorta iniziale, straordinario o domanda non soddisfatta; i loro modelli sono nel Capitolo 15 «Formulazioni dei problemi di lot sizing».

Quadro riassuntivo dell'istanza del CLS (minimizzazione: il lower bound è un bound duale, l'upper bound è il costo di un piano):

Capitolo	Lower bound	Upper bound	Da
Questo capitolo	\(150\)	\(250\)	almeno tre setup; lot-for-lot
Questo capitolo, accorpando	\(150\)	\(180\)	il piano \((3,0,4,4,0)\)
Questo capitolo, enumerazione	\(180\)	\(180\)	i \(94\) piani ammissibili

Esercizi su questo capitolo: Problemi di lot sizing

Approfondimento: che cosa fa il corso su questo problema