Design and evaluation of multi-objective online scheduling strategies for parallel machines using computational intelligence
Loading...
Date
2006-11-24T09:17:01Z
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This thesis presents a methodology for automatically generating
online scheduling algorithms for a complex objective defined by a
machine provider. Such complex objective functions are required if
the providers have several simple objectives. For example, the
different relationships to the various users must be incorporated
during the development of appropriate scheduling algorithms. Our
research is focused on online scheduling with independent parallel
jobs, multiple identical machines and a small user community.
First, Evolutionary Algorithms are used to exemplarily create a
7-dimensional solution space of feasible schedules of a given
workload trace. Within this step no preferences between different
basic objectives need to be defined. This solution space enables
the resource providers to define a complex evaluation objective
based on their specific preferences. Second, optimized scheduling
strategies are generated by using two different approaches. On the
one hand, an adaptation of a Greedy scheduling algorithm is
applied which uses weights to create an order of jobs. These job
weights are extracted again from workload traces with the help of
Evolutionary Algorithms. On the other hand, a Fuzzy rule based
scheduling system will be applied. Here, we classify a scheduling
situation which consists of many parameters like the day time, the
week day, the waiting queue length etc. Depending on this
classification, a Fuzzy rule based system chooses an appropriate
sorting criterion for the waiting job queue and a suitable
scheduling algorithm. Finally, both approaches, the Greedy
scheduling strategy and the Fuzzy rule based scheduling system,
are compared by using again workload traces. The achieved results
demonstrate the applicability of our approach to generate such
multi-objective scheduling strategies.
Description
Table of contents
Keywords
Online scheduling, Multi-objective optimization, Evolutionary algorithms, Parallel machines, Paretofront, Computational grids, Scheduling