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.
Gardin, F., Mauri, G., Pensini, M. (1991). Flowshop and TSP. In J. Becker, I. Eisele, F. Mündemann (a cura di), Parallelism, Learning, Evolution Workshop on Evolutionary Models and Strategies, Neubiberg, Germany, March 10-11, 1989. Workshop on Parallel Processing: Logic, Organization, and Technology - WOPPLOT 89, Wildbad Kreuth, Germany, July 24-28, 1989. Proceedings (pp. 157-182). Springer [10.1007/3-540-55027-5_10].
Flowshop and TSP
GARDIN, FRANCESCO;Mauri, G;
1991
Abstract
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.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
