Modello di Ottimizzazione per la Schedulazione del Personale … · organizzazione dei cicli...

Descrizione del problema Modellizzazione Implementazione e risultati

Modello di Ottimizzazione per la Schedulazione delPersonale Infermieristico di una Residenza Assistita

Candidata: Serena CortopassiRelatori: Prof. Frangioni, Prof. Scutella

Universita di Pisa

Tesi di Laurea Triennale11 aprile 2014

Serena Cortopassi (Universita di Pisa) 11 aprile 2014 1 / 28

Modelli di ottimizzazione matematica

Allocare le risorse disponibili in un certo arco di tempo al fine disvolgere una serie di compiti assegnati.

Ottimizzare il risultato, in termini di

minimizzazione di tempi e costimassimizzazione dei profitti

Problemi di scheduling

Modelli decisionali e algoritmi per la pianificazione di molte attivita:

organizzazione dei cicli produttivi industriali;

generazione di turni lavorativi e orari scolastici;

gestione del traffico e degli orari dei servizi di trasporto.

Problema reale: staff scheduling

Problema

Ottimizzazione della programmazione degli orari di lavoro del personaledella struttura “Il Gignoro” della Diaconia Valdese Fiorentina.

Obiettivo

Assegnare un turno a ogni dipendente per ogni giorno dell’orizzonte dipianificazione considerato.

Problema reale: staff scheduling

Problema

Ottimizzazione della programmazione degli orari di lavoro del personaledella struttura “Il Gignoro” della Diaconia Valdese Fiorentina.

Obiettivo

Assegnare un turno a ogni dipendente per ogni giorno dell’orizzonte dipianificazione considerato.

Quattro fasi:

1 Raccolta delle specifiche del problema e delle richieste dell’utente

2 Raccolta dei dati in input

3 Formulazione del modello matematico

4 Implementazione dell’algoritmo e test su dati reali

Quattro fasi:

Specifiche del problema

Orizzonte di programmazione: mensile.

La struttura e organizzata per moduli.

A ciascun modulo sono associati operatori e domande di copertura.

Tipi di orario: definiti da una fascia oraria, un modulo e una qualifica.

Turni: combinazioni ammissibili di tipi di orario.

Ciascun tipo di orario richiede giornalmente un certo numero dioperatori.

Ciascuna coppia operatore-turno ha un costo di ammissibilita.

Rassegna bibliografica

Purnomo H.W., Bard J.F., Cyclic preference scheduling for nursesusing branch and price, 2007

Caprara A., Monaci M., Toth P., Models and algorithms for a staffscheduling problem, 2003

Brucker P., Qu R., Burke E., Personnel Scheduling: Models andComplexity, 2011

Descrizione dei dati

Dati in input

orizzonte di pianificazione: insieme D dei giorni del mese,D = {1, ..., d};operatori: insieme P = {1, ..., p};tipi di orario: insieme Z = {1, ..., z};turni: insieme T = {0, ..., t};ore previste per il turno s: hs ∈ R, ∀s ∈ T ;

turni ammissibili ogni operatore: insieme T (x) ⊆ T , ∀x ∈ P.Il turno s e ammissibile per l’operatore x ⇔ gx ,s ≥ 0;

domande di copertura: rk,u ∈ N numero di operatori richiesti per ilgiorno k ∈ D per il tipo di orario u ∈ Z ;

Dati in input

assegnamenti programmati: B = {(x , s, k) : x ∈ P, s ∈ T (x), k ∈ D};matrice di incidenza turni-orari: matrice A tale che

as,u =

{1 se il turno s copre il tipo di orario u

0 altrimenti,

con s ∈ T e u ∈ Z ;

scostamento dal budget orario: vx =

y−1∑f =1

vx ,f , ∀x ∈ P, con y mese

considerato in programmazione e vx ,f ∈ R scostamento registrato nelmese f ∈ {1, ..., y − 1};coefficienti di penalita: η1 > ... > η11 ∈ R.

Dati in input

as,u =

0 altrimenti,

y−1∑f =1

Dati in input

as,u =

0 altrimenti,

y−1∑f =1

Dati in input

as,u =

0 altrimenti,

y−1∑f =1

Variabili decisionali

αx ,s,k , ∀x ∈ P, s ∈ T (x), k ∈ D:

αx ,s,k =

{1 se l’operatore x e assegnato al turno s nel giorno k

0 altrimenti

Vincoli

Vincoli hard

assegnare esattamente un turno ad ogni operatore per ogni giornodell’orizzonte di programmazione:∑

s∈T (x)

αx ,s,k = 1 ∀x ∈ P, k ∈ D

rispettare i preassegnamenti:

αx ,s,k = 1 ∀(x , s, k) ∈ B

Vincoli

Vincoli hard

assegnare esattamente un turno ad ogni operatore per ogni giornodell’orizzonte di programmazione:∑

s∈T (x)

αx ,s,k = 1 ∀x ∈ P, k ∈ D

rispettare i preassegnamenti:

αx ,s,k = 1 ∀(x , s, k) ∈ B

Vincoli

Vincoli soft

distribuire uniformemente i riposi agli operatori:

due in ciascuna meta del mese:∑k∈Dh

αx,1,k + γx,h ≥ 2 ∀x ∈ P, h ∈ {1, 2}

γx,h ≥ 0 ∀x ∈ P, h ∈ {1, 2}

uno in ciascuna delle quattro settimane del mese:∑k∈Sj

αx,1,k + δx,j ≥ 1 ∀x ∈ P, j ∈ {1, ..., 4}

δx,j ≥ 0 ∀x ∈ P, j ∈ {1, ..., 4}

Vincoli

Vincoli soft

αx,1,k + γx,h ≥ 2 ∀x ∈ P, h ∈ {1, 2}

γx,h ≥ 0 ∀x ∈ P, h ∈ {1, 2}

αx,1,k + δx,j ≥ 1 ∀x ∈ P, j ∈ {1, ..., 4}

δx,j ≥ 0 ∀x ∈ P, j ∈ {1, ..., 4}

Vincoli

Vincoli soft

αx,1,k + γx,h ≥ 2 ∀x ∈ P, h ∈ {1, 2}

γx,h ≥ 0 ∀x ∈ P, h ∈ {1, 2}

αx,1,k + δx,j ≥ 1 ∀x ∈ P, j ∈ {1, ..., 4}

δx,j ≥ 0 ∀x ∈ P, j ∈ {1, ..., 4}

Vincoli

Vincoli soft

soddisfare le richieste di copertura dei moduli:∑x∈P

∑s∈T (x):as,u=1,

as,u∈A

αx ,s,k + θ+k,u − θ

−k,u = rk,u ∀k ∈ D, u ∈ Z

θ+k,u ≥ 0, θ−k,u ≥ 0 ∀k ∈ D, u ∈ Z

Vincoli

Vincoli soft

prevedere 37 ore di lavoro settimanali per ogni operatore:∑s∈T (x)

∑k∈Sj

hs · αx ,s,k + ε+x ,j − ε

−x ,j = 37 ∀x ∈ P, j ∈ {1, ..., 4}

ε+x ,j ≥ 0, ε−x ,j ≥ 0 ∀x ∈ P, j ∈ {1, ..., 4}

prevedere 376 × n ore di lavoro mensili per ogni operatore, con n

numero di giorni lavorativi del mese considerato in programmazione:∑s∈T (x)

∑k∈D

hs · αx ,s,k + λ+x − λ−x =

6× n ∀x ∈ P

λ+x ≥ 0, λ−x ≥ 0 ∀x ∈ P

Vincoli

Vincoli soft

prevedere 37 ore di lavoro settimanali per ogni operatore:∑s∈T (x)

∑k∈Sj

hs · αx ,s,k + ε+x ,j − ε

−x ,j = 37 ∀x ∈ P, j ∈ {1, ..., 4}

ε+x ,j ≥ 0, ε−x ,j ≥ 0 ∀x ∈ P, j ∈ {1, ..., 4}

prevedere 376 × n ore di lavoro mensili per ogni operatore, con n

numero di giorni lavorativi del mese considerato in programmazione:∑s∈T (x)

∑k∈D

hs · αx ,s,k + λ+x − λ−x =

6× n ∀x ∈ P

λ+x ≥ 0, λ−x ≥ 0 ∀x ∈ P

Vincoli

Vincoli soft

tenere conto dello scostamento (in eccesso e in difetto) accumulatomese dopo mese da ciascun operatore rispetto al budget orarioprevisto. Viene considerato anche il mese in programmazione, inprevisione dello scostamento che si registrera alla fine dell’anno.

β+x − β−x = vx + λ+

x − λ−x ∀x ∈ P

β+x ≥ 0, β−x ≥ 0 ∀x ∈ P

Funzione obiettivo

Termini della funzione obiettivo

richieste di copertura non soddisfatte:

f1 =∑k∈D

∑u∈Z

θ+k,u

scostamento in eccesso e in difetto accumulato fino al meseconsiderato in programmazione:

f2 =∑x∈P

f3 =∑x∈P

β−x

Funzione obiettivo

richieste di copertura non soddisfatte:

f1 =∑k∈D

∑u∈Z

θ+k,u

scostamento in eccesso e in difetto accumulato fino al meseconsiderato in programmazione:

f2 =∑x∈P

f3 =∑x∈P

β−x

Funzione obiettivo

scostamento in eccesso e in difetto registrato nel mese considerato inprogrammazione:

f4 =∑x∈P

f5 =∑x∈P

λ−x

scostamento in eccesso e in difetto registrato ogni settimana del meseconsiderato:

f6 =∑x∈P

∑j∈{1,...,4}

ε+x ,j

f7 =∑x∈P

∑j∈{1,...,4}

ε−x ,j

Funzione obiettivo

scostamento in eccesso e in difetto registrato nel mese considerato inprogrammazione:

f4 =∑x∈P

f5 =∑x∈P

λ−x

scostamento in eccesso e in difetto registrato ogni settimana del meseconsiderato:

f6 =∑x∈P

∑j∈{1,...,4}

ε+x ,j

f7 =∑x∈P

∑j∈{1,...,4}

ε−x ,j

Funzione obiettivo

riposi non assegnati in ciascuna meta del mese:

f8 =∑x∈P

∑h∈{1,2}

γx ,h

riposi non assegnati settimanalmente:

f9 =∑x∈P

∑j∈{1,...,4}

δx ,j

indice di sgradimento dei turni assegnati:

f10 =∑x∈P

∑s∈T (x)

gx ,s∑k∈D

αx ,s,k

Funzione obiettivo

f8 =∑x∈P

∑h∈{1,2}

γx ,h

f9 =∑x∈P

∑j∈{1,...,4}

δx ,j

f10 =∑x∈P

∑s∈T (x)

gx ,s∑k∈D

αx ,s,k

Funzione obiettivo

f8 =∑x∈P

∑h∈{1,2}

γx ,h

f9 =∑x∈P

∑j∈{1,...,4}

δx ,j

f10 =∑x∈P

∑s∈T (x)

gx ,s∑k∈D

αx ,s,k

Funzione obiettivo

operatori in sovrannumero rispetto alle richieste di copertura fatte:

f11 =∑k∈D

∑u∈Z

θ−k,u

La funzione obiettivo del modello, da minimizzare, e la somma dei terminilineari descritti:

min11∑i=1

ηi · fi

Funzione obiettivo

operatori in sovrannumero rispetto alle richieste di copertura fatte:

f11 =∑k∈D

∑u∈Z

θ−k,u

La funzione obiettivo del modello, da minimizzare, e la somma dei terminilineari descritti:

min11∑i=1

ηi · fi

Strumenti implementativi

Implementazione dell’algoritmo: linguaggio C++

Strumenti utilizzati:

librerie sviluppate da COIN-OR

interfaccia OSI

solutori per PLI: Cbc, GLPK e CPLEX

linguaggio di modellazione algebrico FlopC++

Risultati ottenuti

Versione semplificata dell’istanza

Il solutore commerciale CPLEX e stato testato su quattro diversi insiemi dicoefficienti di penalita e tre diversi tempi limite (5, 30 e 60 minuti). Tutti itest garantiscono una soluzione ammissibile intera.

Il solutore open-source Cbc testato sul primo set di coefficienti impiega 3ore per trovare la prima soluzione ammissibile intera.

Il solutore open-source GLPK testato sul primo set di coefficienti dopo 3ore ancora non fornisce una soluzione ammissibile intera.

Risultati ottenuti

Qualita dei risultati - Versione semplificata

Non si registrano violazioni per:

la copertura delle richiestela distribuzione uniforme dei riposi (bisettimanale e settimanale)

Risultati ottenuti

Versione completa dell’istanza

Il solutore commerciale CPLEX e stato testato sui quattro diversi insiemidi coefficienti di penalita e tre diversi tempi limite (5, 30 e 60 minuti).Tutti i test garantiscono una soluzione ammissibile intera.Il primo e il quarto set di coefficienti risolvono il problema all’ottimo.

I solutori open-source Cbc e GLPK testati sul primo e sul quarto set dicoefficienti dopo 3 ore ancora non forniscono una soluzione ammissibileintera.

Risultati ottenuti

Versione completa dell’istanza

Il solutore commerciale CPLEX e stato testato sui quattro diversi insiemidi coefficienti di penalita e tre diversi tempi limite (5, 30 e 60 minuti).Tutti i test garantiscono una soluzione ammissibile intera.Il primo e il quarto set di coefficienti risolvono il problema all’ottimo.

I solutori open-source Cbc e GLPK testati sul primo e sul quarto set dicoefficienti dopo 3 ore ancora non forniscono una soluzione ammissibileintera.

Qualita dei risultati - Versione completa

lo scostamento mensile in eccesso

la distribuzione uniforme dei riposi (bisettimanale e settimanale)

lo scostamento mensile in eccesso

Grazie per l’attenzione.

Modello di Ottimizzazione per la Schedulazione del Personale … · organizzazione dei cicli...

Documents

Transcript of Modello di Ottimizzazione per la Schedulazione del Personale … · organizzazione dei cicli...