Scholarlink

<p>The scheduling measure of minimum weighted number of early jobs has hardly been investigated by scheduling researchers. This note focuses on a single machine scheduling and due-date assignment problem with the objective function of minimizing the weighted number of early jobs plus total weighted tardiness (given a common due-date for all jobs). The problem is proved to be NP-hard, and based on a number of properties of an optimal schedule, a pseudo-polynomial dynamic programming algorithm is introduced. Based on our numerical tests, the proposed algorithm is efficient and practical: medium size problems (of up to 150 jobs) are solved in very reasonable running times.</p>

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

Single machine scheduling to minimize weighted number of early jobs plus total weighted tardiness

  • 期刊论文

  • 发表日期：

    2025年9月16日

查看全文
  • Matan Atsmony,
  • Gur Mosheiov

摘要

The scheduling measure of minimum weighted number of early jobs has hardly been investigated by scheduling researchers. This note focuses on a single machine scheduling and due-date assignment problem with the objective function of minimizing the weighted number of early jobs plus total weighted tardiness (given a common due-date for all jobs). The problem is proved to be NP-hard, and based on a number of properties of an optimal schedule, a pseudo-polynomial dynamic programming algorithm is introduced. Based on our numerical tests, the proposed algorithm is efficient and practical: medium size problems (of up to 150 jobs) are solved in very reasonable running times.