Solving multiple processor and multiple resource constrained scheduling problems using a genetic algorithm approach

Abstract

We consider the multiprocessor scheduling of unit time tasks with precedence constraints and finite set of limited resources. Each task demands some amount of resources for its execution and the total demand for each kind of resources must not exceed a certain limit at any instant of time. Our objective is to find out the minimum time schedule which satisfies the partial orders and the resource usage constraints. We have applied Genetic Algorithm for the present problem. We have shown that the Genetic Algorithm is quite superior to the First Fit Decreasing method.

Keywords:

• Genetic Algorithm
• scheduling
• multiprocessor
• resource
• NP-complete
• precedence constraints
• DAG
• Bin Packing

C.R. Categories:

• I.2.8
• F.2.2
• C.1.2