A Comparison of the neighbourhood structures in job-shop scheduling by the tabu search procedure

Atölye tipi çizelgelemede komşuluk yapılarının tabu arama tekniği ile karşılaştırılması

Abstract

Scheduling together with production planning is an important function which determines the efficiency and productivity of a manufacturing system. Therefore, the much better a job shop level is scheduled, the more likely the efficiency and productivity of the manufacturing system can be increased. When it is conceived that the efficiency of the job shop production is intrinsically low, the important of the scheduling function will be realized well. The aim of this paper is to contribute to creating of the better scheduling methods by modern optimization techniques based on neighbourhood search. Neighbourhood structure is an important element among the search methods based neighbourhood search such as local search, genetic algorithm, simulated annealing, tabu search etc. for job shop scheduling. Because the neighbourhood relationships used in these methods affect the solution quality. It is aimed to compare the 5 neighbourhood structures from the literature and a new neighbourhood structure developed in this paper. As regards the neighbourhood structures, the detailed explanations on Gantt diagrams are given. We compare these neighbourhoods by the tabu search procedure coded in Pascal. In conclusion, it is stated that the proposed neighbourhood structure can efficiently be used in the neighbourhood search methods for job shop scheduling.

Özet

Çizelgeleme üretim planlama ile beraber, bir imalat sisteminin etkinlik ve verimliliğini belirleyen önemli bir fonksiyondur. Bu yüzden, eğer atölye düzeyi ne kadar iyi çizelgelenebilirse, imalat sisteminin etkinlik ve verimliliği o oranda arttırılmış olur. Atölye tipi üretimde etkinliğin (tabii yapısı gereği) genel olarak düşük olduğu düşünüldüğünde, çizelgeleme fonksiyonunun önemi daha iyi anlaşılmaktadır. Bu çalışmanın amacı, komşuluk araması temelinde, çağdaş optimizasyon teknikleriyle daha iyi çizelgeleme yöntemlerinin oluşturulmasına katkı sağlamaktır. Atölye tipi üretim çizelgeleme problemlerinin çeşitli yerel arama, genetik algoritma, benzetimli tavlama ve tabu arama gibi komşuluk araştırması temeline dayanan arama yöntemleriyle çözümünde komşuluk yapısı çok önemli bir Unsur olarak ortaya çikar. Çünkü bu yöntemlerde kullanılan komşu çözüm üretme düzeneğinin yapısının çözüm kalitesini etkilediği düşünülmektedir. Bu çalışmada, literatürde yer alan 5 komşuluk yapısı ile bu çalışma kapsamında geliştirilen yeni bir komşuluk yapısının Gantt diyagramları üzerinde detaylı açıklanması ve birbirleriyle karşılaştırılması amaçlanmıştır. Bu amaçla oluşturulan tabu arama algoritması Pascal dili ile programlanmıştır. Sonuçta, amaçlanan yeni komşuluk yapısının, komşuluk arama yöntemleriyle atölye tipi çizelgelemede etkinlikle kullanılabileceği gibi bazı sonuçlar ifade edilmiştir.