An efficient genetic algorithm for job shop scheduling with tardiness objectives

We consider job shop scheduling problems with release and due-dates, as well as various tardiness objectives. To date, no efficient general-purpose heuristics have been developed for these problems. Genetic algorithms can be applied almost directly, but come along with apparent weaknesses. We show that a heuristic reduction of the search space can help the algorithm to find better solutions in a shorter computation time. Two ways of reducing a search space are investigated by considering short-term decisions made at the machine level and by long-term decisions made at the shop floor level.