Lot sizing capacitato (CLS)¶
Definizione 1: Lot sizing capacitato
Dati:
-
un insieme \(T = \{1,2,\dots,m\}\) di \(m\) periodi di tempo,
-
per ogni periodo \(t \in T\), una domanda \(d_t \in \Z_{\ge 1}\) e una capacità \(cap_t \in \Z_{\ge 1}\), entrambe misurate in unità di un prodotto,
-
per ogni periodo \(t \in T\), tre costi interi non negativi: il costo di setup \(sc_t\), il costo variabile di produzione \(vc_t\) per unità prodotta e il costo di mantenimento a scorta \(hc_t\) per unità tenuta in scorta alla fine del periodo,
il problema del lot sizing capacitato (CLS) chiede di decidere quanto produrre in ogni periodo, in modo che ogni domanda sia soddisfatta con ciò che si produce e ciò che è in scorta, le capacità siano rispettate, e il costo totale di setup, produzione e mantenimento a scorta sia minimo.
Ipotesi
-
Facciamo le seguenti ipotesi:
-
La scorta è vuota all'inizio e alla fine dell'orizzonte. Lasciare scorta alla fine aggiunge solo costo, quindi nessun piano ottimo ne ha bisogno; una scorta iniziale è una variante del problema (Sezione.
-
Le capacità permettono di soddisfare le domande, periodo dopo periodo (altrimenti non esiste alcun piano ammissibile). Formalmente:
\[ \sum_{u=1}^{t} cap_u \ge \sum_{u=1}^{t} d_u, ~~~~ \forall t \in T \] -
Le quantità sono intere. Con dati interi, una volta fissati i periodi con un setup, ciò che resta è un problema di flusso di costo minimo, che ha una soluzione ottima intera: restringere le quantità agli interi non cambia il costo ottimo.
-
Che cosa fa il corso su questo problema¶
| Tecnica | Dove |
|---|---|
| Definizione | Cap. 8 «Problemi di lot sizing» |
| Formulazioni | Cap. 15 «Formulazioni dei problemi di lot sizing» |
| Programmazione dinamica | Cap. 16 «Principi della programmazione dinamica»; Cap. 26 «PD per il problema del lot sizing capacitato» |
| Euristiche MIP | Cap. 33 «Euristiche MIP per i problemi classici» |
| Esercizi | Cap. 8 (5 esercizi); Cap. 15 (5 esercizi); Cap. 26 (2 esercizi) |
Proprietà¶
-
NP-difficile con capacità generali; senza capacità (ULS) è polinomiale (Cap. 1).
-
Lower bound: la somma dei \(k\) costi di setup più piccoli, con \(k\) il minimo numero di periodi le cui capacità coprono la domanda totale (Cap. 8).
-
Lot-for-lot e accorpamenti a mano: \(250\to210\to180\) sull'istanza del Cap. 8, dove \(180\) è ottimo (Cap. 8).
Formulazioni¶
-
Formulazione big-M: il valore forte \(M_t=\min\{cap_t,D_{t,m}\}\) alza il bound del rilassamento lineare sull'istanza del Cap. 8 da \(99.65\) a \(157.5\) (Cap. 15).
-
La formulazione a cammino minimo dà il bound \(170\), il più forte del capitolo (Cap. 15).
Programmazione dinamica¶
-
Senza capacità un piano ottimo produce solo con scorta vuota (Wagner e Whitin): una PD sull'ultimo lotto di produzione risolve l'ULS in \(\Theta(m^2)\) passi (Cap. 25).
-
Con capacità lo stato è (periodo, scorta): \(O(m\,D\,C)\) passi, un tempo pseudo-polinomiale (Cap. 26).