Problema del lot sizing senza capacità (ULS)

Catalogo dei problemi di ottimizzazione combinatoria · Problemi di lot sizing · Catalogo (PDF)

Definizione 1: Problema del lot sizing senza capacità

Dati:

1. un insieme \(T=\{1,2,\dots,m\}\) di \(m \in \Z_{\ge 1}\) periodi,

2. per ogni periodo \(t \in T\), una domanda \(d_t \in \Z_{\ge 1}\),

3. per ogni periodo \(t \in T\), un costo di setup \(sc_t \in \Z_{\ge 0}\), un costo variabile di produzione \(vc_t \in \Z_{\ge 0}\) per unità, e un costo di mantenimento a scorta \(hc_t \in \Z_{\ge 0}\) per unità in scorta alla fine del periodo \(t\),

il problema del lot sizing senza capacità (ULS) chiede di decidere quante unità produrre in ogni periodo, in modo che, partendo con la scorta vuota e terminando con la scorta vuota, la domanda di ogni periodo sia soddisfatta, e il costo totale di setup, produzione e mantenimento a scorta sia minimo.

Ipotesi

• Facciamo le seguenti ipotesi:

  1. C'è un solo prodotto, e la scorta è vuota all'inizio e alla fine dell'orizzonte: l'ULS è il CLS di un solo prodotto senza capacità e senza scorta iniziale.

  2. Le quantità sono intere. Con dati interi, una volta fissati i periodi con un setup, 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	Questa pagina
Formulazioni	Cap. 15 «Formulazioni dei problemi di lot sizing»
Programmazione dinamica	Cap. 16 «Principi della programmazione dinamica»; Cap. 25 «PD per il problema del lot sizing senza capacità»
Euristiche MIP	Cap. 33 «Euristiche MIP per i problemi classici»
Esercizi	Esercizio 8.4; Esercizio 15.6; Cap. 25 (3 esercizi)