Convex Quadratic Programming Relaxations for Network Scheduling Problems
Skutella, Martin
Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
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.
