Practical Multiprocessor Scheduling Algorithms for Efficient Parallel Processing
Hironori Kasahara, Narita · IEEE Transactions on Computers · 1984
This paper describes practical optimization/ approximation algorithms for scheduling a set of partially ordered computational tasks onto a multiprocessor system so that the schedule length will be minimized. Since this problem belongs to the class of ''strong'' NP-hard problems, we must foreclose the possibility of constructing not only pseudopolynomial time optimization algorithms but also fully polynomial time approximation schemes unless P = NP. This paper proposes a heuristic algorithm named CP/MISF (critical path/most immediate successors first) and an optimization/approximation algorithm named DF/IHS (d thfirst/implicit heuristic search). DF/IHS is an excellent scheduling method which can reduce markedly space complexity and average computation time by combining the branch-and-bound method with CP/MISF; it allows us to solve very large scale problems with a few hundred tasks. Numerical examples are included to demonstrate the effectiveness of the proposed algorithms.
Cited by 458 works. doi:10.1109/tc.1984.1676376
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- The Design and Analysis of Computer Algorithms
- Combinatorial optimization: networks and matroids
- Branch-and-Bound Methods: A Survey
- Bounds on Multiprocessing Timing Anomalies
- Computer and job-shop scheduling theory
- Parallel Sequencing and Assembly Line Problems
- Optimal scheduling for two-processor systems
- A comparison of list schedules for parallel processing systems
- Combinatorial Optimization