A variable neighbourhood search algorithm for identical parallel machine problem

Abstract

Degisken komsu araması (VNS), yerel bir aramanın içinde komsuların sistematikbir degisikliginin tamamlandıgı kombinatoryel optimization problemlerini çözmek içinkullanılan yeni bir metasezgisel yöntemlerden biridir. Bu tezde, bir VNS algoritmasıarastırması, toplam üretim zamanı kriteriyle özdes paralel makine çizelgelemesi (IPMS)problemi için önerildi. 150 IPMS test problemi (1,100) arasında düzgün dagılımlıolacak sekilde rasgele olusturuldu. Ayrıca, En Uzun slem Zamanı (LPT) Kuralı, bir üstsınır teoremi olarak en kötü olay analizi için kullanıldı. VNS algoritması ile elde edilensonuçlar, her konfigürasyon için sunuldu. Sonuç kalitesi LPT sonuçlarına göredegerlendirildi ve kıyaslandı. Sonuç olarak, VNS algoritmaları kabul edilebilir islemzamanı içinde LPT sonuçlarının 150 örneginden 92 tanesini iyilestirdi.Anahtar Kelimeler: Çizelgeleme, Özdes Paralel Makine, Toplam Üretim Zamanı,Degisken Komsu Araması

Variable Neighbourhood Search (VNS) is one of the most recent metaheuristicsused for solving combinatorial optimization problems in which a systematic change ofneighbourhood within a local search is carried out. In this thesis, an investigation ofVNS algorithm is proposed for the Identical Parallel Machine Scheduling (IPMS)problem with makespan criterion. 150 IPMS benchmark suites are generated randomlywhich is uniformly distributed between (1,100). In addition, Longest Processing Time(LPT) Rule is used for the worst case analysis as an upperbound theorem. The resultsgained by VNS algorithm are presented for each configuration. The solution quality wasevaluated and compared according to the LPT solutions. It is concluded that the VNSalgorithms improved 92 out of the 150 instances of LPT results in a reasonablecomputing time.Keywords: Scheduling, Identical Parallel Machine, Makespan, VariableNeighbourhood Search