Scholarlink

<p>We consider bicriterion scheduling of equal-length jobs on uniform parallel machines to minimize total tardiness and number of tardy jobs. The Pareto-scheduling problem is studied in this paper, which includes the hierarchical-scheduling problem as a subversion. By using the single-machine scheduling with generated completion times model introduced by Zhao and Yuan (J Comb Optim 39:637–661, <CitationRef CitationID="CR23">2020</CitationRef>), we present an <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(O(n^2)\)</EquationSource> </InlineEquation>-time algorithm to solve the Pareto-scheduling problem, and two <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(O(n\log n)\)</EquationSource> </InlineEquation>-time algorithms to solve two hierarchical-scheduling problems, respectively. Our <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(O(n\log n)\)</EquationSource> </InlineEquation>-time algorithms improve the <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(O(n^2\log n)\)</EquationSource> </InlineEquation>-time algorithms given by Sarin and Prakash (J Comb Optim 8:227–240, <CitationRef CitationID="CR16">2004</CitationRef>) to solve two hierarchical-scheduling problems on identical parallel machines.</p>

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

Bicriterion parallel-machine scheduling of equal-length jobs to minimize total tardiness and number of tardy jobs

  • 期刊论文

  • 发表日期：

    2025年9月26日

查看全文
  • Jing Zhang,
  • Rubing Chen,
  • Jinjiang Yuan,
  • C. T. Ng,
  • T. C. E. Cheng

摘要

We consider bicriterion scheduling of equal-length jobs on uniform parallel machines to minimize total tardiness and number of tardy jobs. The Pareto-scheduling problem is studied in this paper, which includes the hierarchical-scheduling problem as a subversion. By using the single-machine scheduling with generated completion times model introduced by Zhao and Yuan (J Comb Optim 39:637–661, 2020), we present an \(O(n^2)\) -time algorithm to solve the Pareto-scheduling problem, and two \(O(n\log n)\) -time algorithms to solve two hierarchical-scheduling problems, respectively. Our \(O(n\log n)\) -time algorithms improve the \(O(n^2\log n)\) -time algorithms given by Sarin and Prakash (J Comb Optim 8:227–240, 2004) to solve two hierarchical-scheduling problems on identical parallel machines.