Search

Bu tezde, ortalama iş akış süresini ve toplam geç kalmış iş sayısını enküçüklemeyihedefleyen iki ölçütlü tek makina çizelgeleme problemini ele aldık. NP-zor olduğubilinen bu problemın önemi ele aldığı ölçütlerden kaynaklanmaktadır. Zira, elealınan birinci ölçüt tedarik zinciri içerisindeki bir üreticinin, ikincisi ise birtüketicinin bakış açısını temsil eder. Bu çok ölçütlü problem için iki yapıcısezgisel yöntem öneriyoruz. Bu iki yöntem ışın taraması algoritması esas alınarakgeliştirilmiştir. Önerilen bu iki algoritma, üçü literatürde mevcut ikisi de yenigeliştirilmiş olan, 5 farklı sezgisel yöntem ile karşılaştırılmıştır. Yaptığımız sayısaltestler sonucu, önerdiğimiz algoritmaların, çoğu zaman en iyi etkin çizelgelereulaştığı ve karşılaştırıldıkları sezgisel yöntemlerden daha iyi sonuçlar verdikleritesbit edilmiştir.Anahtar Kelimeler: İki Ölçütlü Çizelgeleme, Ortalama İş Akış Süresi, ToplamGeç Kalmış İş Sayısı, Işın Taraması. In this thesis, we consider the bicriteria scheduling problem of minimizing numberof tardy jobs and average flowtime on a single machine. This problem, which isknown to be NP-hard, is important in practice as the former criterion conveys thecustomer?s position and the latter reflects the manufacturer?s perspective in thesupply chain. We propose two new heuristics to solve this multiobjectivescheduling problem. These two heuristics are constructive algorithms which arebased on beam search methodology. We compare these proposed algorithms withthree existing heuristics in the literature and two new meta-heuristics. Ourcomputational experiments illustrate that proposed heuristics find efficientschedules optimally in most of the cases and perform better than the otherheuristics.Keywords: Bicriteria Scheduling, Average Flowtime, Number of Tardy Jobs, BeamSearch. 76

We propose an efficient liver allocation system for allocating donated organs to patients waiting for transplantation, the only viable treatment for End-Stage Liver Disease. We optimize two metrics which are used to measure the efficiency: total quality adjusted life years and the number of organs wasted due to patients rejecting some organ offers. Our model incorporates the possibility that the patients may turn down the organ offers. Given the scarcity of available organs relative to the number patients waiting for transplantation, we model the system as a multiclass fluid model of overloaded queues. The fluid model we advance captures the disease evolution over time by allowing the patients to switch between classes over time, e.g. patients waiting for transplantation may get sicker/better, or may die. We characterize the optimal solution to the fluid model using the duality framework for optimal control problems developed by Rockafellar (1970a). The optimal solution for assigning livers to patients is an intuitive dynamic index policy, where the indices depend on patients' acceptance probabilities of the organ offer, immediate rewards, and the shadow prices calculated from the dual dynamical system. Finally, we perform a detailed simulation study to demonstrate the effectiveness of the proposed policy using data from the United Network for Organ Sharing System (UNOS).