Problemi di tipo NP-difficile e NP-completo

[Francesco Fonte]

Buon pomeriggio ragazzi. Ho provato ad inoltrarmi nelle precedenti discussioni senza riuscire a trovare indicazioni sulla soluzione del problema in oggetto.
In pratica vi chiedo se abbiate o meno maturato delle esperienze nella soluzione di problemi che nella teoria della complessità algoritmica, rientrano nell'ambito dei tipo NP-difficile e NP-completo.
L'ambito di applicazione è quello della pianificazione degli orari di lavoro del personale, dove accanto a normative di legge, accordi di categoria e contrattuali, preferenze, limitazioni di orari, competenze degli addetti, necessità di copertura dei presidi, occorre stendere un orario che medi tutti questi fattori.
Solo un sistema euristico può affrontare quanto sopra in modo efficace.
Pensate ad un capo reparto che deve gestire una squadra di 100 persone dove le variabili sono:
- 10 tipi di attività che potrebbero svolgere
- orari di ingresso possibili senza limitazione alcuna
- durata orario di lavoro compresa tra le 3 ore e le 8 ore
- esigenze specifiche di ognuno dei 100 addetti (giorni di riposo, ferie, esigenze specifiche, ...)
Riuscirvi con un semplice foglio elettronico affidandosi alla capacità dell'uomo è cosa ardua.

Mi dareste una mano?
Grazie
Francesco