The Linear Switching State Space: A New Modeling Paradigm for Task Scheduling Problems
Hamid Tabatabaee, Mohammad Reza Akbarzadeh Totonchi · 2013
Task Scheduling (TS) poses a challenging problem in distributed systems for multiple realms such as multiprocessor systems, ow-shop scheduling and project man- agement problems in which there are multiple tasks and processors (resources), and the problem is to efficiently assign tasks to processors. The importance of this problem can be considered from multiple perspectives such as heterogeneity of processors, computational complexity of reaching a solution as well as theoretical performance analysis. Also, we propose a new modeling paradigm based on system engineering. The proposed switching state space approach opens a possibility of using the extensive theoretical developments that have taken place in thiseld within the past several decades. In its general form, TS is inherently nonlinear because of its many nonlinear constraints. In this paper, we demonstrate that standard TS can be mapped via nonlinear state space and, through theoretical analysis, show stability of the resulting system for static task scheduling prob- lems. The proposed static scheduling schedules dependent tasks on a heterogeneous multi- processor system. A suitable transformation is then devised to convert this model to linear switching state space with nonlinear constraints. To illustrate the utility of the model, two scheduling approaches are then presented based on Height Sorted (HS) and Ready Tasks (RT). These two methods are examples that show how this model can be used to reach the stability criteria. Finally, the proposed methods are compared against a conven- tionally accepted scheduling scheme on several random experiments showing comparative performance.