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.