Task Scheduling Algorithm On A Shared Resource Competition

In the recent years, computers have been widely used in the traffic control, communication network and other fields. The fundamental theory that can support above supplications is the research on effective and fast algorithms for NP-complete problems relevant to these fields. Furthermore the researching work about the fast algorithms on NP-complete problems becomes a hot research topic in computer science for the time being. In this paper we discuss a fast practical algorithm on scheduling problems with sharing resources.In many systems, the task needs certain resources to be finished. The system will release the resource it occupied after it has been finished. Any two tasks needing the same resources and conflicting each other cant go on at the same time. This is a research category with task scheduling problem of shared resource competition. This kind of scheduling problems has extensive applications on the real world For example, Real-time control systems, the solutions of the competition to the shared resource in parallel and distributed computation of multiprocessor, the software design of communication controls, mobile communication controlling and etc. Which kind of schedule algorithms is adopted will influence system directly in operation performance. So the study on tin's kind of scheduling problem has extensive meanings.In this paper, we propose a task scheduling problem on the model of the limited resources captured in short time, which is about the scheduling in traffic intersection and the philosophers' dinning problem (and we label this kind of problem as DHDD problems). The common object of DHDD problem can be described as follows: let the tasks use resources as many as possible and avoid theoccurrence of deadlock and one philosopher's dying of hungry. In DHDD problems, a task is permitted to share resources with some tasks in the task group, and at the same time, is forbidden to share the resources with some other tasks in the group. Usually a task is composed of several sub-tasks, i.e. a task denotes a task class. With the example of scheduling of traffic intersection, the vehicle set in one direction is a task waiting for being scheduled, and each vehicle is a sub-task. In order to avoid confusion, we named a task in the task set as a sub-task, and call the number of the tasks in the task class as the weight of the task class. The number of task changes over time, so the whole scheduling course is on-line. The article use conflict graphic-G(V,E) showing the mathematics model of the problem. At first, the nodes of G are divided into k separated sets Vi, V2, V3, ..., Vk, we name WT as the maximum length of the time that any task may be required to wait by the system. In one time unit, if the waiting time of any task in the task set is less than WT, then we choose the separated set that has the most sub-tasks. Otherwise we choose the separated set that has the longest waiting time, and arrange all the sub-tasks in the separated set share resources. The key of the algorithm is that if k is the minimum one of the separated set in G, this scheduling problem is equal to the minimize-color problems. This article discussed the problem in three cases. G is a bipartite graph, G is a plain surface graph, and G is a common graph. We give a partition algorithm when G is a common graph. And demonstrated the conclusion that SN=p and SN