Scheduling a single machine with parallel batching to minimize makespan and total rejection cost

详细信息    查看全文

• 作者：Cheng He^a ; ^{hech202@163.com" class="auth_mail" title="E-mail the corresponding author} ; Joseph Y.-T. Leung^b ; ^{joseph.y.leung@njit.edu" class="auth_mail" title="E-mail the corresponding author} ; Kangbok Lee^c ; ^{klee5@york.cuny.edu" class="auth_mail" title="E-mail the corresponding author} ; Michael L. Pinedo^d ; ^{mpinedo@stern.nyu.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Batching machine scheduling ; Rejection ; Makespan ; Dynamic programming ; FPTAS ; Approximation algorithms
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：11 May 2016
• 年：2016
• 卷：204
• 期：Complete
• 页码：150-163
• 全文大小：413 K

文摘

We consider the problem of scheduling a set of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005089&_mathId=si1.gif&_user=111111111&_pii=S0166218X15005089&_rdoc=1&_issn=0166218X&md5=88d44bd9b9f7be443caedc9ea6d5a2de" title="Click to view the MathML source">nclass="mathContainer hidden">class="mathCode">$n$ jobs on a single machine with parallel batching and with rejection being allowed. Two bi-criteria problems are considered: (a) minimize the makespan subject to the constraint that the total rejection cost does not exceed a given threshold, and (b) minimize the total rejection cost subject to the constraint that the makespan does not exceed a given threshold. For the case of a batching machine with infinite capacity (i.e., the batch size allowed on the machine is larger than or equal to the number of jobs), we assume that the jobs have release dates. We present an class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005089&_mathId=si2.gif&_user=111111111&_pii=S0166218X15005089&_rdoc=1&_issn=0166218X&md5=bc45b46dbb50661facc901c6d3152600" title="Click to view the MathML source">O(n²)class="mathContainer hidden">class="mathCode">$O\left(n^2\right)$-time 2-approximation algorithm for problem (a) and, in addition, we present dynamic programming algorithms and fully polynomial-time approximation schemes for both problems (a) and (b). For the case of a batching machine with finite capacity (i.e., the batch size allowed on the machine is less than the number of jobs), we assume that the jobs have identical release dates. We propose approximation algorithms for (a) and present dynamic programming algorithms and fully polynomial-time approximation schemes for both problems (a) and (b).