Physical Sciences and Mathematics Commons^™

Some Topics On Deterministic Scheduling Problems, Yumei Huo

Dissertations

Sequencing and scheduling problems are motivated by allocation of limited resources over time. The goal is to find an optimal allocation where optimality is defined by some problem specific objectives.

This dissertation considers the scheduling of a set of ri tasks, with precedence constraints, on m >= 1 identical and parallel processors so as to minimize the makespan. Specifically, it considers the situation where tasks, along with their precedence constraints, are released at different times, and the scheduler has to make scheduling decisions without knowledge of future releases. Both preemptive and nonpreemptive schedules are considered. This dissertation shows that optimal …