It is very difficult to find the minimum makespan and minimum maximum tardiness values concurrently, in the open shop scheduling problems that do not have any precedence constraint of machines of each job. In literature, studies in OSSP are less than flow shop and job shop problem studies.In literature, generally, solutions regarding single criteria are developed; and makespan is the most common objective used. There are some multi objective solutions for one or two machines; but only one criterion is generally used for more than two machines.To the best of our knowledge, this thesis is the first application of Genetic Algorithm and Tabu Search Algorithm to bicriteria Open Shop Scheduling.In this thesis, makespan and maximum tardiness criteria are used concurrently, for problem sizes between 4 jobs ? 4 machines and 15 jobs - 15 machines. For this purpose, a Genetic Algorithm and a Tabu Search Algorithm is developed and applied to test problems.GA and TS are tested, the relative performances of the two algorithms are compared and detailed analysis of results is given.

İşlerin makine kısıtı olmadığı Açık Atölye tipi çizelgeleme problemlerinde işlerin tamamının en az zamanda bittiği ve aynı zamanda maksimum gecikme süresinin en az olduğu çizelgeyi oluşturmak çok zordur. Literatürde, Açık Atölye tipi çizelgeleme problemleri, akış tipi çizelgeleme ve atölye çizelgeleme problemlerinden daha az çalışılmıştır.Literatürde, çizelgeleme alanında yapılan çalışmaların pek çoğunda sadece bir kriter ele alınmıştır ve kriter olarak yoğunlukla üretim tamamlanma zamanı kullanılmıştır. Bir ve iki makine sayılı problemlerde birkaç tane birden çok kriterli çalışmalar yapılmıştır. Ancak ikiden fazla makine sayılı problemlerde genellikle tek amaçlı çalışmalar yapılmıştır.Bilgimiz dahilinde, bu tez iki kriterli Açık Atölye tipi çizelgele problemi çözümüne Genetik Algoritma ve Tabu Arama Algoritması ile çözüm öneren ilk uygulamadır. Bu tezde, üretim tamamlanma zamanı ve maksimum gecikme kriterleri, 4 iş ? 4 makine ve 15 iş ? 15 makine problem boyutları arasında, aynı zamanda kullanılmıştır. Bu amaçla, Genetik Algoritma ve Tabu Arama Algoritması geliştirilmiş ve analiz problemlerine uygulanmıştır.Genetik Algoritma ve Tabu Arama Algoritması analiz edilmiş, iki algoritmanın performansları karşılaştırılmış ve elde edilen sonuçların detaylı analizi yapılmıştır.