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.

Похожие:

Feasible task schedules with minimum project cost solved by a genetic algorithm michael L. Gargano iconOn a Feasible-Infeasible Two-Population (fi-2Pop) Genetic Algorithm for Constrained Optimization: Distance Tracing and No Free Lunch

Feasible task schedules with minimum project cost solved by a genetic algorithm michael L. Gargano iconOf the genetic algorithm to solution of the optimal sensors location problem

Feasible task schedules with minimum project cost solved by a genetic algorithm michael L. Gargano iconKey Words: Genetic Algorithm, Multiple Crossovers, np problem Introduction

Feasible task schedules with minimum project cost solved by a genetic algorithm michael L. Gargano iconAutomatic Clustering Using a Synergy of Genetic Algorithm and Multi-objective Differential Evolution

Feasible task schedules with minimum project cost solved by a genetic algorithm michael L. Gargano iconA. y ng, Michael Jordan, and Y. Weiss. 2001. On Spectral Clustering: Analysis and an algorithm. In

Feasible task schedules with minimum project cost solved by a genetic algorithm michael L. Gargano iconComplexity, Genetic algorithm, Information criterion of fitness, Sample random generation, Graphical models, Contingency tables. 1 Introduction

Feasible task schedules with minimum project cost solved by a genetic algorithm michael L. Gargano iconProject Gutenberg's Booknology: The eBook (1971-2010), by Marie Lebert This eBook is for the use of anyone anywhere at no cost and with almost no restrictions

Feasible task schedules with minimum project cost solved by a genetic algorithm michael L. Gargano iconA modified method of minimum dispersion in the fsk signal parameters estimation task
Применение дискриминирующей функции в задачах оценивания порядка марковской цепи и контекстной функции марковской цепи переменного...
Feasible task schedules with minimum project cost solved by a genetic algorithm michael L. Gargano iconInbred strains of rats \par \qc Updated April 9, 1998. \par \qj Michael F. W. Festing \par For the committee on Genetic Nomenclature of the Rat: \par T. J. Gill

Feasible task schedules with minimum project cost solved by a genetic algorithm michael L. Gargano iconCost Uncertainty Assessment and Management: The Integrated Cost-Risk Analysis Model

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


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