A Branch-Bound Solution to the General Scheduling Problem

Abstract

A mixed integer formulation is presented for the general n job, m machine scheduling problem. This formulation is shown to reduce to a series of noninteger L.P. problems of moderate proportions when applying the branch-bound technique. Solutions are presented for the two problems: minimize make-span and minimize idle time. An example and some computational experience for the “minimize idle time” problem are given.