Ardışık makinelerde çoklu operasyona sahip işlerin eş zamanlı çizelgelenmesi

---

Tezin Türü: Doktora

Tezin Yürütüldüğü Kurum: Uludağ Üniversitesi, Türkiye

Tezin Onay Tarihi: 2014

Tezin Dili: Türkçe

Öğrenci: BURCU ÇAĞLAR GENÇOSMAN

Danışman: HÜSEYİN CENK ÖZMUTLU

Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu

Özet:

Bu doktora çalışmasının amacı; makine elverişlilik ve kaynak kısıtları altında ardışık makinelerde işlenmesi gereken farklı sayıda operasyona sahip işlerin bağımsız paralel makine ortamında eş zamanlı olarak çizelgelenmesi problemi için etkili çözüm yöntemleri geliştirmektir. Problemin çözümü için ilk olarak karışık tamsayılı programlama modeli (KTP1) geliştirilmiştir. Bu model teorik olarak problemi temsil etmekle birlikte, gerçek boyutlu problemlerin çözümünde yetersiz kalmıştır. Sonrasında, kısıt programlamanın özel kısıt tanımlamaları kullanılarak kısıt programlama modeli (KP1) geliştirilmiştir. KTP1 ve KP1 çözümleri karşılaştırılmış ve çeşitli iyileştirme çalışmaları gerçekleştirilmiştir. KP1 modelinin atama prosedürleri incelenerek blok atama yapabilen bir tamsayılı programlama modeli (TP1) geliştirilmiştir. Bu model de gerçek boyutlu problemlerle test edilmiş ve diğer yöntemlerden iyi olmasına rağmen optimal çözümlere istenen hızda ulaşamadığı görülmüştür. Bu problemi basitleştirmek amacıyla mantık-tabanlı Benders ayrıştırma tekniği (MTBA) kullanılmış ve MTBA1 ve MTBA2 olarak adlandırılan iki farklı algoritma geliştirilmiştir. Algoritmalarda kullanılan kesimler çeşitlendirilerek iyileştirme çalışmaları gerçekleştirilmiştir. Son olarak, MTBA algoritmasından esinlenilerek TP2/TP1 algoritması geliştirilmiş ve yöntemin optimum sonucu garantilediği ispatlanmıştır. Yapılan karşılaştırmalar sonucunda, TP2/TP1 algoritması ile dakikalar içinde gerçek boyutlu problemlerin optimal çözümlerine ulaşılabildiği görülmüştür.