Article ID: | iaor20001506 |
Country: | Netherlands |
Volume: | 113 |
Issue: | 1 |
Start Page Number: | 91 |
End Page Number: | 100 |
Publication Date: | Feb 1999 |
Journal: | European Journal of Operational Research |
Authors: | Azizoglu Meral, Kirca Omer |
Keywords: | programming: branch and bound |
We consider the NP-hard problem of scheduling jobs on identical parallel machines to minimize total weighted flow time. We discuss the properties that characterize the structure of an optimal solution, present a lower bound and propose a branch and bound algorithm. The algorithm is superior to prior methods presented in the literature. We also extend the algorithm to uniform parallel machines and solve medium-sized problem instances.