The paper deals with a parallel approach to job shop scheduling by a branch and bound methodology using the lower bound proposed by Ashour and Hiremath. The optimal solution is achieved by an iterative-reductive strategy. At each iteration the algorithm investigates the conflict intervals and it selects a subset of the possible solutions. The makespan value, achieved by the parallel processes, gives the upper limit for the admissible lower bound of the intermediate solutions. Furthermore the best makespan reached by each iteration is reused as a filter to reduce the complexity of the next iteration. The computation is speeded up by a parallel implementation, giving the possibility of distributing code and data into a network of processors. In particular a transputer network and a hypercube system have been employed to carry out the experiments. The concurrent running of more searches manages to reach more makespan values in a shorter time, thus determining a better filtering of the branches to be explored. This facility, in spite of the redundancy due to the parallel approach, produces a total number of opened nodes less than Ashour's serial algorithm.

Genco, A., Lacagnina, V., Masnata, A., Pecorella, G. (1993). Job shop scheduling by a parallel approach. In C.A. Brebbia, H. Power (a cura di), Applications of Supercomputers in Engineering III (pp. 35-45). Transactions of the Wessex Institute [10.2495/ASE930031].

Job shop scheduling by a parallel approach

GENCO, Alessandro;LACAGNINA, Valerio;MASNATA, Attilio;
1993

Abstract

The paper deals with a parallel approach to job shop scheduling by a branch and bound methodology using the lower bound proposed by Ashour and Hiremath. The optimal solution is achieved by an iterative-reductive strategy. At each iteration the algorithm investigates the conflict intervals and it selects a subset of the possible solutions. The makespan value, achieved by the parallel processes, gives the upper limit for the admissible lower bound of the intermediate solutions. Furthermore the best makespan reached by each iteration is reused as a filter to reduce the complexity of the next iteration. The computation is speeded up by a parallel implementation, giving the possibility of distributing code and data into a network of processors. In particular a transputer network and a hypercube system have been employed to carry out the experiments. The concurrent running of more searches manages to reach more makespan values in a shorter time, thus determining a better filtering of the branches to be explored. This facility, in spite of the redundancy due to the parallel approach, produces a total number of opened nodes less than Ashour's serial algorithm.
Settore SECS-S/06 -Metodi Mat. dell'Economia e d. Scienze Attuariali e Finanz.
Genco, A., Lacagnina, V., Masnata, A., Pecorella, G. (1993). Job shop scheduling by a parallel approach. In C.A. Brebbia, H. Power (a cura di), Applications of Supercomputers in Engineering III (pp. 35-45). Transactions of the Wessex Institute [10.2495/ASE930031].
File in questo prodotto:
File Dimensione Formato  
1993_Job shop scheduling by a parallel approach.pdf

Solo gestori archvio

Descrizione: Articolo
Dimensione 882.85 kB
Formato Adobe PDF
882.85 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/10447/55733
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 0
social impact