Pemrograman Kendala dengan OR-Tools

1 Pendahuluan: Mengapa Pemrograman Kendala?

Dalam banyak skenario dunia nyata, kita sering dihadapkan pada masalah yang melibatkan serangkaian keputusan yang harus dibuat dengan batasan tertentu. Contohnya termasuk penjadwalan shift karyawan, menyusun jadwal pelajaran sekolah, atau mengoptimalkan rute pengiriman barang. Masalah-masalah ini dikenal sebagai masalah optimasi kombinatorial, dan seringkali sulit diselesaikan dengan pendekatan brute force atau heuristik sederhana.

Di sinilah pemrograman kendala (constraint programming) berperan — sebuah paradigma yang dirancang untuk menyelesaikan masalah seperti ini secara efisien. OR-Tools dari Google adalah toolkit open-source yang sangat kuat dan menyediakan pemecah kendala (constraint solver) serta mesin optimasi lainnya. Dalam artikel ini, kita akan mengeksplorasi bagaimana menggunakan OR-Tools dalam Python untuk memodelkan dan menyelesaikan masalah penjadwalan dengan kendala keras (hard constraints).

Contoh kasus kita: Menjadwalkan mata pelajaran ke dalam slot waktu mingguan di kelas, di mana setiap mata pelajaran memiliki jumlah jam tertentu, dan tidak boleh ada tumpang tindih mata pelajaran dalam satu kelas pada waktu yang sama.

Yuk kita mulai!

2 Mendefinisikan Masalah Penjadwalan

Kita memiliki daftar mata pelajaran dan kelas. Setiap mata pelajaran memiliki jumlah jam per minggu. Tujuan kita adalah menjadwalkan mata pelajaran ke dalam slot waktu mingguan sehingga:

1. Setiap mata pelajaran dijadwalkan sesuai jumlah jam yang dibutuhkan.
2. Setiap kelas hanya boleh memiliki satu mata pelajaran dalam satu slot.

Berikut definisi mata pelajaran dan kelas:

subjects = {
    "PAI": {"hour": 2},
    "Al-Qur'an": {"hour": 3},
    "Olahraga": {"hour": 2},
}

classrooms = ["Kelas1_C0", "Kelas1_C1"]

weekdays = ["Senin", "Selasa", "Rabu", "Kamis", "Jumat"]
hours = ["07.00", "08.00", "09.00", "10.00", "11.00", "13.00"]
slots = [(d, h) for d in weekdays for h in hours]

3 Membangun Model Kendala

Kita akan menggunakan cp_model dari OR-Tools untuk mendefinisikan variabel dan kendala.

from ortools.sat.python import cp_model

model = cp_model.CpModel()

# Variabel: is_subject_assigned[(kelas, mata pelajaran, slot)] = 1 jika dijadwalkan di slot tersebut
is_subject_assigned = {}
for cls in classrooms:
    for subj in subjects:
        for slot in slots:
            is_subject_assigned[(cls, subj, slot)] = model.NewBoolVar(f"{cls}_{subj}_{slot}")

4 Menambahkan Kendala ke Model

4.1 1. Setiap mata pelajaran dijadwalkan sesuai jumlah jamnya:

subject_slots_per_classroom_subject = {}
for cls in classrooms:
    for subj, subject in subjects.items():
        assigned_slots = [is_subject_assigned[(cls, subj, slot)] for slot in slots]
        var = model.NewIntVar(0, len(slots), f"hours_{cls}_{subj}")
        model.Add(var == sum(assigned_slots))
        model.Add(var == subject["hour"])
        subject_slots_per_classroom_subject[(cls, subj)] = var

4.2 2. Satu kelas hanya boleh memiliki satu mata pelajaran dalam satu slot:

for cls in classrooms:
    for slot in slots:
        one_subject_per_slot = [is_subject_assigned[(cls, subj, slot)] for subj in subjects]
        model.Add(sum(one_subject_per_slot) <= 1)

5 Menyelesaikan Model

Sekarang kita jalankan solver dan cetak hasil jadwal jika solusi ditemukan.

solver = cp_model.CpSolver()
status = solver.Solve(model)

if status == cp_model.FEASIBLE or status == cp_model.OPTIMAL:
    for cls in classrooms:
        print(f"\nJadwal untuk {cls}:")
        for day in weekdays:
            print(f"  {day}:")
            for hour in hours:
                slot = (day, hour)
                subject_found = False
                for subj in subjects:
                    if solver.Value(is_subject_assigned[(cls, subj, slot)]) == 1:
                        print(f"    {hour}: {subj}")
                        subject_found = True
                if not subject_found:
                    print(f"    {hour}: -")
else:
    print("Tidak ada solusi ditemukan.")

Jadwal untuk Kelas1_C0:
  Senin:
    07.00: -
    08.00: Al-Qur'an
    09.00: Al-Qur'an
    10.00: -
    11.00: -
    13.00: -
  Selasa:
    07.00: -
    08.00: -
    09.00: -
    10.00: -
    11.00: -
    13.00: Olahraga
  Rabu:
    07.00: -
    08.00: PAI
    09.00: -
    10.00: -
    11.00: -
    13.00: -
  Kamis:
    07.00: -
    08.00: -
    09.00: -
    10.00: -
    11.00: -
    13.00: -
  Jumat:
    07.00: Al-Qur'an
    08.00: PAI
    09.00: -
    10.00: -
    11.00: Olahraga
    13.00: -

Jadwal untuk Kelas1_C1:
  Senin:
    07.00: -
    08.00: -
    09.00: -
    10.00: -
    11.00: -
    13.00: -
  Selasa:
    07.00: -
    08.00: -
    09.00: -
    10.00: Al-Qur'an
    11.00: -
    13.00: -
  Rabu:
    07.00: -
    08.00: PAI
    09.00: -
    10.00: -
    11.00: -
    13.00: -
  Kamis:
    07.00: Al-Qur'an
    08.00: -
    09.00: -
    10.00: Olahraga
    11.00: Olahraga
    13.00: Al-Qur'an
  Jumat:
    07.00: -
    08.00: -
    09.00: -
    10.00: -
    11.00: -
    13.00: PAI

6 Contoh Keluaran

Contoh hasil jadwal untuk Kelas1_C0:

Jadwal untuk Kelas1_C0:
  Senin:
    07.00: PAI
    08.00: Al-Qur'an
    09.00: Al-Qur'an
    ...

(Hasil dapat berbeda tergantung bagaimana solver menetapkan slot.)

7 Kesimpulan

Kita telah memodelkan masalah penjadwalan sederhana menggunakan pemrograman kendala dengan OR-Tools. Kita:

• Mendefinisikan mata pelajaran dan kelas
• Membuat variabel keputusan biner
• Menambahkan kendala keras untuk jumlah jam dan eksklusivitas
• Menyelesaikan dan mencetak jadwal

Ini baru permulaan — kamu bisa menambahkan lebih banyak kendala seperti ketersediaan guru, preferensi waktu, atau kendala lunak (misalnya meminimalkan jeda antar pelajaran). Pemrograman kendala menawarkan pendekatan deklaratif yang kuat untuk menyelesaikan masalah penjadwalan kompleks.

7.1 🔗 Sumber Belajar

• Dokumentasi Google OR-Tools
• Contoh Python OR-Tools
• MiniZinc – sistem CP populer lainnya

Jika kamu ingin memperluas tutorial ini ke optimasi atau kendala lunak, tinggal beri tahu saya!