Single machine scheduling with timelag constraints
Erteleme kısıtlı tek makine çizelgeleme
- Tez No: 374450
- Danışmanlar: PROF. DR. CEYDA OĞUZ
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2014
- Dil: İngilizce
- Üniversite: Koç Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 164
Özet
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.
Özet (Çeviri)
In a single machine problem a set of tasks has to be processed without preemption on a machine in such a way that at most one task is processed at any time and a given 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 to be scheduled. In a precedence relation, successor task is not allowed to start before the processing of the predecessor task is completed. Precedence relations may be generalized by adding the timelag constraints. In this thesis, timelags are assumed to be minimal timelags. Timelag constraint necessitates delaying the start time of the successor task after the completion time of the preceding task. Precedence constraints between tasks that have to be respected in every feasible schedule generally increase the computational complexity of a scheduling problem. Occasionally, their introduction may turn a problem that is solvable within polynomial time into an NP-complete one (Lenstra and Rinnoy Kan, 1978). Generalizing the problems with precedence constraints by introducing the timelag constraint makes problems harder. In addition to precedence and timelag constraints, the release time constraint is considered in this thesis. Even though there exists a wide variety of results on the complexity of scheduling problems with precedence and timelag constraints, there are still some problems for which the complexity status remains open. In this thesis, two scheduling problems with open complexity status are proven to be polynomially solvable. Also, a scheduling problem which is the generalization of two strongly NP-hard problems is considered and a branch and bound algorithm is proposed. Furthermore, for each problem, integer programming model is given. Finally, computational results are provided.
Benzer Tezler
- Implementation of a distributed scheduling system in BUFAIM
Dağıtık yapıdaki bir çizelgeleme sisteminin BUFAIM'de uygulanması
TUNCAY MERDİVEN
Yüksek Lisans
İngilizce
2004
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ALİ TAMER ÜNAL
- Single machine scheduling with resource-dependent processing times under learning and deterioration effect
Öğrenme ve bozulma etkileri altında, kaynak bağımlı işlem zamanlı tek makineli çizelgeleme problemi
BURAK KILIÇ
Yüksek Lisans
Türkçe
2012
Endüstri ve Endüstri MühendisliğiErciyes ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. M. DURAN TOKSARI
- Single machine scheduling with sequence dependent setup times
Sıra bağımlı hazırlık süreleriyle tekli makina çizelgeleme
BURAK LEFKUR
Yüksek Lisans
İngilizce
2021
Endüstri ve Endüstri MühendisliğiÖzyeğin ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ALİ EKİCİ
DOÇ. DR. OKAN ÖRSAN ÖZENER
PROF. DR. SERHAN DURAN
- Single machine scheduling with overtime in multiproduct assembly environment
Çok ürünlü bir montaj ortamında fazla mesai ile tek makine çizelgeleme
MUSTAFA ÜSTÜNÇELİK
Yüksek Lisans
İngilizce
2023
İşletmeAnkara Sosyal Bilimler Üniversitesiİşletme Ana Bilim Dalı
DOÇ. DR. ÇAĞRI KOÇ
DOÇ. DR. HÜSEYİN TUNÇ
- Single machine scheduling with modern heuristic techniques
Modern sezgisel yöntemler ile tek makine çizelgelemesi
GÜZİN KAVRUKKOCA
Yüksek Lisans
İngilizce
2003
Endüstri ve Endüstri MühendisliğiDokuz Eylül ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. LATİF SALUM