Approximation of the parallel machine scheduling problem with additional unit resources

详细信息    查看全文

• 作者：Emmanuel Hebrard^a ; ^{hebrard@laas.fr" class="auth_mail" title="E-mail the corresponding author} ; Marie-José ; Huguet^a ; ^{huguet@laas.fr" class="auth_mail" title="E-mail the corresponding author} ; Nicolas Jozefowiez^a ; ^{jozefowiez@laas.fr" class="auth_mail" title="E-mail the corresponding author} ; Adrien Maillard^b ; Cé ; dric Pralet^b ; ^{cedric.pralet@onera.fr" class="auth_mail" title="E-mail the corresponding author} ; Gé ; rard Verfaillie^b
• 关键词：Scheduling ; Approximation ; Additional resources
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：31 December 2016
• 年：2016
• 卷：215
• 期：Complete
• 页码：126-135
• 全文大小：1016 K

文摘

We consider the problem of minimizing the makespan of a schedule on class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303122&_mathId=si32.gif&_user=111111111&_pii=S0166218X16303122&_rdoc=1&_issn=0166218X&md5=99238f0fd48a6189839d35ba064f3a74" title="Click to view the MathML source">mclass="mathContainer hidden">class="mathCode">$m$ parallel machines of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303122&_mathId=si33.gif&_user=111111111&_pii=S0166218X16303122&_rdoc=1&_issn=0166218X&md5=6133b4e3ccee68adf9adfe604357d4a9" title="Click to view the MathML source">nclass="mathContainer hidden">class="mathCode">$n$ jobs, where each job requires exactly one of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303122&_mathId=si34.gif&_user=111111111&_pii=S0166218X16303122&_rdoc=1&_issn=0166218X&md5=a04e6a8848dfb3f02a30d2ba015cbbf0" title="Click to view the MathML source">sclass="mathContainer hidden">class="mathCode">$s$ additional unit resources. This problem collapses to class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303122&_mathId=si35.gif&_user=111111111&_pii=S0166218X16303122&_rdoc=1&_issn=0166218X&md5=32dca696ba0e689738a08fbd90510168">class="imgLazyJSB inlineImage" height="15" width="56" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16303122-si35.gif">class="mathContainer hidden">class="mathCode">$P\parallel C_{\max }$ if every job requires a different resource. It is therefore NP-hard even if we fix the number of machines to class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303122&_mathId=si36.gif&_user=111111111&_pii=S0166218X16303122&_rdoc=1&_issn=0166218X&md5=1243b6971f204c63d5d578328a5ea874" title="Click to view the MathML source">2class="mathContainer hidden">class="mathCode">$2$ and strongly NP-hard in general.

Although very basic, its approximability is not known, and more general cases, such as scheduling with conflicts  , are often not approximable. We give a class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303122&_mathId=si37.gif&_user=111111111&_pii=S0166218X16303122&_rdoc=1&_issn=0166218X&md5=9147743f24db44df2117e31c8e264f78">class="imgLazyJSB inlineImage" height="22" width="68" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16303122-si37.gif">class="mathContainer hidden">class="mathCode">$(2-\frac{2}{m+1})$-approximation algorithm for this problem, and show that when the deviation in jobs processing times is bounded by a ratio class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303122&_mathId=si38.gif&_user=111111111&_pii=S0166218X16303122&_rdoc=1&_issn=0166218X&md5=991dd0a1a6893ad31939456d7854a53d" title="Click to view the MathML source">ρclass="mathContainer hidden">class="mathCode">$\rho$, the same algorithm approximates the problem within a tight factor class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303122&_mathId=si39.gif&_user=111111111&_pii=S0166218X16303122&_rdoc=1&_issn=0166218X&md5=290dcd8b7ed128362d8fc77c1b6dce8c">class="imgLazyJSB inlineImage" height="21" width="74" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16303122-si39.gif">class="mathContainer hidden">class="mathCode">$1+\rho \frac{(m-1)}{n}$.

This problem appears in the design of download plans for Earth observation satellites, when scheduling the transfer of the acquired data to ground stations. Within this context, it may be required to process jobs by batches standing for the set of files related to a single observation. We show that there exists a class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303122&_mathId=si40.gif&_user=111111111&_pii=S0166218X16303122&_rdoc=1&_issn=0166218X&md5=41ed8a04b868b0487f91479dfcb0511b">class="imgLazyJSB inlineImage" height="21" width="53" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16303122-si40.gif">class="mathContainer hidden">class="mathCode">$(2-\frac{1}{m})$-approximation algorithm respecting such batch sequences. Moreover, provided that the ratio class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303122&_mathId=si38.gif&_user=111111111&_pii=S0166218X16303122&_rdoc=1&_issn=0166218X&md5=991dd0a1a6893ad31939456d7854a53d" title="Click to view the MathML source">ρclass="mathContainer hidden">class="mathCode">$\rho$, between maximum and minimum processing times, is bounded by class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303122&_mathId=si42.gif&_user=111111111&_pii=S0166218X16303122&_rdoc=1&_issn=0166218X&md5=fb3d92723f9c4365d80d55da743f673b">class="imgLazyJSB inlineImage" height="21" width="39" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16303122-si42.gif">class="mathContainer hidden">class="mathCode">$\lfloor \frac{s-1}{m-1}\rfloor$, we show that the proposed algorithm approximates the optimal schedule within a factor class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16303122&_mathId=si31.gif&_user=111111111&_pii=S0166218X16303122&_rdoc=1&_issn=0166218X&md5=98e92103c19c063f0c084ff87dadc85e">class="imgLazyJSB inlineImage" height="21" width="51" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0166218X16303122-si31.gif">class="mathContainer hidden">class="mathCode">$1+\frac{s-1}{n}$.