Convex programming for scheduling unrelated parallel machines

Abstract We consider the classical problem of scheduling parallel unrelated machines. Each job is tobe processed by exactly one machine. Processing job j on machine i requires time pij. The goalis to find a schedule that minimizes the `p norm. Previous work showed a 2-approximation algo-rithm for the problem with respect to the `1 norm. For any fixed `p norm the previously knownapproximation algorithm has a performance of `(p). We provide a 2-approximation algorithmfor any fixed `p norm (p> 1). This algorithm uses convex programming relaxation. We alsogive a p 2-approximation algorithm for the `2 norm. This algorithm relies on convex quadraticprogramming relaxation. To the best of our knowledge, this is the first time that general convex programming techniques (apart from SDPs and CQPs) are used in the area of scheduling. Weshow for any given `p norm a PTAS for any fixed number of machines. We also consider themultidimensional generalization of the problem in which the jobs are d-dimensional. Here thegoal is to minimize the `p norm of the generalized load vector, which is a matrix where the rowsrepresent the machines and the columns represent the jobs dimension. For this problem we give a (d + 1)-approximation algorithm for any fixed `p norm (p> 1). 1 Introduction We consider the classical problem of scheduling jobs on parallel unrelated machines. Lenstra et. al[14] and Shmoys and Tardos [16] provided a 2-approximation algorithm for minimizing the makespan (`1 norm). However, for the `p norm only `(p)-approximation algorithm was known (see [2]). Weprovide a 2-approximation algorithm for any `p norm. In addition we show a p2-approximationalgorithm for th