Algoritmo di pianificazione

Question

Ho un problema di pianificazione in cui nuovi lavori (serie di attività la cui esecuzione è collegata in sequenza) arrivano ogni pochi secondi circa.
Ogni lavoro richiede l'allocazione di alcune risorse a intervalli noti.
Per esempio:
Job j1 è un insieme di compiti per i quali ci riserviamo risorse {r1, r2, r3} su un modello di programmazione noto:

r1:[t0 .. t1=t0+td1], 
r2:[t2=t1+td2+i2 .. t3=t2+td3] 

• T0 essendo l'ora di inizio dell'esecuzione
• TD1 è la lunghezza dell'assegnazione delle risorse per r1
• t1 è l'ora di fine dell'allocazione risorse per r1
• i1 è la lunghezza di il perioide in attesa tra r1, r2 e così via.

Nell'esempio, un nuovo j2 lavoro viene prevista subito dopo l'esecuzione J1 è iniziata. Il primo orario di inizio per j2 è t1. Un lavoro potrebbe richiedere alcuni minuti di esecuzione, la maggior parte dei quali consiste nell'attesa.

Ho un programma di pianificazione che esamina la tabella di prenotazione corrente e decide qual è il primo momento di partenza possibile per un nuovo lavoro con tempi di allocazione fissi e periodi di attesa ed effettua le prenotazioni di conseguenza.

(Ma in realtà, il periodo di attesa non ha realmente bisogno di essere risolto, ma entro una certa percentuale (forse il 5%) e potrebbero esserci alternative all'utilizzo delle risorse, ad esempio, se la risorsa r3.1 è prenotata, quindi 3.2 può essere utilizzato come tale per ottenere la stessa cosa.)

Tuttavia, se è necessario lo scheduler (sì, è stato suggerito), è possibile regolare dinamicamente tutte le allocazioni del programma quando arriva un nuovo lavoro per massimizzare il totale lavoro svolto (in un giorno) sfruttando il fatto che i tempi di attesa non devono essere esattamente come dati e la possibilità di esecuzione parallela con alcuni duplicati di resrouce (3.1/3.2), quindi guarderei a un completamente diverso schema di programmazione (rispetto al mio attuale approccio di start-as-soon-possible).

1. Quale schema di pianificazione chiamereste quello allora?
2. Qualche suggerimento sull'approccio al (nuovo) problema?

Answer 1

quanto riguarda la tua domanda per quanto riguarda "alternative a Uso delle Risorse":

Il modello più comunemente implementato per affrontare questo tipo di problema è la Object Pool Pattern
L'esempio più conosciuto per questo probabilmente è il ThreadPool

Suggerisco di implementare una classe ResourcePool con un metodo int GetResource(ResourceType type, int durationInSeconds). Il valore restituito indica quando sarà disponibile la risorsa successiva dello ResourceType

Answer 2

Potrebbe trattarsi del RCPSP (problema di pianificazione del progetto con risorse limitate). Le tecniche di soluzione spaziano dalla programmazione di interi e dalla programmazione di vincoli a varie euristiche.La tecnica dipende i dettagli come orizzonte di pianificazione, come attività/posti di lavoro utilizzano le risorse/share, la velocità è necessario un piano di soluzione, ecc

vedi:

https://developers.google.com/optimization/scheduling/job_shop

http://www.laas.fr/files/ROC/2014-Presentations/MILP-RCPSP-PMS2014.pdf