Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines
We consider the problem of scheduling n identical jobs on 3 uniform machines with speeds s1, s2, and s3 to minimize the schedule length. We assume that jobs are subject to some kind of mutual exclusion constraints, modeled by a cubic incompatibility graph. We how that if the graph is 2-chromatic then the problem can be solved in O(n^2) time. If the graph is 3-chromatic, the problem becomes NP-hard even if s1>s2=s3.
Hanna Furmańczyk, Marek Kubale. (2018). Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines, 234, 210-217. https://doi.org/10.1016/j.dam.2016.01.036
wyświetlono 14 razy