PENJADWALAN KEGIATAN BELAJAR MENGAJAR SEKOLAH MENENGAH ATAS MENGGUNAKAN ALJABAR MAX-PLUS

PROSIDING SEMINAR NASIONAL SAINS DAN PENDIDIKAN SAINS UKSW

PENJADWALAN KEGIATAN BELAJAR MENGAJAR SEKOLAH MENENGAH ATAS MENGGUNAKAN ALJABAR MAX-PLUS Yustinus Hari Suyanto1, Subiono2 Graduate of Student Department of Mathematic ITS, Surabaya 1

[email protected], [email protected]

ABSTRAK Penyusunan jadwal mengajar di SMAK St. Louis 1 lebih mengacu pada ketersediaan tenaga pengajar bukan berdasar pembagian bobot kesulitan pelajaran. Hal ini tentunya sangat merugikan anak didik karena memungkinkan terjadinya jadwal pelajaran dimana dalam satu hari mendapatkan jadwal pelajaran dengan bobot kesulitan yang sangat tinggi sehingga siswa mengalami kesulitan dan akhirnya hasilnya tidak optimal. Dalam tesis ini akan disusun suatu penjadwalan kegiatan belajar mengajar yang mengacu pada pembagian yang merata dalam hal bobot kesulitan materi pelajaran. Penjadwalan ini dimaksudkan agar dengan tenaga pengajar yang tersedia dapat dibuat jadwal dengan lebih mengacu pada pembagian bobot kesulitan jenis pelajaran yang merata sehingga anak didik tidak dirugikan. Dalam penyusunannya nanti akan digunakan teori aljabar max-plus untuk mendapatkan jadwal yang sesuai. Kata kunci : ketersedian tenaga pengajar, bobot kesulitan pelajaran, aljabar maxplus. Y

PENDAHULUAN Masalah penyusunan jadwal kegiatan belajar mengajar di sekolah dari tahun ke tahun selalu muncul pada awal tahun ajaran. Sampai saat ini banyak sekolah yang didalam penyusunan jadwal sekolah dengan sistem manual tanpa melakukan perhitungan antara kebutuhan kegiatan belajar mengajar dengan sarana yang ada baik ruang kelas maupun guru pengajar. Sering kali suatu jadwal disusun dan dicoba penerapannya dan bila terdapat kesalahan maka diperbaiki lagi dan dicoba lagi dengan perbaikan sampai akhirnya dapat dijalankan,dan akibatnya kegiatan belajar mengajar sering terganggu. Terdapat suatu anggapan jadwal dikatakan benar jika jadwal setelah dijalankan tidak terjadi seorang guru mengajar di dua kelas pada saat yang bersamaan, padahal setelah dikaji lebih mendalam didalam jadwal tersebut masih banyak kelemahan diantaranya kurang optimalnya pemanfaatan ruang kelas dan pembagian jenis pelajaran yang tidak merata yaitu ada suatu kelas pada hari yang sama mendapatkan jenis mata pelajaran yang begitu banyak sehingga anak didik dibebani jenis pelajaran yang banyak. Dengan adanya sekian banyak jenis mata pelajaran dengan bobot kesulitan yang berbeda dan saling berkaitan satu dengan yang lain maka diharapkan di dalam jadwal pelajaran terdapat pembagian bobot kesulitan pelajaran yang merata dengan mengacu kekuatan dan kemampuan anak didik sebagai subyek pendidikan. Kendala utama dalam penyusunan jadwal pelajaran adalah tidak semua tenaga pengajar adalah guru tetap yang selama satu hari jam kerja berada di sekolah, sehingga sering kali penyusunan jadwal lebih mengacu pada ketersediaan jam tenaga pengajar bukan pada pembagian bobot kesulitan pelajaran. Dalam penjadwalan perlu mengatur sedemikian rupa ada perimbangan antara tenaga pengajar tiap mata pelajaran dengan waktu mengajar yang dibutuhkan, ruang belajar dengan rombongan belajar yang ada, dan perimbangan antar tenaga pengajar dan rombongan belajar yang ada sehingga prosess pembelajaran dapat berjalan dengan baik (Telehala (2010)). Dalam tesis ini akan disusun suatu penjadwalan kegiatan belajar mengajar yang mengacu pada pembagian yang merata dalam hal bobot kesulitan materi pelajaran. PM8-1

PROSIDING SEMINAR NASIONAL SAINS DAN PENDIDIKAN SAINS UKSW 1. ALJABAR MAX-PLUS Aljabar Max-Plus terdiri dari himpunan Rmax  R   ,, (Goverde 2005) dengan R adalah himpunan bilangan real dan    yang dikaitkan dengan dua operasi maksimum (max) dan tambah (+), dengan notasi  menyatakan operasi maksimum dan  menyatakan operasi tambah, sehingga untuk suatu operasi terhadap dua variabel a dan b yaitu a  b berarti max(a,b) dan a  b berarti a + b. Notasi  dan  pada Aljabar Max-Plus masing-masing mempunyai kemiripan dengan operasi tambah (+) dan kali (x) pada aljabar biasa. Definisi 2.1 Diberikan Rmax  R   ,,  dengan    . Pada R , a, b  R didefinisikan sebagai operasi berikut: a  b  max a, b  dan a  b  a  b : i. R   ,,  merupakan semiring komutatif idempoten dengan elemen netral    dan elemen satuan e = 0. ii. R   ,,  merupakan semifield, yaitu bahwa R   ,,  merupakan semiring komutatif di mana untuk setiap a  R terdapat  a sehingga berlaku a   a   0 . Untuk selanjutnya R   ,,  disebut dengan Aljabar Max-Plus(Goverde (2005)), yang dinotasikan dengan Rmax . Relasi  m yang didefinisikan pada Rmax sebagai berikut x y jika x  y  y , merupakan urutan parsial pada Rmax. Lebih lanjut relasi ini merupakan urutan total pada Rmax . Pangkat k dari elemen k 1

a  R dilambangkan x  dengan x   0, x   x  x  . k

0

k

Definisi 2.2 Operasi  dan  pada Rmax dapat diperluas untuk operasi-operasi matriks dalam

  



mn mn mn dengan Rmax untuk i  1,2,  , m dan j  1,2,  , n sehingga : Rmax  A  Aij Aij  Rmax mn i. Untuk A, B  Rmax didefinisikan A  B , dengan  A  B ij  aij  bij .





mn ii. Untuk A, B  Rmax didefinisikan A  B , dengan  A  B ij   kp1 ai ,k  bk , j .

iii. E 

mn Rmax

dengan

E   0,,

jika i  j

jika i  j  mn iv. Matriks   Rmax dengan  ij   ,  ij ij

2. DEFINISI GRAPH DALAM ALJABAR MAX-PLUS Diberikan graph berarah G=(V,A) dengan V adalah suatu himpunan berhingga tak kosong yang anggotanya disebut titik dan A adalah suatu himpunan pasangan terurut titik-titik pada garis V. Suatu lintasan dalam graph berarah G adalah suatu barisan berhingga garis i1 , i2 , i2 , i3 ,  , il 1 , il , dengan ik , ik 1   A untuk l  N , di mana N = himpunan semua bilangan asli, dan k  1,2,  , l  1 . Titik i1 disebut titik awal lintasan dan titik it disebut titik akhir lintasan. Suatu lintasan disebut sirkuit jika titik awal dan titik akhirnya sama. Suatu graph berarah G=(V,A) dengan V = 1, 2, , ... , n dikatakan strongly connected jika untuk setiap i, j  V ,terdapat suatu lintasan dari i ke j. Suatu graph yang memuat sirkuit disebut graph siklik, sedangkan suatu graph yang tidak memuat sirkuit disebut graph taksiklik.

PM8-2

PROSIDING SEMINAR NASIONAL SAINS DAN PENDIDIKAN SAINS UKSW Graph berarah G dikatakan berbobot jika setiap garis  j , i   A dikawankan dengan suatu bilangan real Aij . Bilangan real Aij disebut bobot garis  j, i  dilambangkan dengan w j , i  . mn Graph preseden dari matriks A  Rmax adalah graph berarah berbobot G(A)=(V,A) dengan

V=1,2,...,n,

A

 j, i  wi, j   A

ij



  , i, j . Sebaliknya untuk setiap graph berarah

berbobot G = (V, A) selalu dapat didefinisikan suatu matriks A dengan w , jika i, j   A Aij   ij   , jika i, j   A 3. SISTEM LINEAR MAX-PLUS WAKTU INVARIANT Diberikan suatu parameter ”k” untuk menyatakan suatu kejadian. Untuk memberikan arti parameter k ini, diberikan gambaran pada suatu jaringan-kerja(network), yang terdiri dari beberapa titik dan beberapa ruas garis berarah yang menghubungkan titik-titik tersebut. Jaringan-kerja yang bersesuaian mempunyai n titik yang diwakili oleh setiap xi , sedangkan Aij bersesuaian dengan ruas garis berarah dari titik x j ke titik xi . Setiap titik dalam jaringan kerja mempunyai aktifitas tertentu. Aktifitas-aktifitas ini membutuhkan waktu hingga yang dinamakan waktu aktifitas. Diasumsikan bahwa aktifitas suatu titik hanya dapat dimulai bila semua titik hulunya, yaitu titik yang mendahuluinya secara langsung, telah menyelesaikan aktifitasnya dan mengirimkan hasilnya sepanjang ruas garis berarah yang menghubungkannya. Jadi ruas garis berarah yang bersesuaian dengan Aij dapat ditafsirkan sebagai saluran output titik x j dan sebagai saluran input titik xi . Diasumsikan juga bahwa titik x j memulai aktifitasnya sesegera mungkin setelah semua aktifitas titik hulunya mengirimkan hasilnya ke titik xi . Jadi dengan menganggap aktifitas sebagai kejadian, tafsiran besaran yang digunakan adalah: i. xi k  : waktu saat awal titik xi menjadi aktif pada kejadian ke-k. ii. Aij : jumlah waktu aktifitas titik x j dan lamanya waktu perjalanan dari titik x j ke titik xi (Baccelli, F.; et.al; 1992). Sistem Linear Max-PlusWaktu-Invariant Definisi (Sistem Linear Max-Plus Waktu-Invariant (SLMI), Scutter, 1996) Sistem Linear Max-Plus Waktu-Invariant adalah Sistem Kejadian Diskrit (SKD) (Braker (1993)) yang dapat dinyatakan dengan persamaan berikut: xk  1  A  xk   B  u k  1  y k   C  xk   mn mn mn untuk k =1,2,3,... dengan keadaan awal x0   x 0 , A  Rmax , B  Rmax , C  Rmax .

n m Vektor xk   Rmax menyatakan keadaan (state), u k   Rmax adalah vektor input dan

l adalah vektor output saat sistem waktu ke-k. y k   Rmax Definisi Jika A sebarang matrik bujur sangkar berordo n  n , dan vektor v   ,  ,  ,  T dan terdapat bilangan  sehingga berlaku A  x    x , maka disebut eigen vektor dari A dan  disebut nilai eigen dari A. Algoritma untuk menentukan nilai eigen dan vektor eigen dari matriks dilakukan secara berulang dari bentuk persamaan linear : xk  1  A  xk  dengan k = 0,1,2,… Algoritma menentukan nilai eigen dan vektor eigen (Subiono, 2010, hal.31) sebagai berikut : i. Mulai dari sebarang vector awal x0   

PM8-3

PROSIDING SEMINAR NASIONAL SAINS DAN PENDIDIKAN SAINS UKSW ii. Iterasi persamaan (1) sampai ada bilangan bulat p  q  0 dan bilangan real c sehingga suatu perilaku periodik terjadi, yaitu x p   c  xq  c iii. Hitung nilai eigen dengan   , pq





iv. Hitung vektor eigen dengan v   ip1q  p  q i   xq  i  1

4. APLIKASI ALJABAR MAX-PLUS PADA PENYUSUNAN JADWAL KEGIATAN BELAJAR MENGAJAR. Misalkkan ada tiga kelas yaitu kelas-A, kelas –B dan kelas C diajar oleh 3 guru yaitu guru1, guru2 dan guru3. Guru1 mengajar tiga kelas secara bergantian dengan waktu sebagai berikut: 2 jam pertama @ 45 menit di kelas A, pindah ke kelas B diselingi istirahat selama 30 menit kemudian pindah ke kelas C sehingga graph nya sebagai berikut : B

x1 k 

A

x 2 k  120’

90’

x3 k 

C

90’

Guru2 mengajar tiga kelas secara bergantian dengan waktu sebagai berikut: 2 jam pertama @ 45 menit di kelas B, pindah ke kelas C diselingi istirahat selama 30 menit kemudian pindah ke kelas A sehingga graph nya sebagai berikut : x 4 k 

C

x5 k  120’

90’

x 6 k 

B

A

90’

Guru3 mengajar tiga kelas secara bergantian dengan waktu sebagai berikut: 2 jam pertama @ 45 menit di kelas C, pindah ke kelas A diselingi istirahat selama 30 menit kemudian pindah ke kelas C sehingga graph nya sebagai berikut : x 7 k 

A

120’

90’

C

x8 k 

x9 k  90’

B

Kepindahan guru1 dari kelas A ke kelas B harus menunggu kepindahan guru1 dari kelas C ke kelas A, kepindahan dari kelas B ke kelas C harus menunggu kepindahan dari kelas A ke kelas B demikian selanjutnya sehingga persamaan model kepindahan guru1:

x1 k  1  90  x3 k    x 2 k  1  90  x1 k   x3 k  1  120  x 2 k 

Dengan cara yang sama maka kepindahan guru2 didapat persamaan model kepindahan guru 2 sebagai berikut :

PM8-4

PROSIDING SEMINAR NASIONAL SAINS DAN PENDIDIKAN SAINS UKSW

x 4 k  1  90  x6 k    x5 k  1  90  x 4 k   x6 k  1  120  x5 k  Selanjutnya persamaan model kepindahan guru3 :

x7 k  1  90  x9 k    x8 k  1  90  x7 k   x9 k  1  120  x8 k 

Dari ketiga persamaan diatas dilakukan sinkronisasi dengan aturan bahwa seorang guru hanya dapat mengajar disatu kelas dan sebuah kelas hanya diajar oleh seorang guru. Selanjutnya dilakukan sinkronisasi sebagai berikut: 1. Kepindahan guru1 dari kelas A ke kelas B harus menunggu kepindahan guru2 dari kelas B ke kelas C. 2. Kepindahan guru1 dari kelas B ke kelas C harus menunggu kepindahan guru3 dari kelas C ke kelas A dan kepindahan guru2 dari C ke kelas A. 3. Kepindahan guru2 dari kelas B ke kelas C harus menunggu kepindahan guru3 dari kelas C ke kelas A. 4. Kepindahan guru2 dari kelas C ke kelas A harus menunggu kepindahan guru1 dari kelas A ke kelas B dan kepindahan guru3 dari A ke kelas B . 5. Kepindahan guru3 dari kelas C ke kelas A harus menunggu kepindahan guru1 dari kelas A ke kelas C. 6. Kepindahan guru3 dari kelas A ke kelas B harus menunggu kepindahan guru1 dari kelas B ke kelas C dan kepindahan guru2 dari B ke kelas C. Sehingga persamaan model sinkronisasi kepindahan guru adalah sebagai berikut : x1 k  1  max90  x3 k ,90  x 4 k  x 2 k  1  max90  x1 k ,120  x5 k   90  x7 k   max90  x1 k ,210  x5 k   x7 k 

x3 k  1  120  x 2 k  x 4 k  1  max90  x6 k ,90  x7 k  x5 k  1  max90  x 4 k ,120  x8 k   90  x1 k 

 max90  x 4 k ,210  x1 k   x8 k 

x6 k  1  120  x5 k  x7 k  1  max90  x9 k ,90  x1 k  x8 k  1  max90  x7 k ,120  x 2 k   90  x 4 k 

 max90  x7 k ,210  x 2 k   x 4 k 

x9 k  1  120  x8 k  Dari persamaan diatas dapat dituliskan menjadi :

PM8-5

PROSIDING SEMINAR NASIONAL SAINS DAN PENDIDIKAN SAINS UKSW  x1 k  1     90 90        x1 k           210  210     x 2 k   x 2 k  1  90  x3 k  1   120          x3 k            90 90     x 4 k   x 4 k  1    x k  1  210   90    210     x5 k   5         120       x 6 k   x 6 k  1             90  x 7 k   x 7 k  1  90   x8 k  1   210  210   90     x8 k              120    x9 k   x9 k  1  

Selanjutnya dicari eigen vector dan nilai eigen dengan maxplus scilabs toolbook didapatkan : A = -Inf -Inf 90. 90. -Inf -Inf -Inf -Inf -Inf 90. -Inf -Inf -Inf 210. -Inf 210. -Inf -Inf -Inf 120. -Inf -Inf -Inf -Inf -Inf -Inf -Inf -Inf -Inf -Inf -Inf -Inf 90. 90. -Inf -Inf 210. -Inf -Inf 90. -Inf -Inf -Inf 210. -Inf -Inf -Inf -Inf -Inf 120. -Inf -Inf -Inf -Inf 90. -Inf -Inf -Inf -Inf -Inf -Inf -Inf 90. -Inf 210. -Inf 210. -Inf -Inf 90. -Inf -Inf -Inf -Inf -Inf -Inf -Inf -Inf -Inf 120. -Inf -->[l,d,v]=maxplusmaxalgol(A) v = 1. d = 210. 420. 330. 210. 420. 330. 210. 420. 330. l = 210. Dari scilabs didapat nilai eigen 210 yang artinya jadwal akan periodic setelah 210 menit. Untuk mempermudah perhitungan eigenvector maka elemennya dijadikan nol dengan mengurangkan semua elemennya dengan nilai elemen terkecilnya sehingga didapatkan d_new=d-min(d) d_new = 0. 210. 120. 0. 210. 120. 0. 210. 120. Yang artinya bahwa jika perpindahan guru1 dari kelas A ke kelas B pada pukul 07.00 maka perpindahan guru1 dari kelas B ke kelas C adalah 07.00+ 210’=10.30 dan perpindahan guru1 PM8-6

PROSIDING SEMINAR NASIONAL SAINS DAN PENDIDIKAN SAINS UKSW dari kelas C ke kelas A adalah 07.00+120’=09.00 demikian seterusnya untuk perpindahan guru2. Dan akhirnya didapat jadwal perpindahan guru sebagai berikut : Pukul Kelas-A Kelas-B Kelas-C 07.00-07.45 1 2 3 07.00-08.30 1 2 3 08.30-09.15 3 1 2 09.15-09.45 Istirahat 09.45-10.30 3 1 2 10.30-11.15 2 3 1 11.15-12.00 2 3 1 DAFTAR PUSTAKA Braker,J.G.(1993), Algorithms and Application in Timed Discrete Event Systems, PhD thesis,DELFT,University of Technology, The Netherlands. Goverde, R.M.P (2005), Railway Timetable Stability Analysis using Max-plus System Theory, Journal of Transportation, No: B 41 hal: 179-201. Heidergott,B., Olsder G.J., dan Wousde, J.V.D.j (2006), Max Plus at Work Modeling and Analysis of Synchronisotion, Princetion University Press, New Jersey. Subiono (2000), On classes of min-max-plus systems and their applications, Delft University Press Netherlands. Subiono (2010), Aljabar Max-plus dan Terapannya, Jurusan Matematika ITS,Surabaya. Telehala (2010), Model Penjadwalan Kegiatan Pembelajaran Sekolah pada Kelas Moving dengan Menggunakan Aljabar maxplus, Jurusan Matematika ITS,Surabaya.

PM8-7