Authors: Franke, Carsten
Title: Design and evaluation of multi-objective online scheduling strategies for parallel machines using computational intelligence
Language (ISO): en
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.
Subject Headings: Online scheduling
Multi-objective optimization
Evolutionary algorithms
Parallel machines
Paretofront
Computational grids
Scheduling
URI: http://hdl.handle.net/2003/23102
http://dx.doi.org/10.17877/DE290R-245
Issue Date: 2006-11-24T09:17:01Z
Appears in Collections:Lehrstuhl für Automatisierung und Robotertechnik

Files in This Item:
File Description SizeFormat 
2006_11_15_Publication_Thesis_Carsten_Franke.pdfDNB15.45 MBAdobe PDFView/Open
kurzfassung.pdf22.58 kBAdobe PDFView/Open


This item is protected by original copyright



All resources in the repository are protected by copyright.