Qualcuno riconosce questo problema di programmazione? C'è un algoritmo per questo?

Question

Qualcuno riconosce questo problema di programmazione? C'è un algoritmo per questo?

#1 da (1 voti)

5

Considera il seguente problema:

Descrizione :

Ci sono n lavori J ₁ ... J _n con tempi di ciclo C ₁ .... C _n. Trova un quantum del tempo e una tabella di pianificazione considerando che:

qualsiasi elemento della tabella contiene al massimo un lavoro
il gestore lavori elaborerà un elemento alla volta, ad esempio eseguirà il lavoro (se presente) quindi, dopo che un tempo quantum passa, passerà all'elemento successivo.
il gestore lavori eseguirà il loopback, ovvero dopo l'ultimo elemento continuerà con il primo.
la ciclicità deve essere mantenuta, ovvero la distanza tra due eventuali occorrenze consecutivi (compresi i loopback) del lavoro J _k (k = 1, n) deve essere uguale a C _k / tempo quantum .
la tabella deve essere il più breve possibile.

Esempio :

J ₁ - 4 secondi ciclicità
J ₂ - 6 secondi ciclicità
J ₃ - ciclicità di 8 secondi

Soluzione di esempio :

tempo quantum = 1 s

0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 seconds
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|J1|J2|J3|  |J1|  |  |J2|J1|  |J3|  |J1|J2|  |  |J1|  |J3|J2|J1|  |  |  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

La mia sensazione è che questo appartiene alla famiglia dei problemi di pianificazione e che potrebbe essere un caso speciale di un problema più generale. È così? Ho provato a cercarlo online ma non ho trovato nulla di simile. Dal momento che non ho alcuna esperienza con i problemi di pianificazione non sono nemmeno sicuro di cosa cercare.

Da quello che vedo:

la durata totale della tabella di pianificazione dovrebbe essere il multiplo comune più piccolo di C ₁ ... C _n.
il tempo quantico dovrebbe essere almeno GCD (C ₁, ..., C _n) / n. - Questa non è necessariamente la soluzione ottimale.

Questo mi porta a credere che esista una soluzione diretta e non una che coinvolga la programmazione dinamica. È così?

Qualcuno potrebbe indicarmi alcune risorse, forse anche un algoritmo, per questo problema?

Sono anche curioso di variazioni in cui i lavori possono essere distribuiti tra più di una tabella di pianificazione.

GCD = Greatest Common Divider

Modifica : non sto chiedendo come pianificare N lavori con determinati tempi di ciclo; Sono sicuro che ci sono modi più dinamici per farlo come alcuni hanno suggerito. Il mio problema è " Trova un quantum del tempo e una tabella di pianificazione considerando che: [...] ". È anche possibile che possa avere le sue radici in alcune parti della matematica.

algorithms problem-solving scheduling

posta DonComo 20.05.2014 - 15:42

fonte

1 risposta

Leggi altre domande sui tag algorithms problem-solving scheduling

Progettare le comunicazioni per l'estensibilità Come fare le cose passo dopo passo

score 1 · Answer 1

Potresti determinare la pianificazione migliore utilizzando una coda di priorità . Dove sono i momenti decisionali nella programmazione? È quando hai più di un ciclo per iniziare in un dato secondo.

Dovrai disporre di un tipo di dati "pianificazione" che rappresenti una possibile pianificazione (i dati che hai scritto sopra sono un perfetto esempio dei dati che dovresti rappresentare qui).

Quindi lo pseudo algoritmo dovrebbe essere il seguente:

Aggiungi ciascun tipo di ciclo alla sua pianificazione e invia ogni pianificazione su una coda di priorità, assegnando la priorità al più piccolo GCD * (C1, ..., Cn) / n valore.

Quindi, iniziando dalla pianificazione con il valore GCD * (C1, ..., Cn) / n più piccolo, creare nuovi programmi dal vecchio aggiungendo nuovi cicli da avviare.

Continua per tutto quello che vuoi.

Decidi quando la pianificazione dovrebbe terminare e siccome è una coda di priorità, ti garantiamo che il primo elemento è ottimale in termini di GCD * (C1, ..., Cn) / n in ogni punto dato .

Spero che ti aiuti.