Research On The Multi-tasks Scheduling Problem

The thesis is for multitasks static scheduling problem in distributed environments. Efficient algorithms for it will have both highly theoretical and highly practical value. It is strong NP-complete, which is the hardest among the NP-difficult problems. It has been deeply studied by worldwide researchers for decades. And many schedule models and algorithms were proposed for it.Directed acyclic graph (DAG) is normally used for modelling a set of tasks with precedence relations. But there is only existent definition for DAG reported. In the thesis, two constructible definitions for DAG are put forward to make it intuitive and operable.The constraints are summed up to three: task constraint, link constraint and resource constraint. Then a unified and integrated description and a formalized definition are proposed for the multi-tasks static scheduling problem in distributed environments. It is proved that the problem is computable and strong NP-complete, and there is no approximate algorithms that have constant polynomial time approximate ratio.Following the way from simple to complex, the problem of static scheduling multitasks in homogeneous environments is deeply researched. The DAG model is used but the integrated mathematical model hasn't been set up with all constraints and subject in the description reported, especially when task duplication is allowed. And the resource number is unlimited or as a parameter. In the thesis, the constraints are summed up to task constraint, link constraint and resource constraint, and the resource number is assumed equal to the task number. Then an integrated description and two kinds of formalized definition are proposed for it. It is proved that if the number of resources given equals to the number of tasks, then the optimal solution could be got for the problem that has unlimited resources. It is proved that the problem is computable through three approaches, which helps people understanding the problem more deeply and is benefit to finding good strategies.The commonly categorized schemes are priority list based, cluster based and task duplication based schemes for the problem. In general, the task-duplication-based (TDB) schemes are observed to be better than other schemes. The rationale behind the TDB scheduling algorithms is to take the strategy of trading the time off the space, and to reduce the communication overhead by redundantly allocating some tasks to multiple resources, and they can take advantage of using more resources to further reduce the schedule length. An accurate determination of important tasks for duplication is the key to obtaining a short schedule, and the main difference in the reported algorithms lies in their strategies to select tasks for duplication. Based on task duplication and clustering technique, two efficient approximation algorithms are proposed.A new heuristic approach for greedy task clustering named the interpersonal relationships evolution algorithm (IREA) is proposed. IREA resembles the evolution of the interpersonal relationships within human society, and includes three components: dynamic-group, detach-graph and cutting-edge. The priority rules used are new, relationship number, potentiality, weight and merge degree are defined for cluster's priority, and task potentiality for tasks'priority. The experimental results are good.Among the TDB algorithms, the PY and MJD algorithms give performance guarantee for arbitrary DAGs while other TDB algorithms just give optimal solutions for certain DAGs. In the thesis, another task-duplication-based clustering and scheduling algorithm, called the dynamic critical predecessor (DCP) algorithm is proposed, which references the theoretic best MJD algorithm and improves on its deficiency. The DCP algorithm defines a new choice strategy for the important ancestor set that should be duplicated. An improved granularity concept is proposed, and DCP exceeds other TDB algorithms in performance for arbitrary and specific DAGs. The experimental results for the DCP algorithm are good too and DCP yields better solutions on several benchmarks.Besides, there is no standard benchmark set for the multi-tasks scheduling problems in homogeneous environments until now. The dispersed benchmarks are gathered and made tidy. The optimal solutions for some benchmarks are discussed and proved, that are benefit for the relative work and the future work.Finally, an applying, the workflow schedule problem in the grid workflow platform, is discussed.