Toggle Main Menu Toggle Search

Open Access padlockePrints

The Newcastle University research output collection, currently available on ePrints, will shortly be moving to a new open repository platform, Figshare. To prepare for the data migration we have paused adding new content to ePrints, and will resume once the new repository is launched. During this time you will continue to have access to ePrints (but no new content will appear). We will share updates here when available.

An Improved Branch-and bound Algorithm for the Job-shop Scheduling Problem of Minimising Makespan

Lookup NU author(s):

Downloads

Abstract

An improved algorithm for determining an optimimum solution to a job-shop scheduling problem is presented. The algorithm utilises a backtracking branch-and-bound search but a slightly different branching process from that suggested by Lomnicki (2) has been employed and has resulted in the calculation of more realistic lower bounds. The modifications to the algorithm were discovered in interactive investigations into the problem and in such investigations optimal solutions to the scheduling of up to 30 jons upon 5 machines have been acheived within a modest amount (2-3 minutes) of computation.

Publication metadata

Author(s): Waller L

Series Editor(s): Shaw B

Publication type: Report

Publication status: Published

Series Title: Computing Laboratory Technical Report Series

Year: 1972

Pages: 18

Print publication date: 01/12/1972

Source Publication Date: December 1972

Report Number: 40

Institution: Computing Laboratory, The University of Newcastle upon Tyne

Place Published: Newcastle upon Tyne

Share