Fixed job scheduling on uniform parallel machines

Bekki, Özgün Barış
In this study, a fixed job scheduling problem on uniform parallel machines is considered. The objective function is the maximization of the total weight of the jobs processed. We show that it is NP-hard and develop polynomial time algo rithms for some special cases. We propose a branch and bound algorithm that employs dominance conditions and powerful lower and upper bounding proce dures. Computational analysis is conducted to investigate the effects of changing certain parameters on the difficulty of the problem. The results have revealed that the algorithm finds solutions to large sized problem instances in reasonable times.
Citation Formats
Ö. B. Bekki, “Fixed job scheduling on uniform parallel machines,” M.S. - Master of Science, Middle East Technical University, 2003.