README for Genetic Algorithm in Directed Acyclic Graph (DAG) Task Scheduling Overview This repository implements a genetic algorithm to optimize task scheduling in a Directed Acyclic Graph (DAG) for a set of tasks with dependencies. The algorithm aims to minimize the "makespan," the total time required to complete all tasks across multiple processes. Each task has dependencies, meaning it cannot start until all preceding tasks are completed.

Code Summary The genetic algorithm initializes a population of task schedules and evolves it over a set number of generations. Each chromosome (individual schedule) in the population is an assignment of tasks to processes. The algorithm applies selection, crossover, and mutation to iteratively improve the population and find the schedule with the minimal makespan.

Dependencies Python 3.6+ Required libraries: numpy: For numerical operations and random number generation. networkx: For creating and visualizing the DAG. matplotlib: For visualizing the task dependency graph. Install these libraries via:

bash Copy code pip install numpy networkx matplotlib Parameters num_tasks: Number of tasks to be scheduled. num_processes: Number of available processes for task execution. population_size: Number of chromosomes in the population. generations: Maximum number of generations the algorithm runs. crossover_rate: Probability of crossover between two chromosomes. mutation_rate: Probability of mutation for each chromosome. Task Dependencies Dependencies between tasks are represented as an adjacency list in task_dependencies. This forms a DAG where an edge from task A to task B means task B depends on A.

Execution Times A random execution time (in the range of 10-40) is generated for each task on each process. The matrix execution_times is a num_tasks x num_processes array, where each entry represents the time a specific task would take on a particular process.

Genetic Algorithm Components Initialization: Randomly generates an initial population, where each chromosome is a schedule assigning tasks to processes. Fitness Calculation: Calculates the makespan for each chromosome, respecting task dependencies. Selection: Uses tournament selection to choose chromosomes with lower makespans for the next generation. Crossover: Applies one-point crossover to create offspring from selected chromosomes. Mutation: Randomly mutates task assignments in chromosomes to introduce diversity. Termination: Stops if no improvement in fitness is observed across generations. Running the Code Run the genetic algorithm with:

python Copy code best_solution, best_makespan = genetic_algorithm() print("Best solution:", best_solution) print("Best makespan:", best_makespan) Visualizing Task Dependencies The code generates a visualization of the task dependencies using NetworkX and Matplotlib, displaying the DAG structure.

Example Output An example output includes the best schedule (task-process assignments) and the makespan for each generation: Generation 1: Best Chromosome - [0, 2, 1, ...], Makespan - 100 Generation 2: Best Chromosome - [0, 2, 1, ...], Makespan - 90 ... Best solution: [0, 2, 1, ...] Best makespan: 75

Notes Adjust the parameters for different task sizes, processes, and dependency structures. The algorithm's performance depends on the crossover rate, mutation rate, and the population size.