In network scheduling a set of jobs must be scheduled on
unrelated parallel processors or machines which are
connected by a network. Initially, each job is located
on some machine in the network and cannot be started on
another machine until sufficient time elapses to allow
the job to be transmitted there. This setting has
applications, e.g., in distributed multi-processor
computing environments and also in operations research;
it can be modeled by a standard parallel machine
environment with machine-dependent release dates. We
consider the objective of minimizing the total weighted
completion time.
The main contribution of this paper is a provably good
convex quadratic programming relaxation of strongly
polynomial size for this problem. Until now, only linear
programming relaxations in time- or interval-indexed
variables have been studied. Those LP relaxations,
however, suffer from a huge number of variables. In
particular, the best previously known relaxation is of
exponential size and can therefore not be solved exactly
in polynomial time. As a result of the convex quadratic
programming approach we can give a very simple and easy
to analyze randomized 2-approximation algorithm which
slightly improves upon the best previously known
approximation result. Furthermore, we consider
preemptive variants of network scheduling and derive
approximation results and results on the power of
preemption which improve upon the best previously known
results for these settings.
