Akış tipi grup çizelgeleme problemleri için hibrit hiper sezgisel yöntem tasarımı
Hybrid hyper heuristic approach design to flowshop group scheduling problems
- Tez No: 946116
- Danışmanlar: PROF. DR. İHSAN HAKAN SELVİ, DOÇ. DR. DERYA DELİKTAŞ
- Tez Türü: Doktora
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Çizelgeleme, Üretim, Scheduling, Production
- Yıl: 2025
- Dil: Türkçe
- Üniversite: Sakarya Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Endüstri Mühendisliği Bilim Dalı
- Sayfa Sayısı: Belirtilmemiş.
Özet
Günümüzde müşteri yapısındaki değişim üreticileri düşük maliyetli, yüksek kaliteli ürünleri ürün çeşitliliğini artırarak kısa sürede üretmeye zorlamaktadır. İmalat firmalarının rakipleri arasında hayatta kalabilmesi için imalat sistemlerini optimize etmesi ve kısa sürede yüksek ürün çeşitliliğinde ürün teslimatı yapabilmesi çok önemli hâle gelmiştir. Ürün çeşitliliğinin çok olması üretim sürecinde israf olarak nitelendirilen ürünler arası değişim sürelerinin (ayar zamanı) ve taşıma zamanlarının artmasına sebep olmakta ayrıca operasyon çizelgelemenin karmaşıklaşması gibi birçok zorluğu da beraberinde getirmektedir. Bu zorlukları aşmak için geliştirilen grup teknolojisi yaklaşımıyla ürünler (işler) şekil, malzeme, üretim süreci veya diğer özelliklerindeki benzerliklere göre gruplandırılır. Planlama faaliyetleri de işlerin münferit olarak ele alınmasından ziyade gruplandırılmış işler üzerinden yapılır. Böylece ürünler arası değişim süreleri en aza indirilirken süreçler arasındaki malzeme ve mal akışı da basitleştirilmiş olur. Bu sistemlerdeki planlama faaliyetleri iki seviyeden oluşur. İlk seviyede işlem görecek grupların belirlenmesi gerekir. İkinci olarak ise her grup içindeki işlerin işlem sırası belirlenir. Bu çalışmada, işlerin gruplandığı, her makinede önceki işlem gören gruba bağlı olarak ayar zamanının değiştiği ve işlerin makineler arasında beklemediği akış tipi çizelgeleme problemine dair bir yöntem önerilmiştir. Ele alınan problem çözüm uzayı büyük olan polinom zamanlı çözülemeyen yapıdadır. Literatürde yer alan çalışmalara bakıldığında bu çalışma akış tipi sıra bağımlı işlerin makineler arası beklemediği grup çizelgeleme problemi için yapay tavşan optimizasyonu algoritması uygulayan ve memetik algoritma tabanlı hiper sezgisel yöntem geliştiren ilk çalışmadır. Yapay tavşan algoritması tavşanların doğadaki davranışından esinlenilerek geliştirilen, parametre olarak sadece iterasyon ve popülasyon sayısı içermesi avantajına sahip oldukça yeni bir algoritmadır. Bu algoritma çalışmada başlangıç popülasyonu üretme aşamasında kullanılmıştır. Yapay tavşan algoritması ile bulunan çözümler memetik algoritma tabanlı hiper sezgisel için başlangıç popülasyonunu oluşturmaktadır. Ele alınan problem için geliştirilen memetik algoritma tabanlı hiper sezgisel yöntem ise birçok algoritma konfigürasyonunu temsil edebilen (bu uygulamada 4375 konfigürasyon), geri bildirim mekanizması ile başarılı olan konfigürasyonu ödüllendirme yeteneğine sahip adaptif yapıdadır. Literatürde hiper sezgisel yöntemler sezgisel seçen yöntemler olarak tanımlanmaktadır. Bu çalışmada algoritma operatörleri olan çaprazlama, mutasyon, tepe tırmanması operatörleri ve mutasyon oranı ile arama derinliği parametreleri seçim yapılacak alt seviye sezgisellerdir. Çaprazlama için yedi farklı operatör, mutasyon ve tepe tırmanması için ise 5'er farklı operatör uygulanmıştır. Bunlara ek olarak mutasyon ve tepe tırmanması parametreleri de 5'er farklı sayısal değer olarak uygulanmıştır. Her bir adımda bu alt seviye sezgiseller içinden seçim yapılır. Seçilen operatörler/parametreler uygulandığında eldeki sonuçtan daha iyi sonuç bulunursa seçilen operatörlerin/parametrelerin puanı arttırılır (ödüllendirilir). Böylece sonraki adımlarda iyi sonuç veren operatörlerin/parametrelerin seçilme sıklığı artırılmıştır. Yapay tavşan algoritması ile başlangıç çözüm elde edilen hiper sezgisel yöntem literatürdeki 270 test problemi kullanılarak test edilmiştir. Elde edilen sonuçlar literatürdeki algoritmaların sonuçlarıyla kıyaslanmıştır. Problemde performans kriteri (amaç fonksiyonu) olarak toplam tamamlanma zamanı ele alınmıştır. Toplam tamamlanma zamanı kriteri ile işlerin son makineden ayrılma zamanları toplanarak en küçük değerin elde edilmesi amaçlanmaktadır. Bu değer algoritma performansını mevcut yöntemlerle kıyaslamada kullanılmıştır. Toplam tamamlanma zamanı eşit olan durumlarda ise sırasıyla deneylerden elde edilen ortalama ve standart sapma değerleri performans kriteri olarak kullanılmıştır. Geliştirilen yöntemin parametre optimizasyonu R tabanlı paket program olan irace algoritma konfigürasyon aracı ile yapılmıştır. Bu kapsamda popülasyon büyüklüğü, çaprazlama ve mutasyon oranı, arama derinliği, durdurma kriteri bu paket program ile belirlenen parametrelerdir. Bu parametrelere ek olarak başlangıç popülasyonunun rassal mı yoksa yapay tavşan algoritması ile mi üretilmesi gerektiği yine irace ile belirlenmiştir. Yöntem performansı literatürdeki 2, 3 ve 6 makine içeren 270 adet problem çözülerek test edilmiştir. Elde edilen sonuçlar literatürde son yıllarda geliştirilen iki yöntemle (revize edilmiş çoklu başlangıçlı simüle edilmiş tavlama benzetimi yöntemi ve bu yöntemin yerel arama içeren versiyonu) bulunan sonuçlarla kıyaslanmıştır. Geliştirilen yöntem ve literatürdeki yöntemlerle elde edilen sonuçlar arasındaki farkın anlamlı olma durumu Wilcoxon eşleştirilmiş iki örnek testi ile analiz edilmiştir. Sonuç olarak geliştirilen hibrit hiper sezgisel yöntemle daha küçük toplam tamamlanma zamanı elde edildiği sonuçlar üzerinden gösterilmiştir. Ayrıca ele alınan problem için hiper sezgisel yapıda alternatifleriyle birlikte uygulanan operatörlerden (çaprazlama için 7, mutasyon ve tepe tırmanması için ise 5'er opsiyon) iyi sonuç verenler skorları görselleştirilerek sunulmuştur. Buna ek olarak etkin çalışan mutasyon ve arama derinliği parametreleri de yorumlanarak gelecek çalışmalar için yol gösterici sonuçlar paylaşılmıştır.
Özet (Çeviri)
In today's world, the changing structure of customer demand forces manufacturers to produce low-cost, high-quality products with increased product variety in a short period of time. In order for manufacturing companies to survive among their competitors, it has become crucial to optimize their production systems and to deliver a wide variety of products in a short time. However, high product variety leads to several challenges in the production process, such as increased setup times and transportation times—considered as waste—and a more complex operation scheduling process. To overcome these challenges, the Group Technology (GT) approach has been developed, whereby products (jobs) are grouped based on similarities in shape, material, production process, or other characteristics. Planning activities are then carried out based on these grouped jobs rather than treating each job individually. In this way, setup times between products are minimized, and the flow of materials and goods between processes is simplified. Planning activities in such systems are conducted on two levels. In the first level, the groups to be processed are determined. In the second level, the processing sequence of the jobs within each group is established. In this study, a method is proposed for a flow shop scheduling problem in which jobs are grouped, setup times are sequence dependent (vary depending on the previously processed group), and jobs do not wait between machines as (no-wait constraint). The addressed problem is of a non-polynomial time solvable nature with a large solution space. The research questions for this research is as follows: ● Do hyper heuristic methodology find efficient solutions to flow shop group scheduling problems? ● Is the Artificial Rabbit Optimisation Algorithm effective in solving flow shop group scheduling problems? ● Among the crossover and mutation operators applied to flow shop group scheduling problems in the literature, which have demonstrated effective performance? ● Do the modified crossover operators applied in this study enable an effective exploration of the solution space? ● How do the results of the developed method differ from those of the methods in the literature? Based on the conducted literature review, this study is the first attempt to apply the Artificial Rabbit Optimization Algorithm and develop a memetic algorithm based hyper heuristic method for the no wait flow shop sequence dependent group scheduling problem. The artificial babbit optimization algorithm, inspired by the behavior of rabbits in nature, is a relatively new algorithm that has the advantage of requiring only iteration number and population size as parameters. This algorithm is successively applied in continous optimization problems in literature such as stock price prediction, photovoltaic system optimization and cement compressive strength estimation but this study is the first attempt to apply this methodology in to discrete problems. Artificial rabbit optimization algorithm is used at the very beginning of the designed methodology, to obtain the initial population. The set of solutions (population) found in the last iteration of the artificial rabbit optimization algorithm constitute the initial population for the memetic algorithm based hyper heuristic. They go through evolutionary processes including crossover, mutation and hill climbing. In contrast to classical memetic algorithms, in hyper heuristic design algorithm components are applied with its alternatives and algorithm evolves to choose components that has better performance than alternatives. Hyper heuristic is defined as heuristics that choose heuristic from a predefined set of low level heuristics. In this study, the algorithm operators including crossover, mutation and hill climbing are considered as low level heuristics to be selected. Seven different operators are applied for crossover, and 5 different operators are applied for mutation and hill climbing. In addition to these operators, mutation rate and search depth (hill climbing parameter) parameters are also applied by considering 5 different options and considered as low level heuristic. The performance of each low level heuristic is represented with score values in meme structure, which is formed for each chromosome. This design allows to represent various algorithm configurations in one algorithm (4375 configurations in this research) and adapt itself to choose better low level heuristics through iterations. Applying hyper heuristic includes evolutionary processes with the race between low level heuristics. In each step after having an initial population from an artificial rabbit optimization algorithm, two parent chromosomes are selected with tournament selection (tour size equals 2). This means two randomly chosen individuals are selected and the one with better fitness value is referred to as parent. This selection is done twice to choose both of the parents. Parent chromosomes go into evolutionary process crossover, mutation and hill climbing. These operators are implemented with 7, 5 and 5 alternatives respectively. Depending on this, before applying any of these operators tournament selection (tour size is 2) is conducted. This means two of the operators are selected randomly and the one with a higher score is chosen. Scores for each operator are saved in meme structure which is tailored to each chromosome. Similarly, two of the algorithm parameters including mutation rate and depth search rate are included in meme structure with their five alternatives. Similar to operator selection, two of the five alternatives are selected and the one with higher score is implemented. After having finished the iteration, fitness values of parents and children are compared. If children's fitness is lower than parents (better solution obtained) then scores for each chosen operator and parameters are increased by one. This mechanism is called reinforcement learning in the literature. Designing algorithm components with alternatives and direct iteration process with feedback mechanism construct the main body of hyper heuristic algorithm. The performance criteria (objective function or fitness value) considered is the total completion time. Total completion time should be minimized and it is calculated by adding the completion time of each job on the last machine. Parameter optimization of the designed methodology is carried out using irace, an R-based algorithm configuration tool. The values of parameters such as population size, stopping criterion, and crossover rate are determined by irace. In addition to these parameters, irace also decides whether the initial population is generated using the Artificial Rabbit Optimization algorithm or produced randomly. The performance of the method is evaluated by solving a set of 270 benchmark problems, each repeated ten times. The test instances involve 2, 3, or 6 machines, with up to 16 groups and a maximum of 117 jobs. The results obtained are compared with those of two recently developed methods proposed by Cheng et al. (2021a) in the literature. The compared methods are a revised multi-start simulated annealing algorithm and its variant enhanced with a local search procedure. The Wilcoxon signed-rank test is used to calculate p values and evaluate whether the differences between the proposed method and the literature are statistically significant. Obtained results show that designed methodology has superior performance over revised multi start simulated annealing approach with the %73 of the instances and %33 of them is statistically significant. When compared with local search enhanced variant, designed methodology has better or equal results over %57 of instances. Overall, the crossover and mutation operators that demonstrate effective performance have been identified. Moreover, it is demonstrated that the modified crossover operations perform well. The superiority of the proposed methodology over the existing revised multi-start simulated annealing algorithm and its variant enhanced with local search is also proven.
Benzer Tezler
- Dört zamanlı türbaşarj direk püskürtmeli bir dizel motorunun bilgisayar ile sümülasyonu
Computer aided simulation of a fourstroke turbocharged direct-anjection diesel engine
MUSTAFA BALCI
- Çizgisel kaynaktan ışıyan elektromağnetik dalgaların mükemmel iletken silindir takkesinden optik gibi saçılması
Başlık çevirisi yok
ADNAN GÖRÜR
Yüksek Lisans
Türkçe
1986
Makine MühendisliğiUludağ ÜniversitesiElektronik Mühendisliği Ana Bilim Dalı
DOÇ.DR. H. ERGUN BAYRAKÇI
- Drenaj sistemlerinin projelenmesinde drenaj debisinin önemi ve bu değerin Gediz Havzası koşullarında bazı meteorolijik değerlere göre hesaplanması
In the planing drainage systems, the importance of draimoge coefficient an the determination of this coeffient according to the some meteorological volues in Gediz Vailey
CEVRİ OĞUZ ACAR