About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Mathematical and Computer Modelling
Paper
Scheduling parallel processors: Structural properties and optimal policies
Abstract
Consider a set of parallel processors operating in a distributed fashion, which prohibits task migration among processors. A given set of jobs, 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 properties are all rooted in the subadditivity, submodularity, convexity, and Schur convexity of two operators, max and plus, which relate task times to the flow time (expected job completion time). We show that in general the optimal policy has a threshold structure and a sequential 'tail': there exists a threshold, such that once the number of jobs already scheduled exceeds this threshold, all remaining 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. 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.