An improved branching scheme for the branch and bound procedure of scheduling n jobs on m parallel machines to minimize total weighted flowtime |
| |
| Authors: | SUBHASH C SARIN SEOKYOO AHN ALBERT B BISHOP |
| |
| Affiliation: | 1. Department of Industrial Engineering and Operations Research , Virginia Polytechnic Institute and State University, Blacksburg , Virginia, 24061, USA;2. Korea Institute of Defense Academy , Seoul, S. Korea;3. Department of Industrial and Systems Engineering , The Ohio State University , Columbus, Ohio, 43210, USA |
| |
| 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. |
| |
| Keywords: | |
|
|
