Date of Award

12-2010

Document Type

Thesis

Degree Name

Master of Science (MS)

Committee Chair/Advisor

Dean, Brian C

Committee Member

Hallstrom , Jason O

Committee Member

Jacobs , David P

Abstract

The standard NP-hard knapsack problem can be interpreted as a scheduling problem with n jobs with weights w1 . . .wn and processing times p1 . . . pn, where our goal is to order the jobs on a single machine so as to maximize the weight of all jobs completing prior to a known common deadline d. In this paper, we study the uncertain capacity knapsack problem (UCKP), a generalization of this problem in which the deadline d is not known with certainty, but rather is provided as a probability distribution, and our goal is to order the jobs so as to maximize the expected weight of the set of jobs completing by the deadline. We develop a polynomial-time approximation scheme (PTAS) for this problem. We make no assumptions about probability distributions except that each job, scheduled by itself, completes by the deadline with some constant probability.

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.