Durata fissa I lavori devono essere programmati su un numero fisso di code

Question

Durata fissa I lavori devono essere programmati su un numero fisso di code

Naviga le tue risposte

#1 da (3 voti)
#2 da (1 voti)

1

Diciamo che ho 9 lavori con le stime di quanto tempo ci vorranno per completare e 3 code che elaborano questi lavori - questo costituisce un lotto. Si noti che tutti i lavori vengono assegnati in anticipo a una coda e non in fase di esecuzione. Pertanto, con una pianificazione scadente, alcune code potrebbero rimanere inattive mentre altre continuano a elaborare un lavoro.
Tutti questi lavori dovrebbero essere distribuiti attraverso le code in modo tale che il tempo totale per completare tutte le code sia quasi uguale.

Si consideri:

1.Abbassa Q2, Q3 completato in 15 minuti e rimane inattivo mentre Q1 richiede altri 10 minuti per essere completato.

Batch1:

+------+----+----+----+
|  #   | Q1 | Q2 | Q3 |
+------+----+----+----+
| 1    |  5 |  5 |  5 |
| 2    | 15 |  5 |  5 |
| 3    |  5 |  5 |  5 |
+------+----+----+----+
| Time | 25 | 15 | 15 |
+------+----+----+----+
| Total| 25           |
+------+----+----+----+

2.Ora, idealmente, i lavori dovrebbero essere distribuiti come ...

+------+----+----+----+
|  #   | Q1 | Q2 | Q3 |
+------+----+----+----+
| 1    | 15 |  5 |  5 |
| 2    |  - |  5 |  5 |
| 3    |  - |  5 |  5 |
| 4    |  - |  5 |  5 |
+------+----+----+----+
| Time | 15 | 20 | 20 |
+------+----+----+----+
| Total| 20           |
+------+----+----+----+

Questo sembra essere un problema di programmazione semplice, ma mi occupo di centinaia di tali lavori, suddivisi in più lotti. Dove ogni partita inizierà solo al completamento del primo. Quindi richiederei un qualche algoritmo per decidere il programma. Qualche idea..? Grazie

Aggiornamento:

Aggiunta di ulteriori informazioni basate sul feedback ...

I lavori in un batch sono fissi.
Non ci sono dipendenze tra lavori all'interno di un batch, ma esistono dipendenze tra lotti. Quindi possiamo cercare di risolvere il problema per un singolo batch e la soluzione si applicherà a tutti i batch.
Problema del mondo reale: sto modellando un problema sul caricamento dei dati (ETL) e l'intero processo di caricamento richiede 5-6 ore, che ha diversi lotti. Alla ricerca di modi per ridurre il tempo complessivo.

algorithms

posta Kent Pawar 11.05.2014 - 07:57

fonte

2 risposte

Leggi altre domande sui tag algorithms

Sviluppo di un grande sistema in una piccola azienda [duplicato] Quando il mio codice è automaticamente in GPL?

score 3 · Answer 1

Questo è correlato al problema nello zaino , tranne per il fatto che hai più zaini di dimensioni variabili. Ciò lo rende enormemente più semplice.

Un semplice algoritmo consiste nell'ordinare i lavori per dimensione e quindi, partendo dal lavoro più grande, assegnare ciascuno (uno alla volta) alla coda con il minimo lavoro ad esso assegnato (quindi sì, è necessario mantenere una maniglia su quanto lavoro è già assegnato a ciascuna coda dal batch). Non sono sicuro al 100% se questo produrrà la soluzione migliore, ma ne produrrà uno abbastanza buono ed è facile da implementare correttamente .

Dove le cose diventano più complesse è quando si hanno incertezze nei costi, nelle dipendenze tra i lavori o dove si hanno attività ad alta priorità che si verificano e si interrompono occasionalmente alcune code. Non hai menzionato nessuno di questi, quindi ti suggerirei di andare con il semplice algoritmo.

Proviamo ad assegnare i lavori [5,5,15,5,5,5] a due code da dimostrare.

Ordina i lavori:

[15,5,5,5,5,5]
Assegna i lavori nell'ordine:

A: [] (dimensione 0), B: [] (dimensione 0)
A: [15] (dimensione 15), B: [] (dimensione 0)
A: [15] (dimensione 15), B: [5] (dimensione 5)
A: [15] (dimensione 15), B: [5,5] (dimensione 10)
A: [15] (dimensione 15), B: [5,5,5] (dimensione 15)
A: [15,5] (taglia 20), B: [5,5,5] (taglia 15)
A: [15,5] (taglia 20), B: [5,5,5,5] (taglia 20)

Sembra equilibrato.

score 1 · Answer 2

I lavori in un batch sono stati risolti ad esempio batchA - ha i lavori jobA1, jobA2 ecc.

O abbiamo solo un sacco di lavori, e dobbiamo decidere i batch e le code nei batch.

Può essere considerato come un problema di zaino e devi trovare tre kanpsack con poca differenza nei valori.

I tre zaini sono le tre code di schedulazione.

Se riesci a spiegare la relazione tra i posti di lavoro, ciò aiuterebbe tutti noi a trovare la soluzione.

Ad esempio, Job1 DEPENDS_ON Job2 e allo stesso modo.