Tham khảo tài liệu 'multiprocessor scheduling part 4', kỹ thuật - công nghệ, cơ khí - chế tạo máy phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 80 Multiprocessor Scheduling Theory and Applications . v A contradiction with x - ----- Thus it exists a schedule of length 6 on an old 9 op 9 op ư tasks. 2. . We suppose that A I 8 x 6 n. So A I 8x 6n because an algorithm A is a polynomial-time approximation algorithm with performance guarantee bound smaller than 9 8. There is no algorithm to decide whether the tasks from an instance I admit a schedule of length equal or less than 6. Indeed if there exists such an algorithm by executing the x tasks at time t 8 we obtain a schedule with a completion time strictly less than 8x 6n there is at least one task which is executed before the time t 6 . This is a contradiction since A I 8x 6n. This concludes the proof of Theorem . Conclusion 3 Thurimella and Yesha 1992 Figure . Principal results in UET-UCT model for the minimization of the length of the schedule With the Figure a question arises It exists a . -approximation algorithm with INT for the problems I -. . . I . . and . . . . . Moreover the hierarchical communication delays model is a model more complex as the homogeneous communication delays model. However this model is not too complex since some analytical results were produced. Scheduling with Communication Delays 81 Appendix In this section we will give some fundamentals results in theory of complexity and approximation with guaranteed performance. A classical method in order to obtain a lower for none approximation algorithm is given by the following results called Impossibility theorem Chrétienne and Picouleau 1995 and gap technic see Aussiello et al. 1999 . Theorem Impossibility theorem Consider a combinatorial optimization problem for which all feasible solutions have non-negative integer objective function value in particular scheduling problem . Let c be a fixed positive integer. Suppose that the problem of deciding if there exists a feasible solution of value at most c is . -complete. Then for any c l c there does not exist a
