Öğrenme-unutma etkili ve ayar süreli tek makine çizelgeleme problemleri için yeni çözüm yaklaşımları

Abstract

Bu tez çalışmasında, değişken işlem sürelerinin ve beraberinde ayar sürelerinin olduğu iki farklı tek makine çizelgeleme problemi ele alınmıştır. İlk olarak; sıra bağımlı ayar süreleri ve pozisyona bağlı öğrenme etkisi olan toplam gecikme problemi tanımlanmıştır. NP-zor olan bu problemin kesin çözümleri için dal-sınır algoritması, yaklaşık çözümleri için ise iki adet genetik, iki adet de değişken komşu arama algoritması geliştirilmiştir. Dal-sınır algoritmasında kullanılmak üzere polinom zamanda türetilebilen bir alt sınır ve algoritmanın etkinliğini artırmak için iki farklı baskınlık kuralı ortaya konmuştur. Genetik algoritmanın uygunluk fonksiyonuna tavlama benzetimindeki sıcaklık parametresi ve değişken komşu arama algoritmasının karıştırma operatörüne de baskınlık kuralları eklenerek işlevsellikleri artırılmıştır. Rasgele türetilen problem örnekleri ile yapılan uygulama deneyleri neticesinde, çözüm yöntemlerinin performansları değerlendirilmiştir. Deney sonuçları, dal-sınır algoritmasının küçük boyutlu problem örneklerini makul sürelerde çözebildiğini, sezgisel yöntemlerin de yaklaşık çözümleri elde etme konusunda başarılı olduklarını göstermiştir. Bunun yanında, sezgisel yöntemlere uyarlanmış ilave özelliklerin performans üzerindeki olumlu etkileri de gözlemlenmiştir. İkinci olarak; sıra bağımsız ayar süreleri, zamana bağlı öğrenme etkisi ve yine zamana bağlı unutma etkisi olan maksimum tamamlanma zamanı problemi tanımlanmıştır. Tanımlanan problemde, bir işe yansıyan öğrenme şiddeti kendisinden önce çizelgelenmiş olan işlerin normal işlem süreleri toplamına bağlı bir fonksiyonla ifade edilmiştir. Her işlemden önce üretimin durmasına yol açan ayar süreleri, unutma etkisinin temel kaynağı olarak ele alınmıştır. Bu nedenle, bir işe yansıyan unutma şiddeti, hem duruştan önceki öğrenme şiddetine hem de o işe ait olan ayar süresine bağlı bir fonksiyonla ifade edilmiştir. İşlem süreleri öğrenme etkisinin, ayar süreleri de unutma etkisinin parametresi olduğundan, iki değişkenli yeni bir öğrenme-unutma modeli tanımlanmıştır. Probleme ait bir takım özellikler sayesinde çözüm karmaşıklığının normal şiddette NP-zor olduğu ıspatlanmıştır. Bu nedenle, kesin çözüm yöntemi olarak tam sayılı doğrusal olmayan programlama modeli ve dinamik programlama algoritması geliştirilmiştir. Önerilen dinamik programlama algoritmasının sözde-polinom zamanlı bir çözüm yöntemi olması, tanımlanan problemin normal şiddette NP-zor olduğunu desteklemiştir. Rasgele türetilen problem örnekleri ile yapılan uygulama deneyleri neticesinde, önerilen her iki yöntemin de etkinliği gösterilmiştir.

In this thesis, two different single machine scheduling problems with variable processing times and setup times are discussed. At first; the total tardiness problem with sequence-dependent setup times and a position-dependent learning effect is defined. Since the problem is NP-hard, a branch&bound algorithm is proposed to obtain exact solutions. Furthermore, genetic and variable neighborhood search algorithms are proposed to obtain approximate solutions. A lower bound which can be calculated in polynomial time and two different dominance rules are employed in the branch&bound. The functionality of heuristics is increased by utilizing dominance rules in the shaking operator of the variable neighborhood search and adapting the temperature parameter of the simulated annealing to the fitness function of the genetic algorithm. Some computational experiments are performed on randomly generated test problems to evaluate the performance of solution approaches. Results show that the branch&bound can optimally solve the small-sized problem samples in a reasonable time and heuristics are successful in obtaining approximate solutions. Furthermore, the positive effects of additional features adapted to heuristics are also observed. Secondly; the makespan problem with sequence-independent setup times, time-dependent learning effect and time-dependent forgetting effect is defined. The learning amount of a job is represented by a function of the-sum-of-normal-processing-times of jobs scheduled before. Setup times are assumed to be the reason for forgetting since they lead to interruptions in the production period before each job. Therefore, the forgetting amount of a job is represented by a function of the setup time and existing amount of learning before the interruption. A new bivariate learning-forgetting model is defined since processing times are the parameter of the learning effect and setup times are the parameter of the forgetting effect. By means of problem properties, it is proved that the computational complexity of the defined problem is ordinary NP-hard. Therefore, an integer-nonlinear-programming-model and a dynamic programming algorithm are proposed as exact solution methods. The fact that the proposed dynamic programming is a pseudo-polynomial time algorithm supports the ordinary NP-hardness of the described problem. Some computational experiments with randomly generated problem samples are performed and results indicate the effectiveness of solution methods.