The Linear Switching State Space: A New Modeling Paradigm for Task Scheduling Problems
Subject Areas : Information Technology in Engineering Design (ITED) Journal
Keywords:
Abstract :
AbstractTask Scheduling (TS) poses a challenging problem in distributed systems from multiple perspectivessuch as the uncertainty in resource capacity and topology, heterogeneity of processors, computationalcomplexity as well as theoretical performance analysis. To reach timely solutions, currentapproaches, whether classic approaches, which are based on list scheduling, or intelligentapproaches, which are generally based on evolutionary algorithms, either impose extra constraints orignore some aspects of the reality of this problem. Furthermore, they generally depend on numericalperformance evaluation and lack the ability to reach clear theoretical conclusions. Here, we addressthe problem of theoretical analysis by proposing a new paradigm based on system engineering. Thisnew modeling paradigm is promising due to its extensive theoretical developments. In its generalform, TS is inherently nonlinear because of its many nonlinear constraints. In this paper, wedemonstrate how TS can be mapped via nonlinear state space and, through theoretical analysis, showstability of the resulting system. Then, a suitable transformation is devised to convert this model tolinear switching state space with some nonlinear constraints. It is shown that the resulting model cansuitably represent uncertainty in resource capacity. We then present a systematic method todetermine control vectors based on this model. Finally, the proposed method is compared againstHEFT (heterogeneous earliest finish time) scheme on several random experiments and demonstratecomparative performance.
1. A.J. Page, T.J. Naughton, ”Dynamic task scheduling using genetic algorithms for heterogeneous distributed computing,” in: Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium, IEEE Computer Society, Washington, DC, USA, 2005, p. 189.1. 2. Y.K. Kwok and I. Ahmad, “Dynamic Critical-Path Scheduling: An Effective Technique for Allocating Task Graphs to Multiprocessors,” IEEE Trans. Parallel and Distributed Systems, vol. 7, no. 5, 1996, pp. 506-521. 3. H. Topcuoglu, et al., “Performance-effective and low-complexity task scheduling for heterogeneous computing,” IEEE Trans. Parallel and Distributed Systems, vol. 13, no. 3, 2002, pp. 260-274. 4. A. Rowhanimanesh, A. Karimpour, N. Pariz, “Optimal Path Planning for Controllability of Switched Linear Systems using Multi-Level Constrained GA”, Applications ofSoft Computing: From Theory to Praxis, Springer, Series: Advances in Intelligent and Soft Computing, Volume 58/2009, Pages: 399-408. 5. Z. Sun, S.S. Ge, “Switched Linear Systems: Control and Design (Communications and Control Engineering“), Springer, 2005. ی ـ مهندس در طراحـی ات ـ اوری اطلاع ـ ه فن ـ مجل 24 6. O. Sinnen, Task scheduling for parallel systems, JohnWiley & Sons-Interscience, 2007. 7. O. Sinnen, et al., “Toward a realistic task scheduling model,” IEEE Trans. Parallel and Distributed Systems, vol. 17, no. 3, 2006, pp. 263-275. 8. M. Yoo and M. Gen, “Scheduling algorithm for real-time tasks using multiobjective hybrid genetic algorithm in heterogeneous multiprocessors system,” Computers & Operations Research, vol. 34, 2007, pp. 3084 – 3098. 9. S.-C. Cheng, et al., “Dynamic hard-real-time scheduling using genetic algorithm for multiprocessor task with resource and timing constraints,” Expert Systems with Applications, vol. 36, no. 1, 2009, pp. 852–860. 10. M. Yoo, “Real-time task scheduling by multiobjective genetic algorithm,” Systems and Software, vol. 82, no. 4, 2009, pp. 619-628. 11. K. Shin, et al., “Task scheduling algorithm using minimized duplications in homogeneous systems,” Parallel and Distributed Computing, vol. 68, 2008, pp. 1146–1156. 12.X. Kong, et al., “Permutation-based Particle Swarm Algorithm for Tasks Scheduling in Heterogeneous systems with Communication Delays,” Computational Intelligence Research, vol. 4, no. 1, 2008, pp. 61–70. 13.I.-H. Kuo, et al., “An efficient flow-shop scheduling algorithm based on a hybrid particle swarm optimization model,” Expert Systems with Applications, 2008. 14.H.-S. Choi and D.-H. Lee, “Scheduling algorithms to minimize the number of tardy jobs in twostage hybrid flow shops,” Computers & Industrial Engineering, 2008. 15.R. Hwang, et al., “A comparison of multiprocessor task scheduling algorithms with communication costs,” Computers & Operations Research, vol. 35, 2008, pp. 976 – 993. 16.K. Ogata, Discrete-Time Control Systems, Prentice Hall, 1995. 17.C.-T. Chen, Linear System Theory and Design, Oxford University Press, USA, 1995. 18.H. Ozbay, Introduction to feedback control theory. CRC Press-Technology & Engineering, 1999. 19.S. Al-Sharaeh and B.E. Wells, “A Comparison of Heuristics for List Schedules using The Boxmethod and P-method for Random Digraph Generation,” Proc. of the 28th Southeastern Symposium on System Theory, 1996, pp. 467–471. 20.L.G. Q., et al., “Iterative list scheduling for heterogeneous computing,” Parallel and Distributed Computing, vol. 65, no. 5, 2005, pp. 654–665.
_||_