Solving the single machine scheduling problem with sequence-dependent set-up times as a TSP via evolutionary algorithms

Abstract

Scheduling is an active area of research in applied artificial intelligence. Scheduling problems typically comprise several concurrent (and often conflicting) goals, and several resources which may be allocated in order to satisfy these goals. In many cases, the combination of goals and resources results in an exponentially growing problem space. As an immediate result, no deterministic method exists for solving those problems in polynomial time. Such problems are called NP-complete problems, with respect to the exponential time and memory requirements necessary to reach optimal solutions. Approaches to scheduling have been varied and creative. Examples of the different underlying scheduling techniques are local search, simulated annealing, constraint satisfaction, evolutionary computation, among others. The problem is choosing the appropriate technique for a specific type of scheduling application.