2016-11-01
On some special cases of the restricted assignment problem
Publication
Publication
Information Processing Letters , Volume 116 - Issue 11 p. 723- 728
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 Mj 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 Mj's are intervals of the same length. Further, we give a new and very simple algorithm for the case that |Mj|=2 (known as the graph balancing problem) with ratio 11/6.
| Additional Metadata | |
|---|---|
| doi.org/10.1016/j.ipl.2016.06.007 | |
| Information Processing Letters | |
|
Wang, C. (Chao), & Sitters, R. (2016). On some special cases of the restricted assignment problem. Information Processing Letters, 116(11), 723–728. doi:10.1016/j.ipl.2016.06.007 |
|
