Algorithms in Throughput Maximization

• Author / Creator

  Hyatt-Denesik, Dylan V

• Scheduling problems are problems in which jobs are assigned to machines at particular times. A common objective of scheduling is to schedule as many jobs before their deadline as possible, called Throughput Maximization. In this thesis, we provide algorithms for various cases of Throughput Maximization scheduling problems, varying bounds on the number of release times, job sizes, deadlines, and even the number of release times the release time and deadlines of a job can span across.In Chapter 2, we examine the case where both the number of job sizes and the number of release times is bounded by a constant value. This result is progress to closing a known open problem of Throughput Maximization with only constant sized job sizes [20]. This algorithm is a dynamic program that relies on a framework based around what is known as the Jackson Rule or Earliest Due Date ordering [13]. In Chapter 3, we consider the case of Throughput Maximization where the number of release times and deadlines are bounded by a constant value on a constant number of machines. In this Chapter we find a pseudo-polynomial time exact algorithm that we extend to a PTAS. This algorithm exploits the fact that we can partition the schedule into intervals between two consecutive release times or deadlines, which allows us to assign jobs to each of these intervals in polynomial time. We also extend the show that this case is NP-Complete by a reduction from the Partition problem. In Chapter 4, we present the most general result in this thesis by finding a pseudo-polynomial time algorithm for the case of Throughput Maximization where the only restriction is that there are a constant number of release times, which we extend to the case where the interval between a jobs release time and deadlines has only a constant number of release times, called the span. This algorithm makes use of similar approach to that of Chapter 3, in that we can partition jobs to intervals between consecutive release times and find the schedule interval by interval. The result for the constant span, we use the first algorithm of this chapter as a subroutine over the maximum span of release times

• Subjects / Keywords

  • Real-time scheduling
  • Scheduling
  • throughput maximization
  • Approximation
  • Approximation Algorithms
  • Algorithms

• Graduation date

  Fall 2019

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/r3-z2c9-qq71

• License

  Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.