Flowshop and TSP

In this paper we consider an NP-complete problem that it is particularly important in production processes scheduling: the flowshop problem. We propose a solution based on a parallel architecture, using Simulated Annealing (a combinatorial randomized technique), and a connectionist model: the Boltzmann machine. Then, we consider the methods used to implement an algorithm for the flowshop problem on a Boltzmann machine in order to improve the time computing performances. Our strategy is based on capability to reduce the original problem to another one (TSP), that is equivalent to the first; in fact, we will discuss the flowshop polynomial reduction to the asymmetric TSP (i.e. to Directed Hamiltonian Circuit, or DHC); then, we will investigate the equivalence between the DHC and the open symmetric TSP (or UnDirected Hamiltonian Path, UDHP). Finally, we will describe limits of the proposed approach and possible developments.