Optimasi Multi-Objective untuk Unrelated Parallel Machine Scheduling Problem dengan Mempertimbangkan Setup Time, Preventive Maintenance, dan Machine Eligibility

Rafif Ariq Rabbani, Ir. Achmad Pratama Rifai, ST. M.Eng, Ph.D

2026 | Skripsi | TEKNIK INDUSTRI

Penelitian ini membahas permasalahan Multi-Objective Unrelated Parallel Machine Scheduling Problem (MOUPMSP) dengan mempertimbangkan dua fungsi tujuan, yaitu minimasi makespan dan minimasi emisi karbon. Permasalahan penjadwalan pada parallel machine ini juga memperhitungkan sequence-dependent setup time (SDST), machine eligibility, serta waktu preventive maintenance (PM). Kompleksitas permasalahan meningkat karena adanya trade-off antara waktu penyelesaian produksi dan emisi karbon yang dihasilkan sehingga diperlukan pendekatan optimasi multi-objective untuk memperoleh himpunan solusi Pareto.

Penelitian ini mengembangkan model Mixed Integer Linear Programming (MILP) yang diselesaikan menggunakan metode eksak. Namun, seiring meningkatnya ukuran instance, kompleksitas komputasi metode eksak menjadi sangat tinggi. Oleh karena itu, dikembangkan algoritma Multi-Objective Adaptive Large Neighborhood Search (MOALNS) sebagai pendekatan metaheuristik. Mekanisme MOALNS melibatkan kombinasi operator destroy-repair yang dipilih berdasarkan skema pembaruan bobot, penerapan Metropolis Criterion, serta evaluasi performa solusi menggunakan indikator Hypervolume (HV).

Hasil eksperimen menunjukkan bahwa algoritma MOALNS mampu menghasilkan solusi yang mendekati Pareto front metode eksak pada instance berukuran kecil. Pada instance yang lebih besar, algoritma MOALNS tetap mampu menghasilkan solusi berkualitas dalam waktu komputasi yang feasible sehingga menunjukkan potensi yang baik untuk diterapkan pada permasalahan penjadwalan skala besar.

This study addresses the Multi-Objective Unrelated Parallel Machine Scheduling Problem (MOUPMSP) by considering two objective functions, namely the minimization of makespan and carbon emissions. The scheduling problem in this parallel machine environment also takes into account sequence-dependent setup time (SDST), machine eligibility, and preventive maintenance (PM) time. The complexity of the problem increases due to the trade-off between production completion time and the resulting carbon emissions, thereby requiring a multi-objective optimization approach to obtain a set of Pareto solutions.

This study develops a Mixed Integer Linear Programming (MILP) model that is solved using an exact method. However, as the instance size increases, the computational complexity of the exact method becomes significantly higher. Therefore, a Multi-Objective Adaptive Large Neighborhood Search (MOALNS) algorithm is developed as a metaheuristic approach. The MOALNS mechanism involves a combination of destroy-repair operators selected based on a weight updating scheme, the implementation of the Metropolis Criterion, and the evaluation of solution performance using the Hypervolume (HV) indicator.

The experimental results show that the MOALNS algorithm is capable of generating solutions that closely approximate the Pareto front obtained by the exact method for small-sized instances. For larger instances, the MOALNS algorithm remains capable of producing high-quality solutions within feasible computational times, demonstrating strong potential for application to large-scale scheduling problems.

Kata Kunci : Multi-Objective Optimization Problem, Unrelated Parallel Machine Scheduling Problem, Sequence-Dependent Setup Times, Preventive Maintenance, Machine Eligibility, MILP, MOALNS, Makespan, Emisi Karbon