Job shop scheduling by a parallel approach

Research output: Chapter in Book/Report/Conference proceedingChapter

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 intermediatesolutions. Furthermore the best makespan reached by each iteration is reused asa filter to reduce the complexity of the next iteration. The computation is speeded up by a parallel implementation, giving thepossibility 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 makespanvalues in a shorter time, thus determining a better filtering of the branches to beexplored. 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.
Original languageEnglish
Title of host publicationApplications of Supercomputers in Engineering III
Pages35-45
Number of pages11
Publication statusPublished - 1993

Publication series

NameWIT TRANSACTIONS ON INFORMATION AND COMMUNICATION TECHNOLOGIES

Fingerprint Dive into the research topics of 'Job shop scheduling by a parallel approach'. Together they form a unique fingerprint.

Cite this