*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
TITLE: A Polynomial Time Approximation Scheme (PTSA) for the bi-scenario sum of completion times problem
ABSTRACT:
An influential aspect of any scheduling problem is the processing time of a tasks (job), which typically can be deterministic, stochastic or even uncertain. Scheduling according to unique and known processing times (a.k.a. Nominal) may be naïve, since real production systems are usually subject to inherent uncertainty. Moreover, typically, there are several objectives that the decision-maker seeks to satisfy. We offer a novel approach in the context of deterministic scheduling, borrowed from scenario-based optimization. The new approach copes with uncertainty by simultaneously optimizing a the sum of completion times criterion under two different instances of the processing times. We term the new problem a bi-scenario trade-off problem. We develop a PTAS that approximates the Pareto-optimal set of solutions and show that it is tight. Then we introduce a Branch-and-Bound based algorithm that solves the problem optimally.
