The Linear Switching State Space: A New Modeling Paradigm for Task Scheduling Problems

Task Scheduling (TS) poses a challenging problem in distributed systems from multiple perspectives such as the uncertainty in resource capacity and topology, heterogeneity of processors, computational complexity as well as theoretical performance analysis. To reach timely solutions, current approaches, whether classic approaches, which are based on list scheduling, or intelligent approaches, which are generally based on evolutionary algorithms, either impose extra constraints or ignore some aspects of the reality of this problem. Furthermore, they generally depend on numerical performance evaluation and lack the ability to reach clear theoretical conclusions. Here, we address the problem of theoretical analysis by proposing a new paradigm based on system engineering. This new modeling paradigm is promising due to its extensive theoretical developments. In its general form, TS is inherently nonlinear because of its many nonlinear constraints. In this paper, we demonstrate how TS can be mapped via nonlinear state space and, through theoretical analysis, show stability of the resulting system. Then, a suitable transformation is devised to convert this model to linear switching state space with some nonlinear constraints. It is shown that the resulting model can suitably represent uncertainty in resource capacity. We then present a systematic method to determine control vectors based on this model. Finally, the proposed method is compared against HEFT (heterogeneous earliest finish time) scheme on several random experiments and demonstrate comparative performance.