Solving a class scheduling problem with a genetic algorithm

In this paper, we study the one-machine scheduling problem of minimizing the total flowtime subject to the constraint that each job must finish before its deadline, where the jobs to be scheduled fall into different job classes and setups occur whenever the machine processes consecutive jobs from different classes. A new heuristic is proposed for the problem. We investigate the use of a genetic algorithm to improve solution quality by adjusting the inputs of the heuristic. We present experimental results that show that the use of such a search can be successful.