In a single machine problem a set of tasks has to be processed without preemptionon a machine in such a way that at most one task is processed at any time and agiven objective function is optimized.This thesis examines the single machine scheduling problems with timelag constraints.In these problems, precedence relations exist among the tasks that are tobe scheduled. In a precedence relation, successor task is not allowed to start beforethe processing of the predecessor task is completed. Precedence relations may begeneralized by adding the timelag constraints. In this thesis, timelags are assumed tobe minimal timelags. Timelag constraint necessitates delaying the start time of thesuccessor task after the completion time of the preceding task. Precedence constraintsbetween tasks that have to be respected in every feasible schedule generally increasethe computational complexity of a scheduling problem. Occasionally, their introductionmay turn a problem that is solvable within polynomial time into an NP-completeone (Lenstra and Rinnoy Kan, 1978). Generalizing the problems with precedence constraintsby introducing the timelag constraint makes problems harder. In additionto precedence and timelag constraints, the release time constraint is considered inthis thesis. Even though there exists a wide variety of results on the complexity ofscheduling problems with precedence and timelag constraints, there are still someproblems for which the complexity status remains open.In this thesis, two scheduling problems with open complexity status are provento be polynomially solvable. Also, a scheduling problem which is the generalizationof two strongly NP-hard problems is considered and a branch and bound algorithmis proposed. Furthermore, for each problem, integer programming model is given.Finally, computational results are provided.

Tek makine çizelgeleme probleminde, bir grup iş, ilgili amaç fonksiyonunu en iyileyecekve eşzamanlı olmayacak şekilde kesintisiz olarak işlenmelidir.Bu tez erteleme kısıtlı tek makine çizelgeleme problemlerini konu almaktadır. Buproblemlerde, çizelgelenecek işler arasnda öncelik ilişkileri bulunmaktadır. Bir öncelikiliş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şinbaş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-tamprobleme 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ılmazamanları ile ilgili kısıtlar dikkate alınmaktadır. Geçmiş çalışmalarda öncelik veerteleme 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 polinomsürede çözülebilir olduğu gösterilmektedir. Ayrıca, iki farklı güçlü NP-zor problemingenelleştirilmiş şekli olan bir çizelgeleme problemi incelenmekte ve bir dal ve sınıralgoritması önerilmektedir. Çalışmada incelenen her problem için ilgili tamsayılı programlama modeli sunulmaktadr. Son olarak, önerilen tüm çözüm yöntemleri içinuygulama sonuçları değerlendirilmektedir.