Scholarlink

<p>We study scheduling problems subject to supporting precedence, where each job requires a set of preparatory operations, referred to as supporting tasks. Motivated by diverse real-world applications featuring sequential and hierarchical processes, we introduce a nested structure for all supporting tasks. The objective function exclusively accounts for jobs, including total completion time and the weighted and unweighted number of late jobs. By leveraging the optimality properties unique to this structure, we develop efficient polynomial and pseudo-polynomial dynamic programming algorithms to solve single-agent problems in a single-machine setting, including an extension to the case allowing for job rejection. Then we consider two-agent problems with a constrained optimization form. These algorithms are adapted to tackle the additional complexity of the competing interests of two agents. The extension to the proportionate flow-shop problems highlights their inequivalence against counterpart problems in the single-machine setting in the presence of supporting precedence. We show that the problems are significantly more complex than their single-machine counterparts, namely that problems with due-date-based criteria are strongly <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\mathcal{N}\mathcal{P}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">N</mi> <mi mathvariant="script">P</mi> </mrow> </math></EquationSource> </InlineEquation>-hard.</p>

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

Single-machine and flow-shop scheduling with supporting tasks in a nested structure

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年8月8日

查看全文
  • Renjie Yu,
  • Daniel Oron,
  • Bertrand M. T. Lin

摘要

We study scheduling problems subject to supporting precedence, where each job requires a set of preparatory operations, referred to as supporting tasks. Motivated by diverse real-world applications featuring sequential and hierarchical processes, we introduce a nested structure for all supporting tasks. The objective function exclusively accounts for jobs, including total completion time and the weighted and unweighted number of late jobs. By leveraging the optimality properties unique to this structure, we develop efficient polynomial and pseudo-polynomial dynamic programming algorithms to solve single-agent problems in a single-machine setting, including an extension to the case allowing for job rejection. Then we consider two-agent problems with a constrained optimization form. These algorithms are adapted to tackle the additional complexity of the competing interests of two agents. The extension to the proportionate flow-shop problems highlights their inequivalence against counterpart problems in the single-machine setting in the presence of supporting precedence. We show that the problems are significantly more complex than their single-machine counterparts, namely that problems with due-date-based criteria are strongly \(\mathcal{N}\mathcal{P}\) N P -hard.