Скачать 142.94 Kb.

FEASIBLE TASK SCHEDULES WITHMINIMUM PROJECT COST SOLVED BY A GENETIC ALGORITHM Michael L. GarganoLouis 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 i^{th} row and j^{th } 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.
The cost of completing task i at time t is given by the following.
Cost of doing task i at time t. 
All possible feasible schedules and the resulting project cost. 6 7 5 3 4 1 2
Cost of doing task i at time t.
All possible feasible schedules and the resulting project cost. Theorem A partial order on a finite nonempty 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 nonempty t_{p} = a minimal element in T (if there is a choice choose randomly) T = T – {_{ }t_{p} } p = p + 1 Output( a feasible schedule t_{i1}, t_{i2}, t_{i3},…, t_{in}, i.e., a feasible permutation of t_{1}, t_{2}, t_{3},…, t_{n} ) The Genetic Algorithm
then return best population member(s) else go to step 4. Theorem If P_{1} = t_{i1}, t_{i2}, t_{i3}, t_{i4},… t_{i k}, t_{i k+1},…, t_{i n2}, t_{i n1}, t_{i n} and P_{2} = t_{j1}, t_{j2}, t_{j3}, t_{j4},… t_{j k}, t_{j k+1},…, t_{j n2}, t_{j n1}, t_{j n} are partial orders on a finite nonempty set T (i.e., the parents), then the children (offspring) C_{1} = t_{i1}, t_{i2}, t_{i3}, t_{i4},… t_{i k}, t_{j k+1*},…, t_{j n2*}, t_{j n1*}, t_{j n*} with {_{ }t_{j k+1*},…, t_{j n2*}, t_{j n1*}, t_{j n* }} = T – {_{ }t_{i1}, t_{i2}, t_{i3}, t_{i4},… t_{i k }} and t_{j k+1*},…, t_{j n2*}, t_{j n1*}, t_{j n* }having its ordering the same as in P_{2 } and C_{2} = t_{i1*}, t_{i2*}, t_{i3*}, t_{i4*},… t_{i k*}, t_{j k+1},…, t_{j n2}, t_{j n1}, t_{j n} with {_{ }t_{i1*}, t_{i2*}, t_{i3*}, t_{i4*},… t_{i k* }} = T – {_{ }t_{j k+1},…, t_{j n2}, t_{j n1}, t_{j n }} and t_{i1*}, t_{i2*}, t_{i3*}, t_{i4*},… t_{i k*} _{ }having its ordering the same as in P_{1 } are also partial orders on the finite nonempty 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_{ } P_{1 }= 1 2 3 4 5 6 7 8 9 10 11 12 and _{ } _{ } P_{2 }= 3 1 7 2 4 6 5 8 10 9 12 11 then C_{1} = 1 2 3 4 5 6 7 8 10 9 12 11 C_{2 }= 1 2 3 4 6 7 5 8 10 9 12 11. Notice that the first 6 = k positions of C_{1} are the same as P_{1} while the last 6 = n – k reflect the order of 7 8 9 10 11 12 as seen in P_{2}, that is, 7 8 10 9 12 11 and similarly note that the last 6 = n – k positions of C_{2} are the same as P_{2} while the first 6 = k reflect the order of 3 1 7 2 4 6 as seen in P_{1}, 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. FitnessThere 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 t_{1}, t_{2}, t_{3},…, t_{n} and if t_{i1}, t_{i2}, t_{i3},…, t_{in} is a feasible schedule (i.e., a permutation of the tasks that forms a feasible schedule) then task t_{ij} is completed in time period j with associated cost C (t_{ij}, j). The fitness of this feasible task schedule is given by Fitness (t_{i1}, t_{i2},…, t_{in}) = Σ C (t_{ij}, j) _{ }summed over all tasks = project cost for t_{i1}, t_{i2},…, t_{in} . The Grim ReaperAfter 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 REMARKSFor 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. ACKNOWLEDGEMENTSWe wish to thank Pace University’s Seidenberg School of Computer Science and Information Systems for partially supporting this research. REFERENCESDavis, L. (1991) Handbook of Genetic Algorithms, Van Nostrand Reinhold. Edelson, W. and M.L. Gargano (1998) Minimal EdgeOrdered Spanning Trees Solved By a Genetic Algorithm with Feasible Search Space, Congressus Numerantium 135, 3745. 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, 514. Gargano, M.L., Maheswara Prasad Kasinadhuni, (2004) Selfadaption in Genetic Algorithms using Multiple Genomic Redundant Representations, Congressus Numerantium 167, 183192. 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, 4^{th} Ed, Random House. 