Local constraint based analysis in resource constrained scheduling

Abstract

KAYNAK KISITLI CÎZEL6ELEMEDE BEREKLÎ YEREL KOŞULLAR Kaynak kısıtlı çizelgelerce problemi genel olarak eni yi çizelgeleme teknikleri ile çözülür. Ancak bu yöntemler büyük problemlerde çözüm zamanı açısından yetersiz kalmaktadır, öte yandan gerçek dinamik ortamlarda en iyiye yakın ve hızla elde edilebilen çizelgeler gereklidir. Dinamik öğelere yanıt verilmesinin bir yolu benzetim çalışmalarında veya durağan olarak eniyi çözümlerle karşılaştırılıp değerlendirilen sezgisel yöntemlerdir. Ancak bu yöntemler düzenli olarak iyi çizelgeler yaratamamakta problem özelliklerine göre farklılık göstermektedir. Bu çalışmadaki yaklaşım ise sözü geçen iki yöntemin arasında yer almaktadır. Performans kriteri çizelgeleme işlemi üzerinde bir kısıt olarak görülmekte ve kaynak kısıtları ile birlikte düşünülmektedir. Bu kısıtlar işlerin birbirlerine göre sıralarını her lokal karar verme anında belirlemektedir. Bu çalışmada, zorunlu yerel koşullar ayrıntılı olarak anlatılmakta ve kaynak kısıtlı çizelgeleme için bu koşulları içeren durağan ve dinamik algoritmalar verilmektedir. Daha önce çözülmüş olan durağan proje çizelgeleme problemleri için yerel kısıt analizi yöntemi ile elde edilen sonuçlar hem eniyi çözümlerle hem de tanınmış sezgisel yöntemlerle karşılaştırılmıştır. Ayrıca, çeşitli atelye özelliklerini içeren durağan atelye problemleri için de kısıt analizi sonuçları ile sezgisel yöntemlerin sonuçları karşılaştırılmıştır.

IV LOCAL CONSTRAINT BASED ANALYSIS IN RESOURCE CONSTRAINED SCHEDULINB Resource constrained scheduling problems are generally solved by optimization techniques which cannot accomodate large size problems with respect to computation time. Yet, fast and near optimal schedules are required in actual dynamic environments. A method which has a quick response to dynamic conditions is the usage of dispatching rules which are tested and evaluated in simulation studies or against static optimal solutions. The disadvantage of heuristics lies in their performance dependence on problem characteristics. Constraint based analysis (CBA) approach employed here stands midway between the latter two methods. The performance criterion is imposed on the scheduling process as a constraint together with resource limitations. These constraints are considered as locally essential at each scheduling decision point and activities are sequenced in accordance with the constraints. In this research, the local essential conditions are explained in detail and the static and quasi-dynamic algorithms for resource constrained scheduling in which they are incorporated are conveyed. Static solutions for the previously salved project scheduling test problems obtained employing local CBA are compared with well-known heuristics as well as with the optimal solutions. Furthermore, CBA results for static job-shop problems representing various shop characteristics are compared with heuristics.