A Hybrid Genetic Algorithm And Adaptive Large Neighborhood Search For Flexible Job Shop Scheduling Problem With Fuzzy Processing Time

Hariri, Firda (2025) A Hybrid Genetic Algorithm And Adaptive Large Neighborhood Search For Flexible Job Shop Scheduling Problem With Fuzzy Processing Time. Masters thesis, Institut Teknologi Sepuluh Nopember.

Text 6010222008-Master_Thesis.pdf - Accepted Version Restricted to Repository staff only Download (3MB) | Request a copy

Abstract

The Flexible Job Shop Scheduling Problem with fuzzy processing time (fFJSP) addresses scheduling under both high combinatorial complexity and uncertainty in operation durations. In this problem, each job consists of a sequence of operations, where each operation can be processed by one of several eligible machines, and each machine can handle only one operation at a time. Processing times are modeled as Triangular Fuzzy Numbers (TFNs) to better reflect real-world variability and imprecision. The objective is to minimize the maximum fuzzy completion time (fuzzy makespan), considering both routing and sequencing sub-problems. This study presents a hybrid metaheuristic that integrates an elitist Genetic Algorithm (GA) with Adaptive Large Neighborhood Search (ALNS) to tackle this challenge. The GA phase avoids crossover and instead applies structured mutations (flip, swap, slide) within a local elitism framework to diversify solutions and prevent premature convergence. After GA, ALNS is employed to refine the best solution by adaptively selecting from multiple destroy-and-repair operators. The GA-ALNS method is evaluated on benchmark instances and compared against three GA-based baselines: standalone GA, Decomposition-Integration Genetic Algorithm (DIGA), and Co-evolutionary Genetic Algorithm (CGA). Results show that GA-ALNS delivers superior or competitive performance, particularly in small to medium instances. This confirms the potential of combining global and adaptive local search to effectively solve fFJSP under uncertainty.
=================================================================================================================================
Flexible Job Shop Scheduling Problem dengan waktu proses fuzzy (fFJSP) merupakan masalah penjadwalan yang kompleks karena melibatkan kombinasi solusi yang sangat banyak serta ketidakpastian durasi proses. Dalam masalah ini, setiap job terdiri dari serangkaian operasi yang dapat dikerjakan oleh salah satu dari beberapa mesin yang memungkinkan, dan setiap mesin hanya dapat menangani satu operasi dalam satu waktu. Waktu proses dimodelkan menggunakan Triangular Fuzzy Number (TFN) untuk mencerminkan variabilitas dan ketidakpastian kondisi nyata. Tujuannya adalah meminimalkan waktu penyelesaian maksimum fuzzy (fuzzy makespan), dengan mempertimbangkan dua sub-masalah utama: penentuan mesin dan pengurutan operasi. Penelitian ini mengusulkan metode metaheuristik hibrida yang menggabungkan Genetic Algorithm (GA) dengan elitisme dan Adaptive Large Neighborhood Search (ALNS). Pada fase GA, tidak digunakan operator crossover; sebagai gantinya digunakan mutasi terstruktur (flip, swap, slide) dalam kerangka elitisme lokal untuk mencegah konvergensi dini dan menjaga keberagaman solusi. Setelah proses GA, ALNS diterapkan untuk menyempurnakan solusi terbaik dengan memilih secara adaptif berbagai kombinasi operator destroy dan repair. Metode GA-ALNS diuji pada beberapa instance benchmark dan dibandingkan dengan tiga algoritma berbasis GA lainnya: GA murni, Decomposition-Integration Genetic Algorithm (DIGA), dan Co-evolutionary Genetic Algorithm (CGA). Hasil menunjukkan bahwa GA-ALNS memberikan kinerja yang lebih unggul atau setidaknya sebanding, terutama pada instance skala kecil hingga menengah. Hal ini menunjukkan bahwa penggabungan pencarian global dan lokal adaptif dapat menjadi strategi yang efektif untuk menyelesaikan fFJSP di bawah kondisi ketidakpastian.

Item Type:	Thesis (Masters)
Uncontrolled Keywords:	Adaptive Large Neighborhood Search, Flexible Job Shop Scheduling Problem, Fuzzy Processing Time, Genetic Algorithm, Metaheuristic, Metaheuristik
Subjects:	Q Science > QA Mathematics > QA402.5 Genetic algorithms. Interior-point methods. Q Science > QA Mathematics > QA9.64 Fuzzy logic T Technology > T Technology (General) > T57.6 Operations research--Mathematics. Goal programming T Technology > T Technology (General) > T57.84 Heuristic algorithms. T Technology > TS Manufactures > TS157.5 Production scheduling
Divisions:	Faculty of Industrial Technology and Systems Engineering (INDSYS) > Industrial Engineering > 26101-(S2) Master Thesis
Depositing User:	Firda Hariri
Date Deposited:	14 Jul 2025 02:53
Last Modified:	14 Jul 2025 02:53
URI:	http://repository.its.ac.id/id/eprint/119643

Actions (login required)

View Item