Exécution de notre outil de synthèse sur un nouvel article
Vérifiez l’article ci-dessous, puis lancez sa synthèse.
A Unified Rounding Algorithm For Unrelated Machines Scheduling Problems
Nikhil R. Devanur (Microsoft (United States)), Janardhan Kulkarni (Microsoft (United States))
Résumé : The rise of cloud computing platforms has led to the study of many scheduling problems. Towards this, general algorithmic techniques that are applicable to a wide range of problems are highly valuable. We develop one such technique by a temporal generalization of the rounding algorithm of \citetShmoysT93 for the generalized assignment problem. Our algorithm gives a bi-criteria approximation algorithm for a problem we introduce, called the generalized interval scheduling problem, on unrelated machines. The problem allows for each job, a specification of a collection of intervals on each machine, with the constraint that the job must be completely processed in one of the given intervals on a single machine. The assignment costs and the processing lengths are interval dependent. Next we show how to get improved approximation factors for several classical scheduling problems, involving energy, $\ell_p$-norms of completion time, tardiness, and general delay costs by giving a reduction from these problems to the generalized interval scheduling problem with an appropriately defined assignment cost.