A new polynomial algorithm for a paralle identical scheduling problem

A precedence order is defined based on the release dates of jobs’ direct successors. Using the defined precedence order and Heap Sort, a new polynomial algorithm is provided which aims to solve the parallel scheduling problem P|p _j = 1, r _j , outtree| Σ C _j . The new algorithm is shown to be more compact and easier to implement. This work was supported by the National Natural Science Foundation of China (No. 60474023), Science and Technology Key Project Fund of the Ministry of Education(No. 03184), and the Major State Basic Research Development Program of China (No. 2002CB312200). Yumei LI was born in 1976. She is a teacher at Beijing Technology and Business University. Her current research interest includes algorithm design, algorithm complexity analysis and algorithm optimization for scheduling problems, fuzzy relational equations. Hongxing LI was born in 1953. He is a professor at Beijing Normal University. His current research interest and projects include fuzzy logic systems, fuzzy control theory, neural networks, fuzzy-neural systems, neurofuzzy systems, Bioinformatics, and mathematical theory of knowledge representation. Vincent C. YEN is a professor at Wright State University(USA). His current research interest includes information systems, intelligent systems, CIMS, business workflow process modelling, Petri nets, Metagraph etc.