A genetic algorithm for multiprocessor scheduling
E.S.H. Hou, Nirwan Ansari, Hongliang Ren · IEEE Transactions on Parallel and Distributed Systems · 1994
The problem of multiprocessor scheduling can be stated as finding a schedule for a general task graph to be executed on a multiprocessor system so that the schedule length can be minimized. This scheduling problem is known to be NP-hard, and methods based on heuristic search have been proposed to obtain optimal and suboptimal solutions. Genetic algorithms have recently received much attention as a class of robust stochastic search algorithms for various optimization problems. In this paper, an efficient method based on genetic algorithms is developed to solve the multiprocessor scheduling problem. The representation of the search node is based on the order of the tasks being executed in each individual processor. The genetic operator proposed is based on the precedence relations between the tasks in the task graph. Simulation results comparing the proposed genetic algorithm, the list scheduling algorithm, and the optimal schedule using random task graphs, and a robot inverse dynamics computational task graph are presented.>
Cited by 683 works. doi:10.1109/71.265940
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- Genetic algorithms in search, optimization, and machine learning
- Adaptation in Natural and Artificial Systems
- Computer architecture and parallel processing
- A comparison of list schedules for parallel processing systems
- Job Shop Scheduling with Genetic Algorithms
- Optimal Scheduling Strategies in a Multiprocessor System
- Practical Multiprocessor Scheduling Algorithms for Efficient Parallel Processing
- Deterministic Processor Scheduling
- Parallel processing of robot-arm control computation on a multimicroprocessor system