Gestione dei servizi Elaborazione su calcolatore del calendario dei turni di lavoro con tecniche di...

Gestione dei servizi

Elaborazione su calcolatore del calendario dei turni di lavoro con

tecniche di programmazione lineare.

Corso diRicerca OperativaMetodi e Modelli per la Logistica

• Presentazione del GVSP• Descrizione del problema• Formulazione matematica• Introduzione a GAMS• Implementazione su GAMS• Descrizione del modello• Conclusioni

Indice

Il GVSP è

un’organizzazione

di volontariato che

si occupa di

sicurezza e

soccorso sulle piste

da sci della

Regione.

Presentazione del Gruppo

Gli associati

provengono da

realtà e professioni

differenti, il che li

rende eterogenei

per disponibilità ed

esperienza

operativa.

Presentazione del Gruppo

Obiettivo: organizzare il piano dei servizi formando squadre di tre pattugliatori omogenee per capacità operativa che coprano tutte le giornate richieste distribuendo il carico di lavoro in modo opportuno.

Descrizione del problema


La composizione delle squadre è soggetta a vincoli legati a

- disponibilità dei singoli; - rapporti personali; - capacità individuali; - capacità complessive della squadra.


Vincoli sulla disponibilità

Il tempo che i soci possono dedicare al volontariato è legato principalmente alla professione svolta; ad esempio i commercianti non sono disponibili il Sabato e le Domeniche precedenti le festività Natalizie.


Vincoli interpersonali

Il carattere di alcuni membri del gruppo potrebbe creare situazioni conflittuali che pregiudicano la collaborazione all’interno della squadra,degradandone le prestazioni complessive.


Vincoli sulle capacità

L’attitudine personale e l’esperienza accumulatasono due fattori fondamentali nella formazione delle squadre che devono essere in grado di intervenire in ogni situazione ed imprevisto.

Formulazione matematica

La formulazione matematica consiste nel definire i seguenti insiemi di oggetti:

• gli insiemi dei dati

• le variabili decisionali

• i parametri del problema

• la funzione obiettivo

• i vincoli


Gli insiemi

P pattugliatori;R sottoinsieme di P: i soci con maggiore

esperienza ed in grado di coordinare un team;T turni: insieme delle giornate da coprire (sabati,

domeniche ed altre festività riconosciute);SAB i turni di Sabato;DOM i turni di Domenica;DEC i turni nel mese di dicembre;NOFEST turni per cui è previsto un afflusso

normale.


Le variabili decisionali

Per gli scopi di questo problema viene introdotta una variabile booleana x(p,t), dipendente sia dalle persone che dai turni, definita come segue:

(1)

altrimenti

t turnonel è p orepattugliat il se

0

1),( tpx


I parametri

skill(p) esprime l’abilità e l’esperienza delpattugliatore p;

d(p) permette di personalizzare il numero diservizi assegnabili al pattugliatore pmodificando il numero medio n;


La funzione obiettivo

Detto n il numero di servizi pro capite la f.o. sarà

(2) nz min


I vincoli

Sulla composizione e qualità della squadra:

(3)

(4)

(5)

Pp

tpxTt 3),(

Rp

tpxTt 1 ),(

Pp

StpxpskillTt ),()(


I vincoli

Sul numero di servizi pro capite:

(6)

e sui servizi consecutivi

(7)

Pp

pdntpxPp )(),(

1)1,(),( tpxtpxNOFESTSABt

0),( SABPp

tpxSABt

0),( DECPp

tpxDECt


I vincoli

Sulla disponibilità:

(8)

(9)


I vincoli

Sui rapporti di natura personale:

(10)

dove P* è un sottoinsieme di pattugliatori che per qualche motivo non è opportuno mettere nella stessa squadra.

*

1),( Pp

tpxTt


Il modello così costruito ha le seguenti dimensioni:

variabili decisionali: N=pt = 1647 = 752;

vincoli:

47 per ciascuna delle relazioni (3), (4), (5);16 per la relazione (6);21 per la (7) e la (8);11 per la (9);

47K per la (10) dove K=2 è il numero di sottoinsiemi ;

per un totale di 304 relazioni.

*kP

Introduzione a GAMS

GAMS è l’acronimo per “General Algebraic Modeling System” ed è un ambiente per la rappresentazione di problemi di programmazione lineare e non-lineare. Al suo interno è presente un compilatore ed un insieme di risolutori specifici per i diversi compiti. La potenza di GAMS sta nel linguaggio di programmazione che consente di costruire modelli complessi in modo relativamente semplice e di eseguirne agevolmente la manutenzione e l’aggiornamento a nuove situazioni.

Introduzione a GAMS

I risolutori disponibili sono:

• CONOPT e MINOS• OSL• CPLEX • XA

Introduzione a GAMS

GAMS/CONOPT

I modelli non lineari creati con GAMS devono essere risolti con MINOS e CONOPT. Entrambi cercano un ottimo locale sfruttando algoritmi diversi. Come conseguenza i due risolutori hanno prestazioni differenti e, a seconda della situazione, l’uno risulta preferibile all’altro. In generale CONOPT è preferibile in presenza di numerosi vincoli non lineari; inoltre in caso di modelli mal strutturati li rigetta fornendo suggerimenti costruttivi.

Introduzione a GAMS

GAMS/OSL

OSL (Optimization Subroutine Library) è una libreria IBM contente risolutori ad alte prestazioni per problemi di programmazione lineare, mista e quadratica. OSL offre diversi algoritmi e parametri, la gran parte dei quali sono accessibili dall’utente GAMS attraverso un file di opzioni. Nella maggior parte dei casi GAMS/OSL lavorano bene anche senza la necessità di questi file aggiuntivi.

Introduzione a GAMS

GAMS/Cplex

GAMS/Cplex è un risolutore che permette di combinare le capacità di modellazione di GAMS con la potenza degli ottimizzatori di Cplex studiati per risolvere velocemente problemi difficili e di grandi proporzioni con il minimo intervento da parte dell’utente. Anche se è possibile impostare diverse opzioni, GAMS/Cplex calcola e sceglie automaticamente le migliori impostazioni per il problema specifico.

Introduzione a GAMS

GAMS/XA

XA è l’implementazione della libreria della Sunset Software Technology XA Callable Library, contenente risolutori per la programmazione lineare e mista. La capacità di trattare problemi di programmazione intera è stata migliorata ponendo attenzione a particolari sequenze di variabili quali le serie di potenze, di Fibonacci, e le serie con incrementi definibili dall’utente.

Implementazione su GAMS

Introduzione

Completata la formalizzazione matematica del problema si procede all’implementazione software;questa fase consiste nella traduzione nel linguaggio interno di GAMS della funzione obiettivo, dei vincoli e di tutti gli altri elementi che compongono il problema di programmazione lineare o non lineare. Il risultato è un file sorgente che verrá passato al compilatore.


Elementi base

Il codice scritto per creare il modello in GAMS è molto simile alla notazione comunemente impiegata nei testi che trattano la programmazione matematica. All’interno di un file si trovano le sezioni dove vengono definiti:

- gli insiemi;- i parametri del problema;- le variabili decisionali;- la funzione obiettivo ed i vincoli.


Definizione degli insiemi - introduzione

Gli insiemi sono un elemento fondamentale in GAMS, grazie a loro è possibile modellare problemi complessi con un numero ridotto di relazioni (il problema del GVSP è composto da quasi 300 vincoli che vengono modellati con una decina di equazioni definite sugli insiemi). Tutti gli insiemi devono essere definiti nell’apposita sezione, posta all’inizio del codice, che inizia con la parola riservata “Set” o “Sets” e si chiude con “;”.


Definizione degli insiemi - sintassi

La sintassi EBNF per la dichiarazione deli insiemi è:

set nome_ins ["testo"] [/elemento ["testo"] {,elemento [”testo"]} /] {,nome_ins ["testo"] [/elemento ["testo"] {,elemento ["testo"]} /] ;

Ad esempio:

Sets p pattugliatori / Benazzi, Bisaro, Celso, ColussiF, … / …………... t giornate / 04Dec99, 05Dec99, 08Dec99, … 24Apr00 / ;


Definizione degli insiemi - sottoinsiemi

In GAMS è possibile definire anche sottoinsiemi con sintassi analoga a quella impiegata per gli insiemi. Per i sottoinsiemi è prevista la possibilità di specificare il dominio per evidenziare il legame intercorrente con l’insieme generante oltre a poter sfruttare la funzione di controllo del dominio.


Definizione degli insiemi - controllo di dominio

GAMS dispone di una funzione di controllo di dominio: in fase di compilazione controllati gli elementi del sottoinsieme e genera un errore di compilazione qualora venga incontrato un elemento non presente nell’insieme principale. Nel seguente esempio p è l’insieme dei pattugliatori, mentre r(p) è il sottoinsieme di pattugliatori che possono essere responsabili di squadra.


Definizione degli insiemi - esempi

p pattugliatori / Benazzi,Bisaro,Celso,…Zarattin /

r(p) responsabili / Benazzi,Bisaro,Celso /


Definizione dei parametri - introduzione

I parametri vengono utilizzati per inserire informazio-ni note al modellista, ad esempio i coefficienti tecnologici di un problema di product-mix. I parametri possono essere definiti come scalari e liste, inoltre è possibile indicizzarli su uno o più insiemi.


Definizione dei parametri - sintassi

La sintassi EBNF per la dichiarazione dei parametri è:

parameter(s)

nome_param [testo] [/ elemento [=] valore_con_segno {,elemento [=] valore_con_segno} /]

{, nome_param [testo] [/ elemento [=] valore_con_segno {,elemento [=] valore_con_segno} /] } ;


Definizione dei parametri - esempi

Parameters

d(p) tolleranza rispetto al numero medio di servizi/ Benazzi +2Bisaro 0

…Zarattin -3 /

a(p,t) controlla il numero di turni consecutivi ;

a(p,sab(t))=1000000;a(p,dom(t))=10;


Definizione delle variabili - introduzione

Le variabili in GAMS contengono tutte le grandezze che devono essere determinate dalla soluzione del modello; per default sono di tipo free, senza vincoli sul dominio, ma è possibile specificarNe uno dei seguenti:

positive 0 +negative - 0binary 0 1 integer 0 100 solo valori interi


Definizione delle variabili - sintassi

La sintassi per la dichiarazione delle variabili è molto simile a quella per i parametri, con l’importante differenza che le prime non possono essere inizializzate contestualmente alla dichiarazione e l’assegnazione di un valore richiede una forma specifica.

[tipo_var] variable[s] nome_var [testo] { nome_var [testo] } ;

nome_var.fx = valore ;


Definizione delle variabili - esempi

Le due seguenti definizioni di variabili sono equivalenti:

Variables x(p,t) pattugliatore p assegnato al turno tn numero di servizi pro capite

z variabile da miminizzareBinary variable x(p,t);

Oppure

Binary variable x(p,t) pattugliatore p assegnato al turno tVariables n numero di servizi pro capite

z variabile da miminizzare


Inizializzazione delle variabili - esempi

L’inizializzazione avviene nel modo seguente:

Variables x(p,t) … ;

x.fx('Benazzi','04Dec99')=1;x.fx('Sardelli','04Dec99')=1;x.fx('ValeriT','04Dec99')=1;

I valori assegnati devono essere congruenti con i vincoli del problema, pena la non risolvibilità del problema.


Funzione obiettivo e vincoli - introduzione

La funzione obiettivo ed i vincoli devono essere dichiarati in un’apposita sezione del listato che inizia con la parola riservata Equation(s); come altri elementi possono essere indicizzate su uno o più degli insiemi defini, ottenendo in questo modo su set di funzioni uguali ognuna definita su un elemento dell’insieme o degli insiemi. Inoltre, come le variabili, le equazioni non possono essere inizializzate nello stesso momento della dichiarazione.


Funzione obiettivo e vincoli - sintassi

Dichiarazione:

Equation[s] eqn_name text {, eqn_name} ;

Inizializzazione:

nome_eq. .. espressione_algebrica;

I due punti “..” sono l’operatore necessario alla definizione, mentre “espressione_algebrica” può essere un’uguaglianza od una disuguaglianza.


Funzione obiettivo e vincoli - esempi

Dichiarazione:

Equationscost funzione obiettivoteam(t)$norm(t) vincolo sul numero pattugliatori per teamresp(t) vincolo sul numero responsabili per team

La dichiarazione team(t)$norm(t) specifica che l’equazione è incizzata sull’insieme t ma si applica ai soli elementi contenuti nel sottoinsieme di t chiamato norm.


Funzione obiettivo e vincoli - esempi

Definizione:

cost .. z =e= n + sum( (p,t), a(p,t)*( x(p,t)+ x(p,t+1) -1 ) ) ;

team(t)$norm(t) .. sum(p, x(p,t))=e=3;resp(t) .. sum(r(p), x(p,t))=g=1;turni(p) .. sum(t, x(p,t))=l= n+d(p);


Istruzioni conclusive e parametri di output

Un file GAMS si chiude con le istruzioni

- model;- solve - display;


Istruzione model - introduzione

Model raccoglie le equazioni in gruppi e attribisce loro un identificatore in modo da poterli passare alla successuva istruzione solve. I principali modelli disponibili in GAMS sono

LP Linear programming; NLP Nonlinear programming;DNLP Nonlinear programming with discontinuous

derivatives;RMIP Relaxed mixed integer programming;MIP Mixed integer programming; RMINLP Relaxed mixed integer nonlinear programming.


Istruzione model - sintassi

Il caso più semplice inserisce in un unico gruppo tutte le equazioni tramite la parola chiave all, anche se è possibile definirne più di uno. La sintassi è la seguente:

Model(s) model_name [text] [/ all | eqn_name {, eqn, name} /] {,model_name [text] [/ all | eqn_name {, eqn, name} /]} ;

Ad esempio:

Model assegn /all/ ;


Istruzione solve - introduzione

Una volta creato e nominato il modello si chiede a GAMS, tramite l’istruzione solve, di risolverlo utilizzando uno dei risolutori specifici disponibili per il tipo di problema.


Istruzione solve - sintassi

L’istruzione viene inserita nel file con una delle seguenti due forme tra loro equivalenti:

solve model_name using model_type maximizing|minimizing var_name|;

solve model_name maximizing|minimizing var_name usingmodel_type ;

Esempio:

Solve assegn using mip minimizing z ;


Istruzione display

Questa istruzione, che generalmente chiude il listato, fa si che GAMS includa nel file di output i valori richiesti delle variabili specificate. L’istruzione compare con la seguente forma:

Display nome_var.attr {, nome_var.attr}

Per ogni variabile è possibile richiedere, tramite .attr:

.lo = limite inferiore .up = limite superiore

.l = livello o valore del primale .m = valore marginale o duale

Risultati computazionali

Il file è stato elaborato su Dec Alpha 7000/610 con GAMS 2.25.087.

L’elaborazione richiede tempi dell’ordine di pochi decimi di secondo, circa 3500-3600 iterazioni. La funzione obiettivo ha raggiunto il valore 8. Tutte le giornate programmate rispondono ai criteri richiesti. Sono state incontrate cause di non ammissibilità quando sono stati imposti i valori ad alcune variabili decisionali

Descrizione del modello

Il modello sviluppato sfrutta la definizione di insiemi e sottoinsiemi per ottenere la sufficiente elasticità necessaria a gestire i casi particolari, che coincidono con le festività che cadono fuori dai fine settimana e con i soci che svolgono professioni che vincolano in modo pesante la loro disponibilità.

I parametri d, skill sono stati introdotti per personalizzare il numero di servizi procapite e mettere un limite inferiore alle capacità di una squadra.


Le variabili decisionali, x(p,t), devono esprimere la presenza di un determinato pattugliatore in una particolare giornata, quindi sono state scelte di tipo Binary, che è il corrispondente in GAMS delle variabili booleane; oltre a queste sono presenti altre due variabili: n individua il numero medio di turni pro capite, mentre z contiene il valore della funzione obiettivo ed è necessaria a GAMS come oggetto da minimizzare.

La funzione obiettivo è stata costruita in modo da limitare il numero di servizi pro capite.


I vincoli sfruttano l’indicizzazione sugli insiemi e sui sottoinsiemi per generare automaticamente tutte le equazioni necessarie senza doverle scrivere esplicitamente. I casi particolari sono stato gestiti tramite espres-sioni condizionali che li escludevano dal processo di generazione delle equazioni.

Conclusioni

L’esperimento di pianificazione con tecniche di programmazione lineare ha dato risultati positivi, soprattutto grazie all’impiego del calcolatore. Le uniche difficoltà riguardano la schematizzazione del problema e l’acquisizione del linguaggio di GAMS; I risultati hanno incontrato immediatamente l’appro-vazione di chi gestiva il problema, sia in prima battuta per che dopo una analisi più attenta. Il modello, con una piccola manutenzione del codice, può essere utilizzato anche nelle stagioni successive giustificando così gli sforzi compiuti per la sua creazione.

Gestione dei servizi Elaborazione su calcolatore del calendario dei turni di lavoro con tecniche di...

Documents

Transcript of Gestione dei servizi Elaborazione su calcolatore del calendario dei turni di lavoro con tecniche di...