Belirsiz İşlem Süresine Tabi Paralel Makine Çizelgelemeleri

Abstract

Günümüz dünyasında iş ve üretim rekabeti, firmaların verimlilik artıran ve imalat maliyetini düşüren çizelgeler üretmesine yol açmıştır. Ancak, üretilen çizelgeler beklenmedik aksaklıklar yüzünden, genellikle amaçlandığı şekilde uygulanamamaktadır. Bu aksaklıklar makine arızalanması, sipariş iptali gibi örneklendirilebilir. Aksaklıklara duyarsız çizelge olan gürbüz çizelgeleme, son yıllarda araştırmacılar arasında önem kazanmıştır. Bu çalışmada, belirsiz işlem süresine tabi paralel makine ortamı ele alınmıştır. Performans ölçütü son işin bitiş süresi olarak alınmıştır. Belirsizlik, ayrık senaryolar olarak modellenmiş ve küçük boyuttaki problemleri çözebilen bir tam sayılı programlama oluşturulmuştur. Bu model büyük problemleri çözmede sıkıntılıdır. Bu sebeple senaryo sayısını azaltma yaklaşımı denenmiştir. Daha sonra eşiz ayrıştırma yöntemi ile büyük problemlerin çözümü amaçlanmıştır. Bu yöntemi kullanmadaki amaç büyük bir problem çözmek yerine, küçük ama çok sayıda problem çözerek sonuca ulaşmaktır. Ancak bu yöntem de büyük problemlerde istenilen sonuçları vermemiştir. Bu sebeple senaryo sayısı azaltılarak eşiz ayrıştırma yöntemi kullanılmış ve yeni bir sezgisel önerilmiştir. Aynı zamanda bir tabu arama algoritması oluşturulmuştur. Sonuçlar, önerilen sezgisel algoritmalardan senaryo azaltılması ve tabu arama algoritmalarının paralel makine ortamında iyi sonuçlar verdiğini göstermektedir.

Competition in today's business and production world leads the companies to generate schedules that increase productivity and decrease manufacturing cost. However, most of the schedules cannot be executed exactly because of the unexpected disruptions such as machine breakdowns, order cancellations and so forth. In order to develop disruption resistant schedules, robust scheduling subject has gained interest among researchers. In this study, we consider a parallel machine environment with processing time uncertainty. The performance measure is taken as the completion time of the last job. The uncertainty is modeled by discrete set of scenarios. An integer programming model that can handle small problems is proposed. We observe that this model cannot manage large problems. To alleviate this difficulty, we propose to decrease number of scenarios selected for model. Next, we apply dual decomposition method in order to solve many smaller problems rather than a large problem. Large problems cannot be handled by this method either. This is why; we alter dual decomposition method by relaxing and develop a new heuristic. Also we propose a hybrid tabu search algorithm to solve the large problems. The results show that, the proposed heuristics; selecting scenario approach and tabu search algorithm perform well for the parallel machine scheduling problems.