Single Machine Scheduling Problems With Sequence Dependent Setup Times: An Application In Food Industry

Tez (Yüksek Lisans) -- İstanbul Teknik Üniversitesi, Fen Bilimleri Enstitüsü, 2011Thesis (M.Sc.) -- İstanbul Technical University, Institute of Science and Technology, 2011Tez kapsamında, sıra bağımlı hazırlık zamanlı tek makineli çizelgeleme problemlerinin, farklı teslim tarihli ve farklı erken ve geç bitirme cezalarının olduğu durumlar üzerinde çalışılmıştır. Amaç, tam zamanında üretim felsefesine göre istenilen işi istenilen zamanda tamamlayabilmek, böylece erken bitirme ve geç bitirmenin yaratmış olduğu cezalardan mümkün olduğunca kaçınmaktır. Problemde tek makine üzerinde çizelgelenmesi istenen işlerin her birinin hazırlık zamanları, kendisinden bir önceki işe bağlı olarak değişmektedir. İşlem süreleri, teslim süreleri ve erken bitirme ile geç bitirmenin yaratmış olduğu maliyetler yani cezalar işlere göre değişkendir. Tüm bu kısıtların göz önüne alınması, problemin karmaşıklığını artırmış ve NP-zor karmaşıklık sınıfında bir problem oluşturmuştur. Çalışma kapsamında öncelikle literatürde bu tip problemlerin çözümü için var olan doğrusal modeller, sezgiseller ve meta-sezgiseller araştırılmıştır. Literatürde var olan ve küçük boyutlu problemler için kullanılan bir karışık tamsayılı doğrusal model incelenmiş, bu modelin zayıf yanlarına alternatif olarak yine küçük boyutlu problemlerin çözümü için kullanılabilecek bir başka karışık tamsayılı doğrusal model önerilmiştir. Büyük boyutlu problemlerin çözümü, doğrusal modellerle sonlu zamanlarda olamayacağı ya da çok uzun süreceği için çalışmanın devamında meta-sezgisel yöntemler araştırılmıştır. Öncelikle, literatürdeki çizelgeleme problemleri için kullanılmış meta-sezgisel yöntemler incelenmiştir. Bu incelemeler sonucunda, problemin çözümü için yasaklı arama algoritmasının ve genetik algoritmanın kullanılmasına karar verilmiştir. Burada amaç; yasaklı arama algoritmasının genetik algoritma için bir başlangıç çözümü oluşturması, genetik algoritmanın da bu çözümü iyileştirerek en iyiye en yakın nihai çözümü elde edebilmesidir. Bu aşamadan sonra, algoritmalar kodlanarak, en iyi çözümü bilinen küçük boyutlu problem verileriyle çeşitli testler yapılmıştır. Bu testlerin asıl amacı, algoritmanın çözüm performansını en iyiye çekebilecek parametreleri elde ederek, çözümü bilinmeyen büyük boyutlu problemlerin çözümünde kullanmaktır. Yapılan testlerin sonuçlarına göre yasaklı arama algoritması ve genetik algoritma için parametreler belirlenmiş ve uygulama çalışmasında gıda sektöründe faaliyet gösteren bir işletmedeki problemin çözümünde kullanılmıştır. En iyi çözümü bilinmeyen bu problem üzerinde de deneyler yapılarak meta-sezgisel algoritmayla bulunan en iyi çözüm, problemin en iyi çözümü olarak kabul edilmiş ve algoritmanın performansı istatistiksel olarak değerlendirilmiştir.In this thesis, single machine scheduling problem with sequence dependent setup times, different due dates, different earliness and tardiness costs was studied. The purpose is completing the intended works in the intended times so avoiding costs as far as possible, which is caused by earliness and tardiness. The works which are intended to schedule in a machine have setup times that are dependent on its previous work. Processing times, due dates, earliness and tardiness costs are different in respect of the works. Considering all these restrictions increases complexity of the problem and the problem becomes into NP-hard complexity class. In this study, linear models, heuristics and meta-heuristics, which are used for solving this kind of scheduling problems, were researched in literature previously. A mixed integer linear model, which is used for solving small scaled problems in literature, was analyzed and another mixed integer linear model was proposed again for solving small scaled problems alternatively weakness of preexisting model. Solution of large scaled problem is not possible in complete time or takes too long time, so later on meta-heuristic methods were researched. At first, meta-heuristic methods, which are used for scheduling problems in literature, were analyzed. Following this research, tabu search and genetic algorithm were decided to solve the problem. Tabu search algorithm finds a good initial solution and genetic algorithm enhances it. In this way genetic algorithm finds optimum solution or an approximate solution. After that, algorithms were coded and tested with data sets whose optimum solution is known. The main purpose of these tests is obtaining of best parameters, which optimize performance of algorithms, and using these parameters for large scaled problems. According to results of tests, parameters were determined for tabu search and genetic algorithm and used to solve a problem of an enterprise, which operates in food industry. The problem, whose optimum solution is unknown, was tried to solve proposed meta-heuristic algorithm. Results of the experiments made, the best solution was considered of optimum solution and accordingly this solution performance of the algorithm was tested statistically.Yüksek LisansM.Sc