Permutasyon akış tipi çizelgeleme için bir değişken komşuluk arama yaklaşımı

Abstract

Permütasyon akış tipi çizelgeleme, üretim planlama, üretim sistemi, lojistik ve bilgisayar tasarımı da dahil olmak üzere birçok alanda kullanılmaktadır. Zamanlama alanındaki en rekabetçi kombinasyonel optimizasyon problemlerinden biri akış tipi çizelgelemedir. Bu tezde, permütasyon akış tipi çizelgelemede toplam akış zamanın en aza indirilmesi amaçlanarak, problemin çözümü için bir değişken komşuluk arama yaklaşımı uyarlanmıştır. Bu çözüm yaklaşımında, başlangıç çözümleri elde edebilmek için NEH algoritması kullanılırken, algoritmanın çalkalama ve yerel arama safhasında çeşitli komşuluk yapıları kullanılmıştır. Çalkalama ve yerel arama aşamasında hangi operatörlerin daha yüksek başarım gösterdiğine sonuçlarda yer verilmiştir. Ayrıca, uygulanan pertürbasyon yapısının hangi aşamada devreye alınması gerektiği üzerine istatistiksel testler yapılmıştır. Taillard deney setleri üzerinde elde edilen sonuçlar ile sınır değerleri aralarındaki sapma oranları verilmiştir ve rekabetçi yapısını göstermek amacıyla literatürdeki diğer başarılı algoritmalarla karşılaştırılmıştır.

Permutation flow-shop scheduling is used in many areas including production planning, production system, logistics and computer design. One of the most competitive combinational optimization problems in the field of scheduling is flow-shop scheduling. In this thesis, in order to minimize the total flow time in permutation flow-shop scheduling, a variable neighborhood search approach is adopted to solve the problem. In this solution approach, NEH algorithm is used to obtain initial solutions, while various neighboring structures are used during the shaking and local search phases of the algorithm. The results show which operators perform better during the shaking and local search phases. In addition, statistical tests were performed on which stage the perturbation structure should be triggered. The gaps between the results obtained on the Taillard test sets and the lower-bound values are given and compared with other successful algorithms in the literature in order to demonstrate the competitive structure of the proposed algorithm.