Salve ragazzi,
all'università (sono all'Alma Mater) mi hanno assegnato un progetto sulla schedulazione di lavori in presenza di vincoli ed in cui si consiglia di utilizzare la tecnica del backtracking
Cercando su questo forum ho trovato delle specifiche che si avvicinano molto al mio problema, sapete come aiutarmi?
Un’attività è svolta mediante l’esecuzione, da parte di più persone, di alcuni lavori elementari di cui è nota la durata in unità di tempo (giorni, mesi etc.). L’esecuzione dei lavori può comportare l’esistenza di vincoli temporali: un lavoro, ad esempio, non può cominciare se non è finito un altro (o altri) e cosi via. Si vuole progettare e realizzare un’applicazione per controllare la correttezza di attività lavorative e per proporre una schedulazione dei lavori, se esiste, che sia rispettosa dei vincoli posti. In input si forniscono i dei lavori e i vincoli associati. L’output atteso è la schedulazione dei lavori. La specifica di un lavoro elementare consiste della coppia
<id-lavoro, durata>
Un vincolo, invece, è espresso mediante una tupla del tipo
<I/F, id-lav1, P/D, I/F, id-lav2>
cioè l’inizio(I) o la fine(F) di un lavoro id-lav1, deve avvenire prima(P)/dopo(D) dell’inizio(I)/fine(F) del lavoro id-lav2.
Se tra alcuni lavori non sussistono dipendenze, allora i lavori vanno eseguiti prima possibile, ossia in parallelo.
Quale semplice esempio, si consideri l’input:
#lavori
( 0, 3 )
( 1, 4 )
( 2, 5 )
( 3, 3 )
( 4, 3 )
#vincoli
( I, 1, D, F, 0 )
( I, 4, D, F, 2 )
Possibile output:
t 0 1 2 3 4
0 * - * * -
1 * - * * -
2 * - * * -
3 - * * - -
4 - * * - -
5 - * - - *
6 - * - - *
7 - - - - *
In alternativa l’output può essere prodotto generando una successione di tuple che indicano l’istante di inizio, il lavoro e la sua durata: <tInizio, id-lav, durata>.
Una possibile soluzione (inefficiente) può essere basata sulla tecnica backtracking. Come punti di scelta si utilizzano gli istanti temporali (nel caso peggiore la durata complessiva dell’attività è la somma delle durate dei lavori, conseguente ad una esecuzione totalmente sequenziale), come scelte i lavori che possono eseguire nell’stante considerato.
se qualcuno puo'e vuole aiutarmi posso anche postare il codice da me scritto finora....l'approccio che sto usando e'questo:scrivere una classe astratta Backtracking che implementi il solo metodo risolvi() ,ereditare da essa una classe GestioneSchedulazioni che implementi i metodi astratti (secondo lo schema del "template method"),scrivere una classe Lavoro ed una Vincolo adatte a rappresentare tali oggetti come richiesto,infine una classe di Test(con il main) ed una per raccogliere in input i dati....ma il mio problema e'sostanzialmente nella classe GestioneLavori che stabilisce in che maniera assegnare i lavori a seconda degli istanti e dei vincoli.....vi prego se sapete aiutarmi rispondetemi perche'sono ad un punto che non so'piu'che fare!!
Rispondi quotando
magari ci viene qualche illuminazione
