An optimal scheduling policy for fork/join queues

We consider the problem of optimally scheduling an arriving job on a set of homogeneous single-server queues: (i) arriving jobs consist of a random number of tasks which can be executed independently of each other; (ii) a job is completed only after all of its component tasks have finished execution; and (iii) a central dispatcher schedules the tasks on the queues at job arrival instants using information on the number of tasks currently scheduled on each processor. In the case of two queues when task are exponentially distributed, we show that the individually optimal policy is a mixture of policies corresponding to sequential job execution (all tasks are scheduled on a single processor) and parallel scheduling (tasks are distributed among several queues in a manner that tends to equalize queue lengths). Under conditions that include the case of moderate to heavy loads, the individually optimal scheduler is shown to schedule tasks according to the sequential policy. The conclusions obtained in this special case hold generally for an arbitrary number of processors and general task service time distribution