Convex Quadratic and Semidefinite Programming Relaxations in Scheduling I: Randomized Rounding of the Convex Quadratic Relaxation (CQP′) Is Within 3/2 for R | | Σ wⱼCⱼResearch Paper
Scheduling jobs on unrelated parallel machines to minimize the total weighted completion time, the problem written in the three-field notation, is one of the basic NP-hard models of machine scheduling. Each job may take a different time on each machine, as when heterogeneous processors, plants or crews serve the same pool of tasks, and…