| ¡¡ | Chinese Journal of Computers Full Text |
| Title | An Optimal Algorithm for Normal Scheduling on P4£üfix£üCmax |
| Authors | HUANG Jin-Gui LI Rong-Heng |
| Address | (Department of Computer Education, Hunan Normal University, Changsha 410081) |
| Year | 2009 |
| Issue | No.8(1631¡ª1636) |
| Abstract & Background | Abstract With the advanced of the heterogeneous parallel computing technology, Multiprocessor-job scheduling problem has attracted much attention recently. Because of complexity of the general multiprocessor system, it is impossibility to find the approximation scheduling algorithm with the ideal performance. The paper is focused on the smaller processors system, that 4-processor system and its scheduling problem P4£üfix£üCmax. With introduced the Normal scheduling, and Group scheduling, a linear time algorithm is developed with the 4/3 approximation ratio. It is proved that normal scheduling come from the algorithm is the optimal normal scheduling in 4-processor systems. Keywords multiprocessor-job scheduling; normal scheduling; approximation algorithm; NP-hard problem Background This paper is a product from the research in the projects supported by the National Natural Science Foundation of China, under grants No.60872039 and No.10771060. The objective of the projects is to study the computational complexity and algorithmic techniques for intractable optimization problems in computer networks and in other applications. The research has achieved significant progress recently. The authors have studied the multiprocessor job scheduling algorithms on distributed network systems. Multiprocessor-job scheduling problem has attracted much attention recently. Because of complexity of the general multiprocessor system,The polynomial time approximation schemes for these problems are of great theoretical significance. However, most of these algorithms are based on extensive enumerations of certain kinds of scheduling together with either dynamic programming or linear programming techniques. This makes this kind of algorithms practically slow and difficult to implement. So researchers have asked for practically efficient and easy-implement able approximation algorithms for the parallel job-scheduling problem for systems with small number of processors. The optimal normal scheduling for 3-processor system is given and it is a 5/4-approximation algorithm for the multiprocessor job scheduling in 3-processor system The paper is focused on the smaller processors system, that 4-processor system and its scheduling problem P4£üfix£üCmax. With introduced the Normal scheduling, and Group scheduling, a linear time algorithm is developed with the 4/3 approximation ratio. It is proved that normal scheduling come from the algorithm is the optimal normal scheduling in 4-processor systems. |