PARALEL MAKİNELİ ÇİZELGELEMEDE TOPLAM TAMAMLANMA ZAMANI VE MAKSİMUM GECİKMENİN ENKÜÇÜKLENMESİ

Öz

Bu çalışmada iki ölçütlü özdeş iki paralel makineli çizelgeleme problemi incelenmiştir. Problemin amaç fonksiyonu toplam tamamlanma zamanı ve maksimum gecikmenin ağırlıklı toplamını en küçüklemektir. Tamamlanma zamanı ve maksimum gecikme çizelgeleme literatüründe en çok göz önüne alınan ölçütlerdendir. NP-zor yapıda olan bu problemin çözümü için, 2/2/32/ 23 nnn ++ değişkenli ve 23n kısıtlı bir tamsayılı programlama modeli geliştirilmiştir (burada n iş sayısını ifade etmektedir). Tam sayılı programlama modelinin hesaplama zamanı ve yüksek hesaplama karmaşıklığı dolayısı ile 20 işe kadar olan problemlerin çözümleri gerçekleştirilebilmiştir. Problemin daha büyük boyutlu çözümlerini gerçekleştirmek için çizelgelemede iyi bilinen dağıtım kurallarına göre belirlenen sıralar başlangıç çözümü olarak alınarak tabu arama yöntemleri (Tabu I, Tabu II ve Tabu III) ve rassal arama yöntemi geliştirilmiş ve problemin 1000 işe kadar çözümleri bu yöntemlerle belirlenmiştir.

Anahtar Kelimeler

• Paralel makineli çizelgeleme, iki ölçüt, tamsayılı programlama, sezgisel yöntemler.

Minimization of Total Completion Time and Maximum Tardiness on Parallel Machine Scheduling

Abstract

In this study bicriteria identical two parallel machine scheduling problem is considered. The objective function of the problem is minimization of the weighted sum of completion time and maximum tardiness. Total completion time and maximum tardiness are widely used performance measures in scheduling literature. An integer programming model with 2/2/32/ 23 nnn ++ variables and 23n constraints (where n is the number of jobs) is developed for the problem which belongs to NP-hard class. Because of the lengthy computing time and high computing complexity of the integer programming model, the problem with up to 20 jobs can be solved. A random search method and tabu search based heuristic algorithms (Tabu I, Tabu II and Tabu III) are presented to solve large size problems. To improve the performance of tabu search algorithms the sequences found from the well known dispatching rules are taken as an initial solution of tabu search algorithms. According to computational results the tabu search algorithm is effective in finding problem solutions with up to 1000 jobs.

Keywords

• Identical parallel machine, bicriteria, integer programming, heuristic methods.

Kaynakça

1. Eck, B.T., Pinedo, M., 1993, On the minimization of the makespan subject to flowtime optimality, Operations Research, 41, 797-800.
2. Eren, T., 2004, Çok ölçütlü akış tipi çizelgeleme problemleri için çözüm yaklaşımları, Doktora Tezi, Gazi Üniversitesi Fen Bilimleri Enstitüsü, Ankara.
3. Eren, T., Güner, E., 2002, Tek ve paralel makineli problemlerde çok ölçütlü çizelgeleme problemleri için bir literatür taraması, Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi, 17, 4, 37-69.
4. Eren, T., Güner, E., 2004, Çok ölçütlü akış tipi çizelgeleme problemleri için bir literatür taraması, Pamukkale Üniversitesi Mühendislik Fakültesi Mühendislik Bilimleri Dergisi, 10, 1, 19-30.
5. Glover, F., 1986, Future paths for integer programming and links to artificial intelligence, Computers and Operations Research, 5, 533-549.
6. Gupta, J. N.D., Ho, J.C., Webster, S., 2000, Bicriteria optimization of the makespan and mean flowtime on two identical parallel machines, Journal of the Operational Research Society, 51, 11, 1330-1339.
7. Gupta, J.N.D., Ho, J.C., 2001, Minimizing makespan subject to minimum flowtime on two identical paralel machines, Computers and Operations Research, 28, 705-717.
8. Gupta, J.N.D., Ruiz-Torres, A.J., 2000, Minimizing makespan subject to minimum total flow-time on identical parallel machines, European Journal of Operational Research, 125, 370-380.

9. Lenstra J.K., Kan Rinnooy, A.H.G., Brucker, P., 1977, Complexity of machine scheduling problems, Annals of Discrete Mathematics, 4, 281-300.
10. Lin, C.H., Liao, C.J., 2004, Makespan minimization subject to flowtime optimality on identical parallel machines, Computers and Operations Research, 31, 10, 1655-1666.
11. Mohri, S., Masuda, T., Ishii, H., 1999, Bi-criteria scheduling problem on three identical parallel machines, International Journal of Production Economics, 60, 529-536.
12. Sarin, S.C., Hariharan, R., 2000, Two machine bicriteria scheduling problem, International Journal of Production Economics, 65, 2, 125-139.
13. Suresh, V., Chaudhuri, D., 1996, Bicriteria scheduling problem for unrelated parallel machines, Computers and Industrial Engineering, 30, 1, 77-82.