# Feasible task schedules with minimum project cost solved by a genetic algorithm michael L. Gargano

Скачать 142.94 Kb.
 Название Feasible task schedules with minimum project cost solved by a genetic algorithm michael L. Gargano Дата 07.10.2012 Размер 142.94 Kb. Тип Документы

## FEASIBLE TASK SCHEDULES WITH

MINIMUM PROJECT COST

SOLVED BY A GENETIC ALGORITHM

## Michael L. Gargano

Louis V. Quintas

Pace University

New York, NY 10038

THE PROBLEM

Suppose that a project consists of n separate tasks and one and only one task can be completed in one time period.

However, since some tasks can be started only before others have been completed only feasible task schedules are considered. There is a cost associated with the time at which a task is completed and the project cost is equal to the sum of all the task costs.

How can a feasible task schedule with minimum project cost be found for completing the entire project? This research proposes using a genetic algorithm to efficiently solve this problem.

An example 6 7

5

3 4

1 2

Diagram showing the constraints on the order in which 7 tasks can be done.

The matrix below is another representation for this diagram. The entry in the ith row and jth column is 1 if task i is connected to task j and task j is in a higher position on the diagram, that is i must be completed before j, else the entry is 0.

 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

The cost of completing task i at time t is given by the following.
 Time 1 2 3 4 5 6 7 task 1 2 3 3 3 4 4 5 task 2 2 4 2 8 8 6 6 task 3 1 1 2 2 3 3 3 task 4 2 1 1 3 4 5 6 task 5 5 5 4 4 4 3 3 task 6 4 4 4 4 4 4 4 task 7 2 3 2 3 2 3 2

Cost of doing task i at time t.

------------------------------------------------------------------------------------

 Feasible Schedule Ordered List of Tasks Project Cost 1 1 2 3 4 5 6 7 21 2 1 2 3 4 5 7 6 22 3 1 2 4 3 5 6 7 19 4 1 2 4 3 5 7 6 20 5 1 3 2 4 5 6 7 18 6 1 3 2 4 5 7 6 19 7 2 1 3 4 5 6 7 20 8 2 1 3 4 5 7 6 21 9 2 1 4 3 5 6 7 18 10 2 1 4 3 5 7 6 19

All possible feasible schedules and the resulting project cost.

6 7

5

3 4

1 2
 Time 1 2 3 4 5 6 7 task 1 2 3 3 3 4 4 5 task 2 2 4 2 8 8 6 6 task 3 1 1 2 2 3 3 3 task 4 2 1 1 3 4 5 6 task 5 5 5 4 4 4 3 3 task 6 4 4 4 4 4 4 4 task 7 2 3 2 3 2 3 2

Cost of doing

task i at time t.

 Feasible Schedule Ordered List of Tasks Project Cost 1 1 2 3 4 5 6 7 21 2 1 2 3 4 5 7 6 22 3 1 2 4 3 5 6 7 19 4 1 2 4 3 5 7 6 20 5 1 3 2 4 5 6 7 18 6 1 3 2 4 5 7 6 19 7 2 1 3 4 5 6 7 20 8 2 1 3 4 5 7 6 21 9 2 1 4 3 5 6 7 18 10 2 1 4 3 5 7 6 19

All possible feasible schedules and the resulting project cost.

Theorem A partial order on a finite non-empty set T has a minimal element t and the relation restricted to T – { t } is also a partial order.

Topological Sort Algorithm

Input( T and a partial order on T )

p = 1

while T is non-empty

tp = a minimal element in T (if there is a

choice choose randomly)

T = T – { tp }

p = p + 1

Output( a feasible schedule ti1, ti2, ti3,…, tin,

i.e., a feasible permutation of t1, t2, t3,…, tn )

The Genetic Algorithm

1. Randomly initialize a population of potential solutions.

1. Calculate the fitness of any population member not yet evaluated.

1. Sort the members of the population in order of fitness.

1. Randomly select parents for mating, generate offspring using crossover at random positions and evaluate offspring.

1. Randomly select and clone members of the population, generate mutations by changing them in random positions and evaluate mutants.

1. Sort all the members of the expanded population in order of fitness.

1. Use the grim reaper to eliminate the population members with poor fitness.

1. If (termination criteria is met)

then return best population member(s)

else go to step 4.

Theorem

If P1 = ti1, ti2, ti3, ti4,… ti k, ti k+1,…, ti n-2, ti n-1, ti n

and P2 = tj1, tj2, tj3, tj4,… tj k, tj k+1,…, tj n-2, tj n-1, tj n

are partial orders on a finite non-empty set T (i.e., the parents),

then the children (offspring)

C1 = ti1, ti2, ti3, ti4,… ti k, tj k+1*,…, tj n-2*, tj n-1*, tj n*

with { tj k+1*,…, tj n-2*, tj n-1*, tj n* } = T – { ti1, ti2, ti3, ti4,… ti k }

and tj k+1*,…, tj n-2*, tj n-1*, tj n* having its ordering the same as in P2

and

C2 = ti1*, ti2*, ti3*, ti4*,… ti k*, tj k+1,…, tj n-2, tj n-1, tj n

with { ti1*, ti2*, ti3*, ti4*,… ti k* } = T – { tj k+1,…, tj n-2, tj n-1, tj n } and ti1*, ti2*, ti3*, ti4*,… ti k* having its ordering the same as in P1

are also partial orders on the finite non-empty set T.

In this example the population of potential solutions are simply feasible task schedules (i.e., ordered lists of tasks that satisfy the diagram below ).

Two potential solutions are

1 2 3 4 5 6 7 8 9 10 11 12 and 3 1 7 2 4 6 5 8 10 9 12 11

10 11 12

9

8

5 6 7

4

1 2 3

Constraints on the order in which tasks can be done.

Initial Population

The GA population will consist of N randomly generated feasible task schedules. The initial population (i.e., generation 0) is created by executing the topological sort algorithm N times. Since the topological sort algorithm will randomly choose the next minimal element, many different feasible task schedules will be created.

Mating and Mutating

Selecting parents for mating involves randomly choosing one of the fitter members of the population (i.e., one with a small project cost) and the other member randomly. The reproductive process is a simple crossover operation whereby two randomly selected parents are cut into two sections at some randomly chosen position k and then, as described in the following theorem, have the parts of their task schedules swapped to create two new offspring (children).

Here is an illustration of mating based on Figure 3.

If k = 6 and P1 = 1 2 3 4 5 6 7 8 9 10 11 12 and

P2 = 3 1 7 2 4 6 5 8 10 9 12 11

then C1 = 1 2 3 4 5 6 7 8 10 9 12 11

C2 = 1 2 3 4 6 7 5 8 10 9 12 11.

Notice that the first 6 = k positions of C1 are the same as P1 while the last 6 = n – k reflect the order of 7 8 9 10 11 12 as seen in P2, that is, 7 8 10 9 12 11 and similarly note that the last 6 = n – k positions of C2 are the same as P2 while the first 6 = k reflect the order of 3 1 7 2 4 6 as seen in P1, that is, 1 2 3 4 6 7.

In a similar manner an illustration of mutation based on Figure 3 can be shown.

Starting with P = 2 1 4 5 6 8 11 3 7 10 9 12

then M = 2 1 4 6 5 8 11 3 7 10 9 12

with k = 7 is obtained by cloning the last 5 = n – k positions of P and executing a topological sort on the partial order restricted to the tasks numbered 2 1 4 5 6 8 11 (e.g., one such topological sort may be 2 1 4 6 5 8 11) and finally placing the result in the first k = 7 positions of M.

## Fitness

There is a cost associated with the time at which each task is completed (i.e., C (task, time)) defined by a cost table. The fitness associated with a potential solution (i.e., ordered list of tasks (feasible schedule)) is simply the sum of the costs of completing each task in its time period.

If there are n tasks t1, t2, t3,…, tn and if ti1, ti2, ti3,…, tin is a feasible schedule (i.e., a permutation of the tasks that forms a feasible schedule) then task tij is completed in time period j with associated cost C (tij, j). The fitness of this feasible task schedule is given by

Fitness (ti1, ti2,…, tin) = Σ C (tij, j) summed over all tasks

= project cost for ti1, ti2,…, tin .

## The Grim Reaper

After creating a number of children and mutants, the population will grow from its initial size N to N + E. The grim reaper reduces the enlarged population back down to N by eliminating the population members with poorest fitness.

## CONCLUDING REMARKS

For an arbitrary project with a large number of tasks finding a minimum cost task schedule is a difficult problem and solving it by brute force methods is computationally prohibitive. Thus, it is proposed that using a genetic algorithm approach to solve this problem can be a very effective method for obtaining optimal/near optimal solutions efficiently.

## ACKNOWLEDGEMENTS

We wish to thank Pace University’s Seidenberg School of Computer Science and Information Systems for partially supporting this research.

## REFERENCES

Davis, L. (1991) Handbook of Genetic Algorithms, Van Nostrand Reinhold.

Edelson, W. and M.L. Gargano (1998) Minimal Edge-Ordered Spanning Trees Solved By a Genetic Algorithm with Feasible Search Space, Congressus Numerantium 135, 37-45.

Gargano, M.L., W. Edelson, (2001) Optimally Sequenced Matroid Bases Solved By A Genetic Algorithm with Feasible Search Space Including a Variety of Applications, Congressus Numerantium 150, 5-14.

Gargano, M.L., Maheswara Prasad Kasinadhuni, (2004) Self-adaption in Genetic Algorithms using Multiple Genomic Redundant Representations, Congressus Numerantium 167, 183-192.

Goldberg, D.E. (1989) Genetic Algorithms in Search, Optimization, and Machine Learning, Addison Wesley.

Mitchell, M. (2001) An Introduction to Genetic Algorithms, MIT Press.

Rosen, K.H. (1998) Discrete Mathematics and Its Applications, 4th Ed, Random House.

## Похожие:

Разместите кнопку на своём сайте:
Библиотека

База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека