Scheduling problems over a network of machines

We consider scheduling problems in which jobs must be processed through a (shared) network of machines. The network is given in the form of a graph, the edges of which represent the machines. We are also given a set of jobs, each specified by its processing time and a path in the graph. Every job must be processed in the order of edges specified by its path. We assume that jobs can wait between machines and preemption is not allowed; that is, once a job starts processing on a machine, it must be completed without interruption. Every machine can only process one job at a time. The makespan of a schedule is the earliest time by which all the jobs have finished processing. The completion time of a job in a schedule is defined as the time it finishes processing on its last machine. The total completion time refers to the sum of completion times of all the jobs. Our focus is on finding schedules with the minimum sum of completion times or minimum makespan. In this paper, we develop several algorithms (both approximate and exact) for the problem both on general graphs and when the underlying graph of machines is a tree. Even in the very special case when the underlying network is a simple star, the problem is very interesting as it models a biprocessor scheduling with applications to data migration.