An improved ant colony algorithm for the job shop scheduling problem

Abstract

Instances of static scheduling problems can be easily represented as graphs where each node represents a particular operation. This property makes the Ant Colony Algorithms well suited for different kinds of scheduling problems. In this paper we present an improved Ant System for solving the Job Shop Scheduling (JSS) Problem. After each cycle the Ant System applies a scheduler builder to each solution. The schedule builder is able to generate under a controlled manner different types of schedules (from non-delay to active). Any improvement achieved for a solution will affect the performance of the algorithm in the next cycles by changing accordingly the amount of pheromone on certain paths. Since the pheromone is the building block of an ant algorithm, it is expected that these changes guide the search towards more promising areas of the search space. The computational study involves a set of instances of different size and difficulty. The results are compared against the best solutions known so far and results reported from earlier studies of ant algorithms applied to the JSSP.