Theses and Dissertations

Amit Bugde

Issuing Body

Mississippi State University

Advisor

Dandass, Yoginder

Committee Member

Ramkumar, Mahalingham

Committee Member

Banicescu, Ioana

Date of Degree

5-13-2006

Document Type

Graduate Thesis - Open Access

Major

Computer Science

Degree Name

Master of Science

College

James Worth Bagley College of Engineering

Department

Department of Computer Science and Engineering

Abstract

This research presents a hybrid algorithm that combines List Scheduling (LS) with a Genetic Algorithm (GA) for constructing non-preemptive schedules for soft real-time parallel applications represented as directed acyclic graphs (DAGs). The execution time requirements of the applications' tasks are assumed to be stochastic and are represented as probability distribution functions. The performance in terms of schedule lengths for three different genetic representation schemes are evaluated and compared for a number of different DAGs. The approaches presented in this research produce shorter schedules than HLFET, a popular LS approach for all of the sample problems. Of the three genetic representation schemes investigated, PosCT, the technique that allows the GA to learn which tasks to delay in order to allow other tasks to complete produced the shortest schedules for a majority of the sample DAGs.

URI

https://hdl.handle.net/11668/17315

Download

Share

COinS