<p>This research investigates the bounded batch online-scheduling issue, specifically focusing on incompatible job families assigned to unit flowshop machines. The main criterion is to reduce the makespan. Within a unit flowshop setting, each machine standardizes the processing time of a job to one unit. The concept of linear lookahead pertains to an online algorithm’s ability to anticipate job information within the time interval <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\((t, \lambda t +\beta ]\)</EquationSource> </InlineEquation> at time <i>t</i>. The bound batch capacity, denoted by <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(b &lt; \infty\)</EquationSource> </InlineEquation>, signifies a restriction on the number of jobs that can be contained within a batch. For two unit machines, we introduce the optimal online algorithm <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(A^{b}\)</EquationSource> </InlineEquation>. In instances where multiple unit machines are employed with parameters <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\lambda \ge 1\)</EquationSource> </InlineEquation>, <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(0 \le \beta &lt; 1\)</EquationSource> </InlineEquation>, and <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(f \ge 2\)</EquationSource> </InlineEquation>, we establish a competitive ratio bounded by at most <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(1 + \max \left\{ {\frac{f}{{(2f - 1)(1 + \alpha )}},\frac{f}{{\lambda (2f - 1)\alpha + \beta + f}}} \right\}\)</EquationSource> </InlineEquation> based on the online algorithm <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(A_{f}^{b}\)</EquationSource> </InlineEquation>. Specifically, we present an optimal online algorithm when <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(\lambda =1\)</EquationSource> </InlineEquation> and <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(0 \le \beta \le \displaystyle \frac{3f + 1-\sqrt{9 f^{2}-2f +1}}{4}\)</EquationSource> </InlineEquation>. Additionally, we extend our findings to the bounded batch scheduling problem incorporating a linear lookahead interval and <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(f (=m)\)</EquationSource> </InlineEquation> incompatible job families on multiple unit machines.</p>

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

The online-scheduling problems with the bounded batch and incompatible job families on the unit flowshop machines

  • Xin-Gong Zhang,
  • Jingyi Zhang,
  • Yu-Hsiang Chung,
  • Win-Chin Lin,
  • Chin-Chia Wu

摘要

This research investigates the bounded batch online-scheduling issue, specifically focusing on incompatible job families assigned to unit flowshop machines. The main criterion is to reduce the makespan. Within a unit flowshop setting, each machine standardizes the processing time of a job to one unit. The concept of linear lookahead pertains to an online algorithm’s ability to anticipate job information within the time interval \((t, \lambda t +\beta ]\) at time t. The bound batch capacity, denoted by \(b < \infty\) , signifies a restriction on the number of jobs that can be contained within a batch. For two unit machines, we introduce the optimal online algorithm \(A^{b}\) . In instances where multiple unit machines are employed with parameters \(\lambda \ge 1\) , \(0 \le \beta < 1\) , and \(f \ge 2\) , we establish a competitive ratio bounded by at most \(1 + \max \left\{ {\frac{f}{{(2f - 1)(1 + \alpha )}},\frac{f}{{\lambda (2f - 1)\alpha + \beta + f}}} \right\}\) based on the online algorithm \(A_{f}^{b}\) . Specifically, we present an optimal online algorithm when \(\lambda =1\) and \(0 \le \beta \le \displaystyle \frac{3f + 1-\sqrt{9 f^{2}-2f +1}}{4}\) . Additionally, we extend our findings to the bounded batch scheduling problem incorporating a linear lookahead interval and \(f (=m)\) incompatible job families on multiple unit machines.