文献类型：期刊文献

英文题名：On some special cases of the restricted assignment problem

作者：Wang, Chao[1];Sitters, Rene[2,3]

机构：[1]East China Univ Sci & Technol, Shanghai 200237, Peoples R China;[2]Vrije Univ Amsterdam, NL-1081 HV Amsterdam, Netherlands;[3]CWI, NL-1098 XG Amsterdam, Netherlands

年份：2016

卷号：116

期号：11

起止页码：723

外文期刊名：INFORMATION PROCESSING LETTERS

收录：;EI(收录号：20164102891381);WOS:【SCI-EXPANDED(收录号:WOS:000381590000012)】；

基金：This research done while visiting the VU University Amsterdam and was supported in part by the China Scholarship Council under grant No. 201306740038.

语种：英文

外文关键词：Scheduling; Restricted assignment problem; Design of algorithms

摘要：We consider some special cases of the restricted assignment problem. In this scheduling problem on parallel machines, any job j can only be assigned to one of the machines in its given subset M-j of machines. We give an LP-formulation for the problem with two job sizes and show that it has an integral optimal solution. We also present a PTAS for the case that the M-j's are intervals of the same length. Further, we give a new and very simple algorithm for the case that vertical bar M-j vertical bar = 2 (known as the graph balancing problem) with ratio 11/6. (C) 2016 Elsevier B.V. All rights reserved.