In this thesis, we study a two stage flow shop problem with a single server. All jobs are available for processing at time zero. Processing of a job is preceded by a sequence independent setup operation on both machines. The setup and processing times of all jobs on the two machines are given. All setups are performed by the same server who can perform one setup at a time. Setups cannot be performed simultaneously with job processing on the same machine. Once the setup is completed for a job, processing can automatically progress without any further need for the server. Setup for a job may start on the second machine before that job finishes its processing on the first machine. Preemption of setup or processing operations is not allowed. A job is completed when it finishes processing on the second machine. The objective is to schedule the setup and processing operations on the two machines in such a way that the total completion time is minimized. This problem is known to be strongly NP-hard [3]. We propose a new mixed integer programming formulation for small-sized instances and a Variable Neighborhood Search (VNS) mechanism for larger problems. We also develop several lower bounds to help assess the quality of heuristic solutions on large instances for which optimum solutions are not available. Experimental results indicate that the proposed heuristic provides reasonably effective solutions in a variety of instances and it is very efficient in terms of computational requirements.

Bu tez kapsamında; tek sunuculu iki aşamalı seri akış problemi çalışılmıştır. Tüm işler sıfır zamanında işlem görmek üzere hazırdırlar. Her iki makine üzerinde, bir iş için işleme başlamadan önce sıradan bağımsız olarak hazırlık işlemleri yapılmaktadır. Bütün işler için, işlem süreleri ve hazırlık süreleri verilmiştir. Tüm hazırlık işlemleri, tek seferde sadece bir iş için hazırlık yapabilen bir sunucu tarafından yapılmaktadır. Aynı makine üzerinde bir işe ait işlem operasyonu devam ederken aynı anda hazırlık işlemi yapılamamaktadır. Bir işin hazırlığı tamamlandığı zaman, işlem operasyonu sunucuya ihtiyaç duyulmadan otomatik olarak yapılabilmektedir. Bir işin ikinci makinede hazırlanmasına, aynı işin birinci makinedeki işlemi devam ederken başlanabilmektedir. Hazırlık sürelerinin ve işlem sürelerinin bölünerek yapılmasına müsaade edilmemektedir. Bir iş, ikinci makinedeki işlemi bittiğinde tamamlanmış olarak kabul edilir. Problemin amacı verilen tüm işleri iki makine üzerinde toplam tamamlanma zamanlarını en azlayacak şekilde çizelgelemektir. Bu problem NP-zor bir problemdir. Küçük boyutlu problemleri çözmek için karışık tam sayılı programlama modeli, büyük problemleri çözebilmek için ise sezgisel Değişken Komşu Arama mekanizması önerilmiştir. Ayrıca, sezgisel algoritmaların performansını en iyi sonuçların elde edilemediği büyük problemlerde değerlendirebilmek amacıyla, alt sınırlar geliştirilmiştir. Yapılan deneylerin sonucunda; önerilen sezgisel algoritmaların farklı örnek çeşitlerinde etkili sonuçlar verdiği ve hesaplanabilirlik açısından çok etkili oldukları görülmüştür.