The Task Scheduling Problem: A NeuroGenetic Approach

Abstract

This paper addresses the task scheduling problem which involves minimizing the makespan in scheduling n tasks on m machines (resources) where the tasks follow a precedence relation and preemption is not allowed.  The machines (resources) are all identical and a task needs only one machine for processing.  Like most scheduling problems, this one is NP-hard in nature, making it difficult to find exact solutions for larger problems in reasonable computational time.  Heuristic and metaheuristic approaches are therefore needed to solve this type of problem.

This paper proposes a metaheuristic approach - called NeuroGenetic - which is a combination of an augmented neural network and a genetic algorithm.  The augmented neural network approach is itself a hybrid of a heuristic approach and a neural network approach.  The NeuroGenetic approach is tested against some popular test problems from the literature, and the results indicate that the NeuroGenetic approach performs significantly better than either the augmented neural network or the genetic algorithms alone.