SCHEDULING PARALLEL PROCESSORS - STRUCTURAL-PROPERTIES AND OPTIMAL POLICIES

Consider a set of parallel processors operating in a distributed fashi on, which prohibits task migration among processors. A given set of jo bs, each of which consists of a number of tasks, is to be processed by the parallel processors. Finding an optimal schedule in this context is a difficult combinatorial problem in general. Our focus here is on identifying key properties of the problem so as to provide insight to the structure of optimal policies. We demonstrate that these propertie s are all rooted in the subadditivity, submodularity, convexity, and S chur convexity of two operators, max and plus, which relate task times to the flow time (expected job completion time). We show that in gene ral the optimal policy has a threshold structure and a sequential ''ta il'': there exists a threshold, such that once the number of jobs alre ady scheduled exceeds this threshold, all remaining jobs must be sched uled sequentially, i.e., each job with the entirety of its tasks is as signed to one processor only. In the special case of two processors, w e further develop a recursive algorithm that generates the complete op timal schedule. For the case of three or more processors, we focus on a class of policies that we call ''fully parallel or fully sequential' ' (FPFS), and identify optimal policies within this class.