Evaluasi kontribusi solusi awal Heuristik terhadap performa simulated annealing pada job shop scheduling problem

INDONESIA:

Penelitian ini membahas evaluasi kontribusi solusi awal heuristik berbasis Shortest Processing Time (SPT) terhadap performa algoritma Simulated Annealing (SA) dalam menyelesaikan Job Shop Scheduling Problem (JSSP). Permasalahan JSSP merupakan masalah optimasi penjadwalan yang bertujuan meminimalkan nilai makespan dengan memperhatikan urutan operasi dan keterbatasan mesin. Penelitian ini membandingkan dua pendekatan, yaitu Simulated Annealing dengan solusi awal acak dan Simulated Annealing dengan solusi awal berbasis algoritma greedy menggunakan aturan SPT. Dataset yang digunakan adalah dataset benchmark FT06 yang terdiri atas enam pekerjaan dan enam mesin. Parameter SA yang digunakan meliputi temperatur awal sebesar 100, cooling rate sebesar 0,95, temperatur minimum sebesar 0,1, dan iterasi per suhu sebanyak 10. Evaluasi performa dilakukan melalui pengujian sebanyak 30 percobaan dengan indikator nilai makespan, stabilitas hasil, konvergensi, frekuensi pencapaian solusi terbaik, serta uji statistik menggunakan uji Mann-Whitney U. Hasil penelitian menunjukkan bahwa penggunaan solusi awal berbasis SPT memberikan performa yang lebih stabil dan menghasilkan rata-rata makespan yang lebih baik dibandingkan solusi awal acak. Selain itu, pendekatan SA berbasis SPT juga menunjukkan proses konvergensi yang lebih cepat dan konsisten dalam mencapai solusi terbaik. Namun, penggunaan solusi awal heuristik berbasis SPT belum memberikan pengaruh yang signifikan terhadap kualitas solusi akhir yang dihasilkan oleh algoritma Simulated Annealing. Hal ini menunjukkan bahwa algoritma Simulated Annealing memiliki kemampuan eksplorasi solusi yang baik. Penelitian ini diharapkan dapat memberikan kontribusi dalam pengembangan metode optimasi penjadwalan, khususnya terkait pengaruh solusi awal heuristik terhadap performa algoritma metaheuristik.

ENGLISH:

This study discusses the evaluation of the contribution of a heuristic initial solution based on Shortest Processing Time (SPT) to the performance of the Simulated Annealing (SA) algorithm in solving the Job Shop Scheduling Problem (JSSP). JSSP is a scheduling optimization problem that aims to minimize the makespan value while considering operation sequences and machine constraints. This research compares two approaches, namely Simulated Annealing with a random initial solution and Simulated Annealing with an initial solution generated using the greedy algorithm with the SPT rule. The dataset used in this study is the FT06 benchmark dataset consisting of six jobs and six machines. The SA parameters include an initial temperature of 100, a cooling rate of 0.95, a minimum temperature of 0.1, and 10 iterations per temperature level. Performance evaluation was carried out through 30 experimental runs using indicators such as makespan, result stability, convergence analysis, frequency of achieving the best solution, and statistical testing using the Mann-Whitney U test. The results indicate that the use of an SPT-based initial solution provides more stable performance and produces a better avera ge makespan compared to the random initial solution. However, the use of an SPT-based heuristic initial solution does not significantly affect the quality of the final solution produced by the Simulated Annealing algorithm. This finding indicates that Simulated Annealing possesses a strong capability to explore the solution space effectively. Furthermore, the SPT-based SA approach demonstrates faster and more consistent convergence in achieving the best solution. This study is expected to contribute to the development of scheduling optimization methods, particularly regarding the influence of heuristic initial solutions on the performance of metaheuristic algorithms.

ARABIC;

تناقش هذه الدراسة تقييم مساهمة الحل الابتدائي الاسترشادي القائم على قاعدة أقصر زمن معالجة (Shortest Processing Time - SPT) في أداء خوارزمية التلدين المحاكى(Simulated Annealing) لحل مشكلة جدولة الورش الإنتاجية. (Job Shop Scheduling Problem - JSSP)وتُعد هذه المشكلة من مسائل تحسين الجدولة التي تهدف إلى تقليل قيمة زمن الإنجاز الكلي (Makespan) مع مراعاة تسلسل العمليات والقيود المتعلقة بالآلات. تقارن الدراسة بين منهجين، هما خوارزمية التلدين المحاكى ذات الحل الابتدائي العشوائي، وخوارزمية التلدين المحاكى ذات الحل الابتدائي المبني باستخدام الخوارزمية الجشعة وفق قاعدة SPT. وقد استُخدمت مجموعة البيانات القياسية FT06 ، والتي تتكون من ست وظائف وست آلات. وشملت معلمات الخوارزمية درجة حرارة ابتدائية مقدارها ١٠٠، ومعدل تبريد مقداره ٠،٩٥، ودرجة حرارة دنيا مقدارها ٠،١، وعدد ١٠ تكرارات لكل مستوى حراري. وتم تقييم الأداء من خلال إجراء ٣٠ تجربة اعتمادًا على مؤشرات زمن الإنجاز الكلي، واستقرار النتائج، وسلوك التقارب، وتكرار الوصول إلى أفضل حل، بالإضافة إلى الاختبار الإحصائي مان–ويتني U. وأظهرت النتائج أن الحل الابتدائي القائم على قاعدة SPT يوفر أداءً أكثر استقرارًا ويحقق متوسط زمن إنجاز كلي أفضل مقارنةً بالحل الابتدائي العشوائي. كما أظهر هذا النهج سرعة أكبر واتساقًا أفضل في التقارب نحو أفضل الحلول. ومع ذلك، فإن استخدام الحل الابتدائي الاسترشادي القائم على قاعدة SPT لم يُظهر تأثيرًا معنويًا على جودة الحل النهائي الناتج عن خوارزمية التلدين المحاكى. وتشير هذه النتيجة إلى أن خوارزمية التلدين المحاكى تمتلك قدرة جيدة على استكشاف فضاء الحلول بفاعلية. ومن المتوقع أن تسهم هذه الدراسة في تطوير أساليب تحسين الجدولة، ولا سيما فيما يتعلق بتأثير الحلول الابتدائية الاسترشادية على أداء الخوارزميات الميتاهيوريستية.