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.
Recommended Citation
Dabney, Matthew, "A PTAS for the Uncertain Capacity Knapsack Problem" (2010). All Theses. 982.
https://open.clemson.edu/all_theses/982