Toggle Main Menu Toggle Search


A Branch-bound-and-imply Algorithm for an Improved Attack Upon the Job-shop Scheduling Problem

Lookup NU author(s):



In branch-and-bound approaches to discrete optimization problems the calculation of lower bounds often assumes certain relations about the behaviour of unassigned variables. Consideration of such behaviour can allow constraints to be imposed upon the space still to be examined with the effect that the performance of the search can be improved. A job-shop scheduling problem is considered here in order to illustrate a potential curtailment of the 'combinatorial explosion' so frequently encountered with such problems.

Publication metadata

Author(s): Waller L

Series Editor(s): Shaw B

Publication type: Report

Series Title: Computing Laboratory Technical Report Series

Year: 1973

Pages: 15

Source Publication Date: May 1973

Report Number: 48

Institution: Computing Laboratory, The University of Newcastle upon Tyne

Place Published: Newcastle upon Tyne