Single machine scheduling with timelag constraints

Tek makine çizelgeleme probleminde, bir grup iş, ilgili amaç fonksiyonunu en iyileyecek ve eşzamanlı olmayacak şekilde kesintisiz olarak işlenmelidir. Bu tez erteleme kısıtlı tek makine çizelgeleme problemlerini konu almaktadır. Bu problemlerde, çizelgelenecek işler arasnda öncelik ilişkileri bulunmaktadır. Bir öncelik ilişkisinde ardıl iş öncül iş tamamlanmadan işlenmeye başlayamaz. Öncelik ilişkileri, erteleme kısıtları eklenerek genelleştirilebilir. Bu tezde, erteleme sürelerinin, farklı işlerin bitiş ve başlangıçları arasında bırakılması gereken en küçük zaman boşlukları oldukları varsayılmaktadır. Erteleme kısıtı, öncül iş tamamlandıktan sonra ardıl işin başlama zamanını ertelemeyi gerektirir. Genelde, olurlu çözümde uyulması gereken öncelik kısıtları, çizelgeleme probleminin karmaşıklık derecesini arttırmaktadır. Bazen, öncelik kısıtlarının eklenmesi polinom sürede çözülebilir olan bir problemi NP-tam probleme dönüştürebilir (Lenstra and Rinnoy Kan, 1978). Öncelik kısıtlı problemler, erteleme kısıtı eklenerek genelleştirildiklerinde daha zor problemlere dönüşmüş olurlar. Bu tezde, öncelik ve erteleme kısıtlarına ek olarak, işlerin sisteme bırakılma zamanları ile ilgili kısıtlar dikkate alınmaktadır. Geçmiş çalışmalarda öncelik ve erteleme kısıtlı problemlerin karmaşıklıkları konusunda çok sayıda sonuca ulaşılmış olsa da, karmaşıklık durumu bilinmeyen bazı problemler bulunmaktadır. Bu tezde, karmaşıklık derecesi bilinmeyen iki ayrı çizelgeleme probleminin polinom sürede çözülebilir olduğu gösterilmektedir. Ayrıca, iki farklı güçlü NP-zor problemin genelleştirilmiş şekli olan bir çizelgeleme problemi incelenmekte ve bir dal ve sınır algoritması önerilmektedir. Çalışmada incelenen her problem için ilgili tamsayılı programlama modeli sunulmaktadr. Son olarak, önerilen tüm çözüm yöntemleri için uygulama sonuçları değerlendirilmektedir.