Deep Reinforcement Learning Hyper-Heuristic Berbasis Proximal Policy Optimization untuk Multi Objective Unrelated Parallel Machine Scheduling Problem

Rifat Rivansyah, Ir. Achmad Pratama Rifai, S.T., M.Eng, Ph.D.

2026 | Skripsi | TEKNIK INDUSTRI

Penelitian ini membahas permasalahan Multi-Objective Unrelated Parallel Machine Scheduling Problem (MOUPMSP) dengan dua fungsi tujuan, yaitu minimasi makespan dan minimasi total emisi karbon. Permasalahan ini mempertimbangkan sequence-dependent setup time (SDST), preventive maintenance (PM), dan machine eligibility, sehingga proses penjadwalan tidak hanya menentukan urutan pekerjaan, tetapi juga pemilihan mesin yang feasible dan mempertimbangkan periode maintenance. Adanya konflik antara minimasi makespan dan emisi karbon menyebabkan permasalahan ini perlu diselesaikan menggunakan pendekatan optimasi multiobjektif.

Penelitian ini mengembangkan Deep Reinforcement Learning Hyper-Heuristic berbasis Proximal Policy Optimization (DRLH-PPO) sebagai pengganti adaptive layer pada Multi-Objective Adaptive Large Neighborhood Search (MOALNS). Struktur dasar MOALNS, seperti pembentukan solusi awal, proses destroy-repair, pembaruan archive, dan mekanisme penerimaan solusi tetap dipertahankan. Perbedaan utama terletak pada mekanisme pemilihan operator, yaitu dari pemilihan berbasis bobot historis menjadi pemilihan berbasis policy PPO berdasarkan state pencarian.

Hasil eksperimen menunjukkan bahwa DRLH-PPO menghasilkan rata-rata nilai hypervolume sebesar 0,844, lebih tinggi dibandingkan MOALNS sebesar 0,799 pada seluruh dataset pengujian. Selain itu, DRLH-PPO memiliki rata-rata standar deviasi hypervolume sebesar 0,008, lebih rendah dibandingkan MOALNS sebesar 0,014, sehingga menunjukkan performa yang lebih stabil antar pengulangan. Dari sisi waktu komputasi pada instance pembanding 6×2 hingga 12×2, rata-rata waktu testing DRLH-PPO adalah 1,636 detik, lebih tinggi dibandingkan MOALNS sebesar 0,743 detik, tetapi masih lebih rendah dibandingkan metode eksak sebesar 3.102,658 detik. Dari sisi kualitas Pareto front, titik-titik solusi DRLH-PPO berada di bawah Pareto front MOALNS, sehingga menunjukkan kualitas trade-off yang lebih baik antara minimasi makespan dan minimasi total emisi karbon.

This study addresses the Multi-Objective Unrelated Parallel Machine Scheduling Problem (MOUPMSP) with two objective functions, namely the minimization of makespan and total carbon emissions. The problem considers sequence-dependent setup time (SDST), preventive maintenance (PM), and machine eligibility, so the scheduling process involves not only determining the job sequence, but also assigning jobs to eligible machines and avoiding maintenance periods. The conflict between minimizing makespan and carbon emissions requires the problem to be solved using a multi-objective optimization approach.

This study develops a Deep Reinforcement Learning Hyper-Heuristic based on Proximal Policy Optimization (DRLH-PPO) as a replacement for the adaptive layer in Multi-Objective Adaptive Large Neighborhood Search (MOALNS). The basic structure of MOALNS, including initial solution generation, the destroy-repair process, archive update, and solution acceptance mechanism, is retained. The main difference lies in the operator selection mechanism, which is changed from historical weight-based selection to PPO policy-based selection using the search state.

The experimental results show that DRLH-PPO produces an average hypervolume value of 0,844, which is higher than MOALNS with an average hypervolume value of 0,799 across all testing datasets. In addition, DRLH-PPO has an average hypervolume standard deviation of 0,008, which is lower than MOALNS with an average standard deviation of 0,014, indicating more stable performance across repeated runs. In terms of computational time on the comparative benchmark instances from 6×2 to 12×2, the average testing time of DRLH-PPO is 1,636 seconds, which is higher than MOALNS at 0,743 seconds, but remains lower than the exact method at 3.102,658 seconds. In terms of Pareto front quality, the solution points generated by DRLH-PPO are located below the MOALNS Pareto front, indicating a better trade-off quality between makespan minimization and total carbon emission minimization.

Kata Kunci : Multi-Objective Unrelated Parallel Machine Scheduling Problem, Deep Reinforcement Learning Hyper-Heuristic, Proximal Policy Optimization, Makespan, Emisi Karbon.