This paper proposes a novel schedule-based approach for scheduling a continuous stream of batch jobs on the machines of a computational Grid. Our new solutions represented by dispatching rule Earliest Gap| Earliest Deadline First (EG-EDF) and Tabu search are based on the idea of ¯lling gaps in the existing schedule. EG-EDF rule is able to build the schedule for all jobs incrementally by applying technique which ¯lls earliest existing gaps in the schedule with newly arriving jobs. If no gap for a coming job is available EG-EDF rule uses Earliest Deadline First (EDF) strategy for including new job into the existing schedule. Such schedule is then optimized using the Tabu search algorithm mov- ing jobs into earliest gaps again. Scheduling choices are taken to meet the Quality of Service (QoS) requested by the submitted jobs, and to optimize the usage of hardware resources. We compared the proposed solution with some of the most common queue-based scheduling algo- rithms like FCFS, EASY back¯lling, and Flexible back¯lling. Experi- ments shows that EG-EDF rule is able to compute good assignments, often with shorter algorithm runtime w.r.t. the other queue-based al- gorithms. Further Tabu search optimization results in higher QoS and machine usage while keeping the algorithm runtime reasonable.
Comparison of multi criteria scheduling techniques
Baraglia R;
2008
Abstract
This paper proposes a novel schedule-based approach for scheduling a continuous stream of batch jobs on the machines of a computational Grid. Our new solutions represented by dispatching rule Earliest Gap| Earliest Deadline First (EG-EDF) and Tabu search are based on the idea of ¯lling gaps in the existing schedule. EG-EDF rule is able to build the schedule for all jobs incrementally by applying technique which ¯lls earliest existing gaps in the schedule with newly arriving jobs. If no gap for a coming job is available EG-EDF rule uses Earliest Deadline First (EDF) strategy for including new job into the existing schedule. Such schedule is then optimized using the Tabu search algorithm mov- ing jobs into earliest gaps again. Scheduling choices are taken to meet the Quality of Service (QoS) requested by the submitted jobs, and to optimize the usage of hardware resources. We compared the proposed solution with some of the most common queue-based scheduling algo- rithms like FCFS, EASY back¯lling, and Flexible back¯lling. Experi- ments shows that EG-EDF rule is able to compute good assignments, often with shorter algorithm runtime w.r.t. the other queue-based al- gorithms. Further Tabu search optimization results in higher QoS and machine usage while keeping the algorithm runtime reasonable.File | Dimensione | Formato | |
---|---|---|---|
prod_139020-doc_128276.pdf
solo utenti autorizzati
Descrizione: Comparison of multi criteria scheduling techniques
Tipologia:
Versione Editoriale (PDF)
Dimensione
210.97 kB
Formato
Adobe PDF
|
210.97 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.