Back to search

Georgia Institute of Technology

Scheduling and assignment on dynamic processor networks

Abstract

dc:description.abstract

We address the problem of scheduling tasks characterized by dynamic completion time behavior. Existing scheduling methodologies reduce problems to using constant task durations and are therefore not suitable for problems with more complex completion time behavior. One such problem is scheduling applications on computer networks with time-varying communication channel capacities. We present a methodology that can be used to solve such problems. The specific contributions of this work are: (a) a novel representation for the completion time of tasks in scheduling problems, (b) a method for approximating that representation efficiently using an affine over-approximation, and (c) a mixed-integer programming-based formulation to solve a variety of scheduling problems using this representation and approximation. The resulting framework can be used to solve scheduling problems with time-varying task durations, and thus solve problems with time-varying communication links or resources. A case study is provided, in which we devise a scheduling scheme for computation on a computer network composed of processors onboard a satellite constellation. This example is an instance of scheduling applications on computer networks with known time-varying communication channel capacities and the results of the case study demonstrate the improvement of using the approximation method over existing methods.

Degree

thesis:*
Level thesis:degree_level
Masters
Department dc:contributor.department
Electrical and Computer Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2020

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Mains, John B.
Advisor dc:contributor.advisor
  • Feron, Eric
Committee members dc:contributor.committeemember
  • Coogan, Samuel
  • Bloch, Matthieu

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/63680

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Mains, John B.. Scheduling and assignment on dynamic processor networks. Masters thesis, Georgia Institute of Technology, 2020. http://hdl.handle.net/1853/63680