An efficient branch and bound algorithm for the resource leveling problem

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Mühendislik Fakültesi, İnşaat Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2013

Öğrenci: HÜSEYİN YENİOCAK

Danışman: RİFAT SÖNMEZ

Özet:

Resource leveling problem (RLP) focuses on optimizing resource utilization curves obtained by using Critical Path Method (CPM). This thesis presents a new and efficient branch and bound algorithm for the RLP. The proposed algorithm has been compared with mixed-integer linear modeling methods and previous branch and bound algorithms. An adaptive branch and bound heuristic has been developed for a good upper bound calculation. A new lower bound calculation strategy has been introduced and dual calculation has been used to obtain better lower bound values. Activity selection methods for branching process have been proposed to improve lower bounds and accelerating techniques have been implemented to achieve an efficient branch and bound algorithm for the RLP. Extensive computational experiments have been conducted using test problems from the literature including instances from Project Scheduling Problem Library (PSPLIB), Kolisch et al. (1999), Franck et al. (2001) and Rieck et al. (2012). The branch and bound algorithm has proven the best performance in terms of computational times for problems up to 20 activities for all objective functions. Moreover, for resource idle days optimization, problems up to 30 activities were solved for the first time in literature. Mixed-integer linear model could only solve problems with 10 activities for resource idle days and its performance highly depends on the type of the objective function. The proposed branch and bound algorithm provides a powerful method for the RLP due to its flexibility in applying several accelerating techniques and it can solve optimization functions in all forms.