Task scheduling with precedence constraints to minimize the total completion time

REFERENCES

• AOOLPHSON , D. , and Hu , T. C. , 1973 , Optimal linear ordering . SIAM Journal on Applied Mathematics , 25 , 403 – 423 .
   Google Scholar
• BLAKE , B. A. , and SCHWAN , K. , 1991 , Experimental evaluation of a real-time scheduler for a multiprocessor system . IEEE Transactions on Software Engineering , 17 , 34 – 44 .
   Google Scholar
• BOKHARI , S. H. , 1981 , A shortest tree algorithm for optimal assignments across space andtime in a distributed processor system . IEEE Transactions on Software Engineering , 7 , 583 – 589 .
   Web of Science ®Google Scholar
• CHANG , J. M. , Hsu , C. C. , and CHEN , A. P. , 1992 , Task scheduling with precedence constraintsto minimize the total completion time . Proceedings of the International ComputerSymposium , pp. 53 – 60 .
   Google Scholar
• CONWAY , R. W. , MAXWELL , W. L. , and MILLER , L. W. , 1967 , Theory of Scheduling ( Reading , Mass . Addison-Wesley ).
   Google Scholar
• GAREY , M. R. , 1973 , Optimal task sequencing with precedence constraints . Discrete Mathematics , 4 , 37 – 56 .
   Google Scholar
• GAREY , M. R. , and JOHNSON , D. S. , 1979 , Computers and Intractability a Guide to the Theoryof NP-Completeness ( San Francisco , Calif. Freeman ).
   Google Scholar
• HORN , W. A. , 1972 , Single machine job sequencing with tree-like precedence ordering andlinear delay penalties . SI AM Journal on Applied Mathematics , 23 , 189 – 202 .
   Web of Science ®Google Scholar
• HOROWITZ , E. , and SAHNI , S. , 1976 , Exact and approximate algorithms for schedulingnon-identical processors . Journal of the Association for Computing Machinery , 23 , 317 – 327 .
   Web of Science ®Google Scholar
• Hsu , C. C. , WANG , S. D. , and Kuo , T. S. , 1989 , Efficient task assignment for distributedcomputing systems . Journal of the Chinese Institute of Engineers , 12 , 317 – 329
   Google Scholar
• LAWLER , E. L. , 1978 , Sequencing jobs to minimize total weighted completion time subject toprecedence constraints . Annals of Discrete Mathematics , 2 , 75 – 90 .
   Google Scholar
• LENSTRA , J. K. , RINNOOY KAN , A. H. G. , and BRUCKER , P. , 1977 , Complexity of machinescheduling constraints . Annals of Discrete Mathematics , 1 , 343 – 362 .
   Google Scholar
• MCNAUGHTON , R. , 1959 , Scheduling with deadlines and loss functions . Management Science , 6 , 1 – 12 .
   Web of Science ®Google Scholar
• NILSON , N. J. , 1980 , Principles of Artificial Intelligence ( Palo Alto , Calif. Tioga ).
   Google Scholar
• RAMAMRITHAM , K. , STANKOVIC , J. A. , and SHIAH , P. F. , 1989 , O(n) scheduling algorithms forreal-time multiprocessor systems . Proceedings of the International Conference onParallel Processing , pp. 143 – 152 .
   Google Scholar
• SETHI , R. , 1977 , On the complexity of mean flow time scheduling . Mathematics of OperationsResearch , 2 , 320 – 330 .
   Google Scholar
• SHEN , C. C. , and TSAI , W. H. , 1985 , A graph matching approach to optimal task assignmentin distributed systems using a minimax criterion . IEEE Transactions on Computers , 34 , 197 – 203 .
   Web of Science ®Google Scholar
• SIDNEY , J. B. , 1975 , Decomposition algorithms for single-machine sequencing with precedencerelations and deferral costs . Operations Research , 23 , 283 – 298 .
   Web of Science ®Google Scholar
• SINCLAIR , J. B. , 1987 , Efficient computation of optimal assignments for distributed tasks . Journal of Parallel and Distributed Computing , 4 , 342 – 362 .
   Web of Science ®Google Scholar
• WANG , L. L. , and TSAI , W. H. , 1988 , Optimal assignment of task modules with precedencefor distributed processing by graph matching and state space search . Behaviour andInformation Technology , 28 , 54 – 68 .
   Google Scholar
• YANG , C. I. , WANG , J. S. , and LEE , R. C. T. , 1989 , A branch-and-bound algorithm to solvethe equal-execution-time job scheduling problem with precedence constraint andprofile . Computers and Operations Research , 16 , 257 – 269 .
   Google Scholar