An improved branching scheme for the branch and bound procedure of scheduling n jobs on m parallel machines to minimize total weighted flowtime

Abstract

A branch and bound procedure to solve the n job, m parallel machine problem for the weighted flowtime criterion has been developed by Elmaghraby and Park (1974) and further modified by Barnes and Brennan (1977). This paper proposes a branching scheme different from theirs and shows its superiority. Also, some new and simple results are presented which are easy to implement to obtain an efficient branch-and-bound algorithm. In addition, a new and improved lower bound is developed which is easy to compute.