Scholarlink

<p>We consider a certain proportionate flow shop scheduling problem with step-deteriorating processing times and study two objective functions: makespan and sum of completion times. We reformulate these problems as monotone dynamic programs that fall into both FPTAS frameworks of Alon and Halman. Consequently, we get for each one of them an FPTAS and a strongly polynomial FPTAS, where the latter one improves upon the running time of the fastest FPTAS known to date.</p>

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

A faster fully polynomial time approximation scheme for proportionate flow shop scheduling with step-deteriorating processing times

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年12月8日

查看全文
  • Nir Halman

摘要

We consider a certain proportionate flow shop scheduling problem with step-deteriorating processing times and study two objective functions: makespan and sum of completion times. We reformulate these problems as monotone dynamic programs that fall into both FPTAS frameworks of Alon and Halman. Consequently, we get for each one of them an FPTAS and a strongly polynomial FPTAS, where the latter one improves upon the running time of the fastest FPTAS known to date.