Graph balancing: a special case of scheduling unrelated parallel machines

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F14%3A00424769" target="_blank" >RIV/67985840:_____/14:00424769 - isvavai.cz</a>
Alternative codes found
RIV/00216208:11320/14:10286411
Result on the web
<a href="http://dx.doi.org/10.1007/s00453-012-9668-9" target="_blank" >http://dx.doi.org/10.1007/s00453-012-9668-9</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00453-012-9668-9" target="_blank" >10.1007/s00453-012-9668-9</a>

Result language
angličtina
Original language name
Graph balancing: a special case of scheduling unrelated parallel machines
Original language description
We design a 1.75-approximation algorithm for a special case of scheduling parallel machines to minimize the makespan, namely the case where each job can be assigned to at most two machines, with the same processing time on either machine. (This is a special case of so-called restricted assignment, where the set of eligible machines can be arbitrary for each job.) This is the first improvement of the approximation ratio 2 of Lenstra, Shmoys, and Tardos (Math. Program. 46:259?271, 1990), to a smaller constant for any special case with unbounded number of machines and unbounded processing times. We conclude by showing integrality gaps of several relaxations of related problems.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2014
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)