Abstract
dc:description.abstractThe 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.
Degree
thesis:*- Name thesis:degree_name
- Master of Science (MS)
- Level thesis:degree_level
- Thesis
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Dabney, Matthew
- Contributors dc:contributor
-
- Dean, Brian C
- Hallstrom , Jason O
- Jacobs , David P
Subjects
dc:subject × 6Identifiers
dc:identifier.*- Repository record dc:identifier
- https://open.clemson.edu/all_theses/982