Scheduling Problem_with Delivery Times Between Tasks Whose Precedence Constraints Are Formed To An Outtree In A Communication Model

A kind of parallel machine scheduling problem with the pseudo-delivery times among tasks whose precedence constraints are formed to an outtree is discussed.The example which the limit scheduling problem is given by the scheduling problem P_m| pseudo-delivery, outtree|C_max. By restrictions the knapsack problem reduced to limit knapsack problem, By restrictions the knapsack problem reduced to scheduling problems to prove the scheduling problem P_m| pseudo - delivery, outtree |C_max is NP-complete. Then given for all of the complexity of an algorithm, the algorithm complexity is O(n), and given the corresponding proof . And then a heuristic algorithm which the number of job less than a few the number of machines, and proved the optimal performance, and the scheduling complexity is O(n|B| log n)...