A Parallel machine scheduling problem with sequence dependent set-up times

Abstract

ÖZET Bu tezin konusu, gelişigüzel termin tarihleri, sisteme giriş zamanlan ve işlem zamanlan olan ve sıraya bağlı iş hazırlık zamanlarının geçerli olduğu, bağımsız, boşaltmasız n sayıdaki işi, m sayıdaki paralel, özdeş makineye atama problemidir. Buradaki amaç en büyük artı gecikmeyi enküçüklemektir. Bu çalışmada Önerilen çözüm yöntemi iki aşamadan oluşmaktadır. İlk aşama çeşitli bulgusal algoritmaları kapsamakta, ikinci aşama ise ilk aşama çizelgelerinin sonuçlarını geliştirmeye yönelik bir iş değiştirme algoritmasından oluşmaktadır. Bulgusal algoritmaların sonuçlarını değerlendirmek amacıyla, örtük birerleme yöntemine dayanan bir eniyileme algoritması geliştirilmiş ve uygulanmıştır. Son olarak, değişik zorluk düzeylerinde problemler tasarlanmış ve yukarıda değinilen tüm algoritmalar bu problemler üzerinde denenmiştir. Bulgusal algoritmaların sonuçlan en iyi sonuçla ve birbirleriyle, sonuç kalitesi ve çalışma zamanı açısından karşılaştırılmıştır. Îş değiştirme algoritmasıyla elde edilen gelişmeler de ayrıca kaydedilmiştir. Örtük birerleme yöntemine dayanan ve en iyi sonucu bulan algoritmanın çalışma zamanını kısaltmak amacıyla üç adet dışlama kuralı uygulanmış ve bu kuralların performansları değişik düzeylerde dışladıkları sonuçlara göre kaydedilmiş ve değerlendirilmiştir.

IV ABSTRACT The subject of concern in this research is to study the problem of scheduling a set of independent, nonpreemptive jobs with sequence dependent set-up times and arbitrary ready times, due dates and process time requirements, on parallel, identical machines with the aim of minimizing maximum tardiness of all jobs in the job set The complete heuristic solution methodology proposed in this thesis is composed of two phases. The first phase includes initial solution generation heuristic algorithms and the second phase covers an interchange algorithm, that is applied to the resulting schedules of the first phase, with the aim of improving the solution value. In order to test the performances of the heuristic algorithms, an optimization algorithm based on implicit enumeration technique has been developed. Finally, several test problems, each of which have different difficulty levels, have been generated in order to test the performances of the heuristic algorithms proposed in this thesis. The results of the heuristic algorithms were compared with the optimal schedules obtained by the implicit enumeration algorithm, and the heuristic algorithms were also compared with each other with respect to solution quality and computation time. Improvements obtained by the second phase of the heuristic algorithm over the solutions of the first phase heuristic algorithms have been also recorded. In the implicit enumeration algorithm, three exclusion rules have been employed with the aim of reducing the size of the solution space and thus the required computation time. Performances of the three exclusion rules were evaluated with respect to the number of nodes fathomed by each exclusion rule.