A POLYNOMIAL TIME FEASIBILTY CONDITION FOR STATE DEPENDANT MULTIPROCESSOR SCHEDULING

Dr. Natasha Neogi
Assistant Professor
Department of Aerospace Engineering (Affiliate Professor, Computer Science) University of Illinois, Urbana-Champaign

Abstract. A difficulty encountered in many real-time scheduling applications involves the dependence of task duration on the execution order of the tasks. This implies that the execution time of the task is dependent on the characteristics of its predecessor. Attempting to find a valid schedule for a generic set of tasks even for a single processor, is intractable, as the problem is exponential in the number of tasks.

Furthermore, the general problem of multiprocessor scheduling, is, of course, NP-complete. In a multiprocessor environment, with unrelated processors, the question becomes: Given a set A of a_i tasks, where i = 1 · · · p, that must be scheduled over m processors, is it possible to schedule the tasks on the processors such that each task adheres to its deadline, and the makespan of the processor that terminates last is guaranteed to terminate before a deadline D? If we consider a class partition of the tasks, that is, we create an abstraction that limits the values the execution times a task can take, and then draw the processor speeds from an exponential distribution, the problem is rendered more tractable. In this paper, we examine first the static problem, where a predetermined set of tasks is given, and then modify this approach to encompass a dynamic environment, where tasks arrive throughout the execution timespan. A feasibility algorithm for the class-restricted version of the problem which has computational complexity of O(p2(q-1)log2m) is developed, where q is the number of classes, and each processor