NEURAL NETWORK APPROACHES TO JOB SHOP PROBLEMS

Henrik J\"onsson

Master Thesis

Advisor: Bo S\"oderberg

Abstract

A combinatorial optimization problem in the form of the job shop
problem is approached, using artificial neural networks. The feedback
networks are encoded with Potts neurons, and updated through mean
field theory. For the updating of the starting times belonging to the
operations, simple gradient descent is used.  The topology of the
operations is handled with two different techniques. One is to map the
operations onto artificial slots on the machines, and the other is to
let the neurons take care of the topology, and then a propagator
formalism is needed for the complications that arise.
 The neural network algorithms are tested on the standard
10$\times$10~Fisher \&Thompson problem, and compared with two simple
heuristic methods. The network approaches outperform the heuristic
algorithms, but are still far from the optimal solution.
 Also random test beds for 3$\times$3 and 10$\times$10 job shop
problems are investigated.

June 1997