Multi-project scheduling with 2-stage decomposition

Abstract

Faaliyetlerin kesintisiz gerçeklestirildigi ve aralarndaki öncül iliskilerinin bitisbaslangç tipinde oldugu, öncül ve ardl faaliyetler arasndaki minimum zaman boslugukstnn sfr oldugu bir ortamda; çoklu kaynak reçeteli, yenilenebilir ve yenilenemezkaynak kstl, çoklu proje çizelgeleme sorunu incelenmistir. iki-asamal ayrsmyaklasm uygulanarak, sorun bir 0-1 matematiksel programlama modelleri hiyerarsisi seklinde düzenlenmektedir. ilk asamada, her proje, farkl yapay bütçedegerlerinin sistematik bir biçimde kullanlmasyla olusturulan farkl süre ve kaynakreçetelerine sahip tek bir makro-faaliyete indirgenir. Bu sürecin sonunda olusanproje serimi Net Bugünkü Degeri (NPV) ençoklamak hedeyle çizelgelenerek, projelerinkaynak kullanmlar ve baslangıç zamanlar belirlenir. ikinci asamada iseher proje, ilk asamada elde edilen baslangıç zamanlar ve kaynak kısıt çizgelerinegöre proje süresini enazlamak hedeyle çizelgelenir. Her iki asamada da veri miktarn azaltmak amacyla baz önisleme yöntemleri gerçeklestirilmistir. Uygun birzaman ufku belirlemenin pozitif nakit aksl çoklu kaynak reçeteli, kaynak kstlproje çizelgeleme üzerindeki etkisi incelenmis ve üç farkl zaman ufku belirlemeyöntemi degerlendirilmistir. Kesin çözüm yöntemi için baslangç çözümü olarak dakullanabilecek iyi çözümler üreten bir genetik algoritma yaklasm da getirilmistir.Bunun yan sra, 2-asamal ayrsm sonras elde kalan kaynak kapasitelerini sonucuiyilestirmek amacyla projelere dagtan bir ardl isleme yöntemi de gelistirilmistr.incelenen problem yapsna sahip test problemleri mevcut olmadgndan önerilençözüm yöntemini snayabilmek için 81, 84, 27 ve 4 problemden olusan dört yeni problemkümesi olusturulmustur. üç farkl çözüm yöntemi kongürasyonu kullanlarakilk üç kümedeki problemler çözülmüs ve bu tez çerçevesinde gelistirilmis ResourceReturn olarak isimlendirilmis yeni bir sezgisel karar kural dördüncü problem kümesikullanlarak snanms ve sonuçlar paylasılmıştr.

A non-preemptive, zero time lag multi-project scheduling problem with multiplemodes and limited renewable and nonrenewable resources is considered. A 2-stagedecomposition approach is adopted to formulate the problem as a hierarchy of 0-1 mathematical programming models. At stage one, each project is reduced to amacro-activity with macro-modes, which are systematically generated by utilizingarticial budgets. The resulting single project network problem is a Multi-ModeResource Constrained Project Scheduling Problem (MRCPSP) with positive cashows. MRCPSP with positive cash ows is solved to maximize NPV and to determinethe starting times and resource allocations for the projects. Using the startingtimes and resource proles obtained in stage one each project is solved at stagetwo for minimum makespan. Three dierent time horizon setting methods, namely,relaxed greedy approach, articial budget and Lagrangian relaxation are developedfor setting the time horizon for MRCPSP with positive cash ows. A genetic algorithmapproach is adopted to generate good solutions, which is also employed as astarting solution for the exact solution procedure. The result of the second stage issubjected to a post-processing procedure to distribute the resource capacities thathave not been utilized earlier in the procedure. Since currently there are no datainstances with the required structure, four new test problem sets are generated with81, 84, 27 and 4 problems each. Three dierent congurations of solution proceduresare tested employing the rst three problem sets. A new heuristic decisionrule designated here as Resource Return factor is presented and tested employingthe fourth problem set.