Scholarlink

<p>This paper studies a bi-criteria parallel machine scheduling problem with uncertain processing times to minimize makespan and total completion time. We adopt a scenario-based approach for uncertainty and assume that a scenario index can take any real value in an interval. This index value can represent, for example, the amount of congestion in a network. We assume that the job processing times are non-decreasing polynomial functions of fixed degrees with respect to the scenario index. To tackle multi-criteria optimization in the presence of uncertainty, researchers have proposed the concept of multi-scenario efficient set&#xa0;(Botte and Schöbel 2019, Engau and Sigler 2020). We adopt this framework and want to compute, in polynomial time, an approximation of this set with theoretical performance guarantees. Based on a dynamic programming framework, with carefully designed states, we obtain a Fully Polynomial-Time Approximation Scheme (FPTAS) for the problem.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Approximating multi-scenario efficient solutions for an uncertain bi-criteria parallel machine scheduling problem

  • 期刊论文

  • 发表日期：

    2026年6月30日

查看全文
  • Xiechen Zhang,
  • Eric Angel,
  • Feng Chu,
  • Damien Regnault

摘要

This paper studies a bi-criteria parallel machine scheduling problem with uncertain processing times to minimize makespan and total completion time. We adopt a scenario-based approach for uncertainty and assume that a scenario index can take any real value in an interval. This index value can represent, for example, the amount of congestion in a network. We assume that the job processing times are non-decreasing polynomial functions of fixed degrees with respect to the scenario index. To tackle multi-criteria optimization in the presence of uncertainty, researchers have proposed the concept of multi-scenario efficient set (Botte and Schöbel 2019, Engau and Sigler 2020). We adopt this framework and want to compute, in polynomial time, an approximation of this set with theoretical performance guarantees. Based on a dynamic programming framework, with carefully designed states, we obtain a Fully Polynomial-Time Approximation Scheme (FPTAS) for the problem.