SIRA-BAĞIMLI HAZIRLIK ZAMANLI İKİ ÖLÇÜTLÜ ÇİZELGELEME PROBLEMİ: TOPLAM TAMAMLANMA ZAMANI VE MAKSİMUM ERKEN BİTİRME

Yıl 2007, Cilt: 23 Sayı: 1, 95 - 105, 01.02.2007

Tamer Eren Ertan Güner

Öz

Bu çalışmada tek makineli sıra-bağımlı hazırlık zamanlı iki ölçütlü çizelgeleme problemi ele alınmıştır. Problemde incelenen ölçütler toplam tamamlanma zamanı ( ∑C ) ve maksimum erken bitirmedir ( Emax ). NP-zor sınıfında olan bu problemi çözmek için 0-1 karışık tamsayılı programlama modeli önerilmiştir. Önerilen model, 12 işe kadar olan problem setleri için çözülebilmiştir. Büyük boyutlu problemleri çözmek için modifiye edilmiş NEH algoritması, tabu arama temelli sezgisel algoritmalar ve rassal arama yöntemleri kullanılmıştır. Deney sonuçlarına göre, sunulan sezgisel yöntemler 1000 işe kadar olan problemlerin çözümlerini bulabilecek etkinliktedir. İncelemelerimize göre ele aldığımız bu iki ölçütlü (toplam tamamlanma zamanı ve maksimum erken bitirme) sıra-bağımlı hazırlık zamanlı problem ( max 1/ sjk /α ∑C + βE ), ilk defa bu çalışmada ele alınmıştır.

Anahtar Kelimeler

Tek makineli çizelgeleme, Sıra-bağımlı hazırlık zamanı, İki ölçüt, 0-1 karışık tamsayılı programlama, Sezgisel yöntemler

A BICRITERIA SCHEDULING PROBLEM WITH SEQUENCE DEPENDENT SETUP TIMES: TOTAL COMPLETION TIMES AND MAXIMUM EARLINESS

Öz

We consider a bicriteria scheduling problem with sequence-dependent setup times on a single machine is considered. The objective function of the problem is minimization of the weighted sum of total completion time and maximum earliness. A 0-1 mixed integer programming model is developed for the problem which belongs to NP-hard class. Results of computational tests show that the proposed model is effective in solving problems with up to 12 jobs. For solving problems containing large number of jobs, modified NEH algorithm, tabu search based heuristic and random search methods are presented. According to computational results, heuristic algorithms are effective in finding problem solutions with up to 1000 jobs. According to the best of our knowledge, no works exists on the minimization of the weighted sum of total completion time and maximum earliness problem with sequence-dependent setup times.

Anahtar Kelimeler

Single machine scheduling, Sequence-dependent setup times, Bicriteria, 0-1 mixed integer programming, Heuristic methods