A Sort Of Scheduling Problem With Pseudo-threads In A Communication Model

In this paper, we discussed a kind of scheduling problem with delivery times between tasks whose precedence constraints are formed to a k - level - outtree. We assume that delivery time equals to zero if two tasks (father and sucessor) incident to a directed edge are scheduled to the same machine to process, or we process the sucessor of this two tasks in accordance with their factal delivery time. At the same time, we assume that those tasks are processed according to the level, that a machine processing a task is not preemptive and processes at most a task at a time, that the system does not include communication times in the course of processing. This method breaked three restraints of original model: the first is that the number of machines is numberless, the second is that precedence constraints between tasks is a 1 - level - outtree, the third is that the system includes communication times. So that we abstracted a general scheduling problem ofP_m | pseudo - delivery times, k- level -outtree|C_max. We analysed the complexityof this problem, and give a heuristic algorithm, At last we analysed the algorithm's optimal performance, time complexity and probability capacity. The result shows that the given algorithm works well.