Turni degli uffici comunali

Il sindaco della città più bella del mondo, per venire incontro alle esigenze dei propri cittadini, vuole riorganizzare gli orari dell'ufficio comunale. La settimana viene suddivisa in $I=\{1,\ldots,m\}$ fasce orarie. Un sondaggio presso le categorie dei cittadini $h=1,\ldots,H$ stabilisce per ciascuna categoria quali sono le fasce orarie preferite. Questa informazione viene descritta da una matrice a componenti 0-1: $d_{hi} = 1$ se la categoria $h$ predilige la fascia $i$ e $0$ altrimenti (si noti che ogni categoria può esprimere più preferenze, quindi su una riga della matrice vi possono essere più elementi a 1). Il sindaco incontra anche i rappresentanti degli impiegati comunali e concorda con loro il minimo numero di impiegati necessari in ciascuna fascia per far funzionare l'ufficio ($b_i$), la composizione dei turni di lavoro ammissibili ($j=1,\ldots,n$) e il loro costo $c_j$. Un turno di lavoro consiste in un sottoinsieme di fasce nel quale uno stesso impiegato è allo sportello. Questa informazione è descritta da una matrice $0-1$: $a_{ij}=1$ se il turno $j$ copre la fascia $i$.

Il problema del sindaco consiste nel determinare in quali fasce aprire gli sportelli dell'ufficio comunale in modo che ciascuna categoria di cittadini veda soddisfatte almeno 2 delle proprie preferenze. Inoltre deve stabilire quali turni di lavoro attivare in modo da garantire in ogni fascia attivata la presenza del numero minimo di impiegati, minimizzando il costo complessivo.

Leggi i suggerimenti <>