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

Post a Comment

Popular posts from this blog

Aljabar Python

-
Python dapat mengoprasikan Aljabar dengan bantuan library numpy. Sedikit operasi vektor dan matriks yang penting diketahui In [1]: import numpy as np import math Vektor ¶ Penting : Bedakan ketika menulis u=[1,2,3] dan u=np.array([1,2,3]) yang pertama adalah list, yang kedua adalah vektor Tampilan vektor pada python selalu tertulis menyamping , walaupun kita tambahkan transpose, tampilan akan tetap menyamping. Hal ini sangat penting dan harus berhati-hati. u=np.array([1,2,3]) artinya $\mathbb{u}=\begin{bmatrix}1\\2\\3\end{bmatrix}$, tampilan pada python u= [1 2 3] np.transpose(u)=$\mathbb{u}^T=\begin{bmatrix}1&2&3\end{bmatrix}$, tampilan pada python u= [1 2 3] In [2]: u = [ 1 , 2 , 3 ] #ini adalah list, bukan vektor v = [ 4 , 5 , 6 ] #ini adalah list, bukan vektor print ( "List u=" , u ) print ( "List v=" , v ) print ( "Penjumlahan list : u+v
Read more

Fungsi Rekursif

-
Fungsi Rekursif ¶ Fungsi yang memanggil dirinya sendiri untuk melakukan perhitungan Faktorial Misalkan $f(n)$ menyatakan faktorial dari $n$, dengan $n$ adalah bilangan bulat lebih dari 1. Maka $f(n)=n\times (n-1)\times (n-2)\times (n-3)\times ...\times 1$ Bisa juga dituliskan dalam bentuk rekursif, yaitu $f(n)=n\times f(n-1)$ Contoh : $f(5)=5\times 4\times 3\times 2\times 1$ $f(5)=5 \times f(4)$ $f(4)=4 \times f(3)$ $f(3)=3 \times f(2)$ $f(2)=2 \times f(1)$ In [1]: #Menghitung faktorial dari n, TANPA fungsi dan tanpa rekursif print ( "Masukkan bilangan bulat lebih dari 1 yang akan dihitung faktorialnya" ) n = int ( input ()) if ( n == 0 or n == 1 ): hasil = 1 else : hasil = n print ( "n saat ini =" , n , "-hasil saat ini" , hasil ) while n >= 2 : n = n - 1 hasil = hasil * n print ( "n saat ini =" , n , "-hasil saat ini" ,
Read more

Pengolahan Matriks (manual)

-
Pengolahan Matriks dan Vektor ¶ Pada tulisan berikut, akan diberikan contoh algoritma dan program untuk mengolah matriks dan vektor tanpa menggunakan library atau fungsi yang sudah tersedia. Transpose Matriks ¶ Misalkan matriks $A=\begin{bmatrix}a_{1,1}&a_{1,2}&\cdots&a_{1,n} \\a_{2,1}&a_{2,2}&\cdots&a_{2,n} \\\vdots&\ddots&\ddots&\vdots \\a_{m,1}&a_{m,2}&\cdots&a_{m,n}\end{bmatrix}$ Transpose dari matriks $A$ adalah $A^T=\begin{bmatrix}a_{1,1}&a_{2,1}&\cdots&a_{m,1} \\a_{1,2}&a_{2,2}&\cdots&a_{m,2} \\\vdots&\ddots&\ddots&\vdots \\a_{1,n}&b_{2,n}&\cdots&a_{n,m}\end{bmatrix}$, atau $B=\begin{bmatrix}b_{1,1}&b_{1,2}&\cdots&b_{1,m} \\b_{2,1}&b_{2,2}&\cdots&b_{2,m} \\\vdots&\ddots&\ddots&\vdots \\b_{n,1}&b_{n,2}&\cdots&b_{n,m}\end{bmatrix}$ , untuk setiap $i\in\{1,2,...,m\}$ dan $j\in\{1,2,..
Read more

Contoh Fungsi : Standar Deviasi

-
Hitung Standar Deviasi dari Barisan Bilangan Bulat ¶ Diberikan sebuah barisan bilangan bulat dengan n elemen, $A = (a_1,a_2,...,a_n)$. Hitunglah standar Deviasinya. Menghitung Rata-Rata : $$\bar{a}=\frac{1}{n}\sum_{i=1}^n a_i$$ Menghitung Standar Deviasi : $$\sigma=\sqrt{\frac{1}{n-1}\sum_{i=1}^n (a_i-\bar{a})^2}$$ Algoritma Hitung Rata-Rata Deskripsi : Hitung rata-rata Masukkan : list/array dengan n elemen, Keluaran : rata-rata Langkah-langkah : Masukkan list/array bilangan, A deklarasi tempat penyimpanan jumlah, sum=0 untuk setiap i pada (1,2,...,panjang A) sum=sum+A[i] rata-rata=sum/panjang A 3. Hitung Standar Deviasi Deskripsi : Hitung Standar Deviasi Masukkan : list/array bilangan dengan n elemen, Keluaran : nilai standar deviasinya Langkah-langkah : Masukkan n (banyak elemen list/array) Buat list/array berukuran n, A Hitung rata-rata dari A, simpan pada variabel rata Masukkan list/array bilanga
Read more