DOS Seminar - Liron Yedidsion

Event Details
  • Date/Time:
    • Thursday October 15, 2015 - Friday October 16, 2015
      11:00 am - 10:59 am
  • Location: Main 228
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
No contact information submitted.

Summary Sentence: DOS Seminar - Liron Yedidsion

Full Summary: No summary paragraph submitted.

TITLE: A Polynomial Time Approximation Scheme (PTSA) for the bi-scenario sum of completion times problem


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.

Additional Information

In Campus Calendar

School of Industrial and Systems Engineering (ISYE)

Invited Audience
Undergraduate students, Faculty/Staff, Graduate students
No keywords were submitted.
  • Created By: Anita Race
  • Workflow Status: Published
  • Created On: Oct 12, 2015 - 6:09am
  • Last Updated: Apr 13, 2017 - 5:17pm