vABSTRACTHYBRID CONTINUOUS SCATTER SEARCH APPROACH TOTARDINESS RELATED SCHEDULING PROBLEMSIn this thesis, a hybrid approach, which integrates Scatter Search (SS) and aVariable Neighborhood Search (VNS), is presented to attack tardiness related schedulingproblems. The aim is to find advanced strategies that can be adapted to the basic SSmethodology in order to enhance its diversification and intensification capabilitiesthroughout the scheduling problems. The Hybrid Continuous Scatter Search (HCSS)approach is first implemented on the Single Machine Total Weighted Tardiness (SMTWT)problem to minimize total weighted tardiness. Then the HCSS method is modified toaddresses the Parallel Machine Total Tardiness (PMTT) problem, which consists of a set ofjobs to be scheduled on a number of parallel processors to minimize total tardiness. TheNP-hard nature of both problems renders a challenging area for research.In order to develop a robust hybrid methodology, the key elements of the ScatterSearch such as reference set update method, initial solution generation method, solutioncombination method and as an intensification strategy-the hybridized VNS areinvestigated. The employed solution encoding, diverse solution selection methods, anddynamic solution combination method are unique and introduced first time in this thesis toprovide new ideas for Scatter Search era. The proposed HCSS approach yields goodquality results with respect to optimal/best-known solutions reported in the literature.

viÖZETARTI GEC KME TABANLI Ç ZELGELEME PROBLEMLER NEMELEZ SÜREKL DAĞILIM ARAMASI YAKLAŞIMIBu tezin konusu olan çalışmada, Artı Gecikme Tabanlı Atama problemleriniçözmek için Dağılım Araması (DA) ve Değişken Komşuluk Araması (DKA) yöntemlerinibünyesinde birleştiren melez bir yaklaşım sunulmuştur. Bu tezde amaç, DA metodununatama problemlerinin çözümündeki başkalaşım ve kuvvetlendirme kabiliyetlerini artırmakiçin temel metodolojisine adapte edilebilecek ileri seviye stratejiler bulmaktır. MelezSürekli Dağılım Araması (MSDA) yaklaşımı ilk olarak Tek Makina Toplam Ağırlıklı ArtıGecikme (TMTAG) probleminde toplam ağırlıklı artı gecikmeyi en küçüklemek içinyürütülmüştür. Bir sonraki kademede MSDA metodu, bir takım işin birkaç paralel işlemciüzerinde toplam artı gecikmesini en küçüklemek amacıyla oluşturulan Paralel MakinaToplam Artı Gecikme (PMTAG) problemini ele alabilmesi için uygun bir şekilde modifiyeedilmiştir. lgilenilen problemlerinin NP-zor doğası itibari ile ortaya iddialı bir araştırmakonusu çıkmıştır.Sağlam bir metodoloji geliştirmek için Dağılım Araması yönteminin anahtarelemanları olan; referans kümesi güncelleme metodu, başlangıç çözümü oluşturmametodu, çözüm birleştirme metodu ve çözüm kuvvetlendirme stratejisi olarak DKAyöntemi incelenmiştir. Kullanılan çözüm kodlaması, farklı çözüm seçme metodu vedinamik çözüm birleştirme metodu DA yöntemine yeni fikirler teşkil etmek amacı ile ilkdefa bu tezde sunulmuşlardır. Tasarlanan MSDA yaklaşımı literatürde yayınlanmış bilinenen iyi çözümlerle karşılaştırıldığında kaliteli sonuçlar vermektedir.