OPTIMAL TASK-SCHEDULING ON DISTRIBUTED PARALLEL PROCESSORS

We study the optimal scheduling of n jobs, each with a given job dependent number of tasks, on a set of parallel processors, which operate in a distributed fashion (so that task migration is not allowed). The task processing times are independent and identically distributed, and a job is completed only when all of its tasks are completed. The optimal schedule assigns the tasks to the processors so as to minimize the flow time, the sum of the expected completion times of all jobs. While finding such an optimal schedule in general is a difficult combinatorial problem, our focus here is on identifying key structural properties of the optimal schedule, that provides insight and guidelines for task scheduling in parallel processing systems. Specifically, we develop simple, closed-form upper and lower bounds on the optimal flow time, and show that the ratio of the bounds goes to unity as the number of jobs increases. We also show that the optimal schedule has a threshold structure: there exists a threshold n such that once n jobs are scheduled, the remaining n - n jobs must be scheduled sequentially (i.e., each job with the entirety of its tasks is assigned to one processor only). In the special case of two processors, we further develop a recursive algorithm that generates the complete optimal schedule.