Problema di Programmazione Dinamica

[RacheleN93]

Salve a tutti,

Mi ritrovo davanti ad un problema che non riesco a risolvere in nessun modo:

Sia dato un progetto che è stato suddiviso in n sottoprogetti numerati da 1 ad n, in maniera tale che il sottoprogetto 1 deve essere iniziato e terminato prima che venga iniziata l’esecuzione del sottoprogetto 2, quindi deve essere eseguito il sottoprogetto 2, e così via.
Supponiamo che ci siano due modalità di esecuzione di ogni sottoprogetto. Sia ci(1) il costo di eseguire il sottoprogetto i nella prima modalità, e ci(2) il costo di eseguire lo stesso sottoprogetto nella seconda modalità. Sia ti(1) il tempo richiesto dall’esecuzione del sottoprogetto i nella modalità 1 e ti(2) il tempo richiesto dall’esecuzione del sottoprogetto i nella modalità 2. Si assuma che i tempi siano interi.
Si vuole determinare una modalità di minimo costo per completare l’intero progetto in un tempo non superiore a T. Si assuma che il costo del progetto sia la somma dei costi dei sottoprogetti e che il tempo totale sia la somma dei tempi dei sottoprogetti.


A prima vista mi sembra isomorfo al ad un job shop scheduling problem, tuttavia essendoci non una ma due variabili da tenere in considerazione ad ogni passaggio (devo scegliere ad ogni passo tra tempo e costo) non so come risolverlo!
In ricorsione è molto semplice, ma in programmazione dinamica non so cosa fare.
Oltretutto essendoci oggetti tra loro non compatibili (ad esempio le modalità dei sottoprogetti) non posso neanche usare il knapsack problem o un derivato.

Qualcuno ha qualche idea?