Scholarlink

<p>This research introduces pseudo-polynomial optimal algorithms for various variants of the problem aimed at minimizing both weighted and unweighted total earliness and tardiness for a given set of jobs with a common, non-restrictive due date and optional job rejection. In this context, each job is associated with a rejection cost, allowing for the possibility of rejecting a subset of the jobs. The variants we consider in this paper include non-restricted rejection, an upper bound on the total rejection cost, an upper bound on the total scheduling cost, and a Pareto-optimal solution. Several key innovations are presented: the integration of optional job rejection, the nontrivial adaptation to the environment of multiple machines, the provision of efficient algorithms for both weighted and unweighted scenarios, and the introduction of Pareto-optimal scheduling. These advancements make the proposed algorithms highly applicable to real-world production systems while maintaining pseudo-polynomial complexity, providing both theoretical depth and practical utility.</p>

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

Minimizing the total weighted earliness-tardiness about a non-restrictive common due date with optional job rejection on single and multiple machines

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年1月24日

查看全文
  • Baruch Mor,
  • Dana Shapira,
  • Nir Sonn

摘要

This research introduces pseudo-polynomial optimal algorithms for various variants of the problem aimed at minimizing both weighted and unweighted total earliness and tardiness for a given set of jobs with a common, non-restrictive due date and optional job rejection. In this context, each job is associated with a rejection cost, allowing for the possibility of rejecting a subset of the jobs. The variants we consider in this paper include non-restricted rejection, an upper bound on the total rejection cost, an upper bound on the total scheduling cost, and a Pareto-optimal solution. Several key innovations are presented: the integration of optional job rejection, the nontrivial adaptation to the environment of multiple machines, the provision of efficient algorithms for both weighted and unweighted scenarios, and the introduction of Pareto-optimal scheduling. These advancements make the proposed algorithms highly applicable to real-world production systems while maintaining pseudo-polynomial complexity, providing both theoretical depth and practical utility.