Ant Colony Optimization for DSM's Flexible Job Shop Problem

Abstract

This papers examines an ant colony optimization approach for solving a specific variant of the Flexible Job Shop Problem faced by the Dutch chemistry company DSM. Jobs consisting of operations on a specific enzyme need to be scheduled as efficiently as possible on groups of available machines. The most interesting requirement upon the general FJSP are the sequence-dependent cleaning times a machine needs when it processes two different enzyme types consecutively. This can all be intuitively represented using a weighted disjunctive graph, which ACO uses as its input. The algorithm consists of a number of epochs for which multiple ants create a feasible schedule one operation at the time. Scheduling choices are made using pheromones and an heuristic visibility function based on earliest starting times. Pheromone amounts are updated using both a negative local updating rule and a positive global update for the best ant per epoch. Two hyperparameters, the initial pheromone amount τ0 and the cutting exploration parameter q0 are experimentally evaluated. Varying τ0 does not consistently impact the solution quality nor runtime, while the higher the value of q0, the better both measures. Performance evaluation of ACO is done using a provided MILP solver as baseline and the makespan as objective function for a range of different time limits. For the tested instances, ACO shows to significantly outperform MILP, finding good solutions exceptionally fast. Based on this, ACO is an efficient method to solve the production scheduling problem of DSM.