Çizelgeleme algoritmalarının çalışma sürelerinin ileri veri yapıları ile iyileştirilmesi

Abstract

Günümüzde gelişen teknoloji ve artan ürün çeşitliliği işletmelerin rekabet ortamında hayatta kalabilmeleri için süreçlerinde iyileşme yapmalarını gerektirmektedir. Bu yüzden, işletmelerin sınırlı kaynaklarını daha etkin kullanabilmeleri için üzerinde çokça durduğu önemli bir konu da çizelgelemedir. Üretim sürecinde zaman tasarrufu elde etmek ya da bir sürecin daha kısa sürede tamamlanmasını sağlayarak sahip olunan sınırlı kaynakların verimini arttırmak adına iyileştirme sürecine yönelik çizelgeleme algoritmaları günümüzün en popüler çözüm yöntemlerindendir. Ancak çizelgeleme algoritmaları gerçek sistemler üzerinde uygulanmak istediğinde, çözüm süreleri uzamakta ve bugünün bilgisayar hızlarında bile gerçek hayatta uygulanabilir sürelerde çözüm sağlanamamaktadır. Çizelgeleme algoritmalarının gerçek hayatta uygulalanabilir olması adına, bu çalışmanın amacı; teknolojik gelişmelere rağmen çözülemeyen çok büyük boyutlu çizelgeleme algoritmalarının ileri veri yapılarıyla performansını iyileştirmektir. Bu nedenle çalışmada liste ve bağlı liste yapılarına sahip iki adet algoritma önerilmiştir. Veri yapısının algoritma çözüm hızına çok önemli etkisi mevcuttur ve özellikle çok büyük boyutlu problemler üzerinde bu etki daha iyi görüleceği için sentetik veriler oluşturulmuştur. Esnek atölye tipi çizelgeleme problemi üzerinden farklı parametreleri de dikkate almaya çalışarak üç senaryo tasarlanmıştır. Bu senaryolara göre liste ve bağlı liste veri yapılarına sahip algoritmaların çalışma süreleri açışından performansları değerlendirilmiştir. İleri veri yapısı içeren algoritmanın, temel veri yapısına sahip algoritmaya göre bütün senaryolar için istatistiksel olarak anlamlı bir farkla daha hızlı çalıştığı gözlenmiştir. Diğer çizelgeleme algoritmalarına, özellikle popülasyon tabanlı algoritmalara, uygulandığında CPU işlem süresinin düşeceği ön görülmektedir

Nowadays, developing technology and increasing product diversity require businesses to improve their processes in order to survive in competitive environments. Therefore, an businesses focus on scheduling to effectively use their limited resources. Scheduling algorithms are one of the most popular solution methods today in order to save time in the production processes or to increase the efficiency of limited resources by ensuring that a process is completed in a shorter time. However, when scheduling algorithms are applied, the solution durations are extensively large and applicable results cannot be attained in real time. In order to make scheduling algorithms applicable in real-time, the aim of study is to improve the performance of very large scheduling algorithms that cannot be solved despite technological developments with advanced data structures. Two algorithms, one with listdaha straucture, and the second with linked list data structure, were proposed. The data structures have a very important effect on the algorithm solution speed, and therefore synthetic data were created to show their effect especially on very large sized problems. The performances of the algorithms with two different data structures were evaluated in terms of running times. Three scenarios were designed with different parameters, and algorithms were written according to these scenarios with list and linked list data structures. It has been observed that the algorithm with the advanced data structure Works statistically significantly faster for all scenarios than the algorithm with basic data structure. It is predicted that CPU processing time will decrease when applied to other scheduling algorithms, especially population-based algorithms.