Approximation algorithms for the workload partition problem and applications to scheduling with variable processing times
详细信息 查看全文
- 作者：Daniel Oron ; a ; d.oron@econ.usyd.edu.au" class="auth_mail" title="E-mail the corresponding author ; daniel.oron@sydney.edu.au" class="auth_mail" title="E-mail the corresponding author ; Dvir Shabtayb ; dvirs@bgu.ac.il" class="auth_mail" title="E-mail the corresponding author ; George Steinerc ; george.steiner4@gmail.com" class="auth_mail" title="E-mail the corresponding author
- 关键词：Workload partition problem ; Scheduling ; Identical parallel machines ; Controllable processing times ; Approximation algorithms
- 刊名：European Journal of Operational Research
- 出版年：2017
- 出版时间：16 January 2017
- 年：2017
- 卷：256
- 期：2
- 页码：384-391
- 全文大小：474 K
文摘
- class="listitem" id="list_celist0002">
- class="label">•
We prove that the WWP on parallel machines is strongly NP-hard.
- class="label">•
We provide an FPTAS for the case of a fixed number of machines.
- class="label">•
For the general case we develop a constant ratio approximation algorithm.