Model Jadwal Guru

Masalah Penjadwalan Guru di Sekolah

Pada tulisan ini, akan diuraikan salah satu model matematika untuk penjadwalan guru di sekolah.
Pendekatan yang digunakan pada model ini adalah penugasan guru yang dipasangkan ke slot waktu mengajar yang tersedia.
Pada tulisan ini tidak dilakukan optimisasi untuk meminimumkan banyak guru. InsyaAllah tulisan terkait ini akan menyusul :)

Data Penjadwalan

  • Setiap guru ditugaskan mengajar suatu mata pelajaran, dengan beban tertentu, pada kelas tertentu
  • Setiap kelas memiliki slot banyak sesi belajar untuk setiap harinya

Model Penjadwalan KBM Pada Sekolah

Pembuatan jadwal mengajar guru pada dasarnya adalah membuat jadwal yang memenuhi kendala. (Tahap berikutnya adalah optimisasi dari jadwal tersebut)
Terdapat dua kategori kendala :

  1. Kendala yang tidak boleh dilanggar (hard constraint). Kendala ini terbagi menjadi dua kategori
    • Kendala dasar, kendala yang selalu ada di setiap sekolah
    • Kendala tambahan, kendala yang hanya terjadi di kasus-kasus tertentu
  2. Kendala yang boleh dilanggar (soft constraint)
    • Contoh kasus : Kepala sekolah sebisa mungkin hanya mengajar mulai sesi ke 3, apabila kondisi tidak memungkinkan maka kepala sekolah boleh mengajar pada sesi-2.
    • Kendala ini belum diimplementasikan pada tulisan ini.

Hard Constraint

Kendala dasar

  1. Dalam sepekan, banyaknya sesi guru mengajar di suatu kelas sama dengan banyaknya sesi mengajar yang telah ditugaskan di kelas tersebut
  2. Setiap guru maksimal mengajar satu kelas pada hari dan sesi yang sama
  3. Pada setiap kelas terdapat tepat seorang guru pada hari dan sesi yang sama
    • Tidak boleh ada kelas yang kosong di suatu sesi
  4. Setiap guru hanya mengajar satu kali di suatu kelas untuk hari dan sesi yang sama

Kendala Tambahan (1)

  1. Guru tidak boleh mengajar lebih dari 6 sesi per hari

Kendala tambahan lain :

  • Beberapa pasang guru tidak diperbolehkan mengajar pada hari dan sesi yang sama
    • Contoh kasus : Terdapat 3 guru olahraga, tetapi lapangan yang tersedia hanya ada satu, sehingga tidak diperbolehkan mengajar pada waktu yang sama.
  • Beberapa pasang guru wajib mengajar pada hari dan sesi yang sama
    • Terdapat mata pelajaran yang harus dilaksanakan pada sesi yang sama karena suatu alasan tertentu.
    • Misalkan Guru 1 mengajar mata pelajaran matematika di kelas A dan Guru 1 mengajar mata pelajaran matematika di kelas B, jadwal KBM harus dilaksanakan pada hari sesi yang sama.

Soft Constraint

Model Matematika

Misalkan $x_{t,c,d,s}$ merupakan variabel keputusan

$x_{t,c,d,s}=\begin{cases}1, \text{ apabila guru ke-}t\text{ mengajar pada kelas ke-}c\text{ pada hari ke-}h\text{ sesi ke-}s \\0, \text{ apabila guru/mata pelajaran ke-}t\text{ TIDAK mengajar pada kelas ke-}c\text{ pada hari ke-}h\text{ sesi ke-}s\end{cases}$
Misalkan :

  • $nt$ menyatakan banyak guru di suatu sekolah
  • $nc$ menyatakan banyak kelas di suatu sekolah
  • $nd$ menyatakan banyak hari dalam sepekan
  • $ns$ menyatakan banyak sesi dalam sehari
  • $T_{g,c}$ menyatakan banyak sesi yang ditugaskan kepada guru ke-$g$ pada kelas ke-$c$


Misalkan :

  • $T$ menyatakan himpunan guru di suatu sekolah
  • $C$ menyatakan himpunan kelas di suatu sekolah
  • $D$ menyatakan himpunan hari dalam sepekan
  • $S$ menyatakan himpunan sesi dalam sehari

minimumkan $\displaystyle f(x)=\sum_{t=1}^{nt} \sum_{c=1}^{nc} \sum_{d=1}^{nd} \sum_{s=1}^{ns} x_{t,c,d,s}$
Terhadap kendala (dasar) :

  1. Untuk setiap guru, untuk setiap kelas, $\displaystyle \sum_{d=1}^{nd} \sum_{s=1}^{ns} x_{t,c,d,s}= T_{g,c}$
  2. Untuk setiap setiap kelas, untuk setiap hari, untuk setiap sesi, $\displaystyle \sum_{t=1}^{nt} x_{t,c,d,s}\leq 1$
  3. Untuk setiap kelas, untuk setiap hari, untuk setiap sesi, $\displaystyle \sum_{t=1}^{nt} x_{t,c,d,s}= 1$
  4. Untuk setiap guru, untuk setiap kelas, untuk setiap hari, $\displaystyle \sum_{s=1}^{ns} x_{t,c,d,s}\leq 1$

Kendala Tambahan :

  1. Untuk setiap guru, untuk setiap hari, $\displaystyle \sum_{d=1}^{nd} \sum_{c=1}^{nc} x_{t,c,d,s}\leq 6$

karena belum terdapat soft constraint fungsi objektifnya hanya akanmencari sosuli feasibel saja.

Latihan :)

Kendala Tambahan
Formulasikan kendala untuk :

  1. Pasangan guru yang tidak boleh mengajar bersamaan pada hari dan sesi yang sama
  2. Pasangan guru yang harus mengajar bersamaan pada hari dan sesi yang sama
  3. Sesi mengajar diatur sedemikian rupa sehingga dalam 1 pertemuan diusahakan menjadi 2 sesi.
    Kendala ini akan menggantikan kendala tambahan nomor 4

    • Contoh (1) : Tugas mengajar dalam kelas A adalah 4 sesi (4 jam pelajaran). Maka guru tersebut akan mengajar di kelas A dibagi menjadi 2 pertemuan yaitu (2-2), masing-masing pertemuan 2 sesi (2 jam pelajaran).
    • Contoh (2) : Tugas mengajar dalam kelas A adalah 5 sesi (5 jam pelajaran). Maka guru tersebut akan mengajar di kelas A dibagi menjadi 3 pertemuan yaitu (2-2-1) atau (2-1-2) atau (1-2-2)
  4. Sesi mengajar diatur sedemikian rupa sehingga dalam 1 pertemuan diusahakan menjadi 3 sesi (3 jam pelajaran).
    Kendala ini akan menggantikan kendala tambahan nomor 4

    • Contoh (3) : Tugas mengajar dalam kelas A adalah 5 sesi (5 jam pelajaran). Maka guru tersebut akan mengajar di kelas A dibagi menjadi 2 pertemuan yaitu (2-3) atau (3-2).
    • Contoh (4) : Tugas mengajar dalam kelas A adalah 6 sesi (6 jam pelajaran). Maka guru tersebut akan mengajar di kelas A dibagi menjadi 2 pertemuan yaitu (3-3), masing-masing pertemuan adalah 3 sesi (3 jam pelajaran)
  5. Pemisah untuk sesi waktu istirahat.
    Misalkan istirahat dijadwalkan setelah sesi ke-5 dan sebelum sesi ke-6. Oleh karena itu tidak diperbolehkan mata pelajaran yang sama mengambil sesi ke-5 dan 6 sebagai waktu belajarnya.

Selain membuat modelnya, tuliskan juga bagaimana data masukkan yang harus dimasukkan oleh user :)

Comments

Popular posts from this blog

Aljabar Python

MA3071 : Algoritma Newton & Conjugate Gradien

Contoh Fungsi : Standar Deviasi

Contoh Program Linear di Python & R