PENYELESAIAN MASALAH PENJADWALAN MATA PELAJARAN SEKOLAH MENENGAH PERTAMA MENGGUNAKAN PEMROGRAMAN LINEAR INTEGER MAHNURI

PENYELESAIAN MASALAH PENJADWALAN MATA PELAJARAN SEKOLAH MENENGAH PERTAMA MENGGUNAKAN PEMROGRAMAN LINEAR INTEGER

MAHNURI

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2009

ABSTRAK MAHNURI. Penyelesaian Masalah Penjadwalan Mata Pelajaran Sekolah Menengah Pertama Menggunakan Pemrogramam Linear Integer. Dibimbing Oleh TONI BAKHTIAR dan PRAPTO TRI SUPRIYO.

Jadwal mata pelajaran pada Sekolah Menengah Pertama merupakan bagian yang sangat penting. Tujuan penyusunan jadwal adalah untuk menempatkan mata pelajaran dalam penjadwalan sesuai dengan klasifikasinya dan memenuhi preferensi guru dalam mengajar serta memenuhi kendala lainnya. Dalam karya ilmiah ini, preferensi dan kendala diakomodasi oleh koefisien bobot yang diberikan terhadap mata pelajaran dan guru. Masalah penjadwalan di sini diformulasikan sebagai masalah minimisasi. Pemberian kerangka bobot yang kecil terhadap mata pelajaran dan guru menunjukkan periode waktu yang diinginkan dalam penjadwalan, begitu juga sebaliknya. Masalah penjadwalan dalam karya ilmiah ini dimodelkan sebagai masalah pemrograman linear integer (Integer Linear Programing/ILP) dan untuk menyelesaiakan masalah penjadwalan di sini digunakan software Lingo 8.0. Hasil dari penelitian ini adalah jadwal mata pelajaran lengkap untuk Sekolah Menengah Pertama “Masa Depan”.

ABSTRACT MAHNURI. Courses Scheduling Problem at Junior High School with Integer Linear Programming. Supervised by TONI BAKHTIAR and PRAPTO TRI SUPRIYO.

The course scheduling at junior high school is an important task. The purpose of course scheduling is to allocate courses according to their classification and to satisfy teachers preferences on teaching and other constraints. In this paper, the preferences and constraints are accommodated by means of coefficients as weights attached into courses as well as teachers. The problem is formulated as a minimization problem. The preferences and constraints with smaller weights framework indicate more preffered time periods, and vice versa. The scheduling problem in this paper is modeled in term of integer linear programming (ILP) and Lingo 8.0 is used to solve the problem. The result of the research is a fully defined schedule for “Masa Depan” junior high school.

PENYELESAIAN MASALAH PENJADWALAN MATA PELAJARAN SEKOLAH MENENGAH PERTAMA MENGGUNAKAN PEMROGRAMAN LINEAR INTEGER

Skripsi Sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor

Oleh : MAHNURI

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2009

Judul

: Penyelesaian Masalah Penjadwalan Mata Pelajaran Sekolah Menengah Pertama menggunakan Pemrograman Linear Integer

Nama

: Mahnuri

NIM

: G54104064

Menyetujui,

Pembimbing I

Pembimbing II

Dr. Toni Bakhtiar, M.Sc. NIP 19720627 199702 1 002

Drs. Prapto Tri Supriyo, M.Kom. NIP 19630715 199002 1 002

Mengetahui, Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor

Dr. Drh. Hasim, DEA. NIP 19610328 198601 1 002

Tanggal Lulus :

KATA PENGANTAR Puji dan syukur penulis panjatkan ke hadirat Allah Azza wa Jalla atas segala nikmat, karunia, izin, dan pertolongan-NYA sehingga penulisan skripsi ini berhasil diselesaikan. Shalawat serta salam tercurah kepada nabi Muhammad Shalallohu‘alaihi wasalam sebagai suri tauladan terbaik bagi umatnya hingga akhir zaman. Tema yang dipilih adalah Riset Operasi dengan judul Penyelesaian Masalah Penjadwalan Mata Pelajaran Sekolah Menengah Pertama Menggunakan Pemrogramam Linear Integer. Skripsi ini merupakan syarat untuk menyelesaikan studi pada Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Terima kasih penulis ucapkan kepada : 1. Bapak Dr. Toni Bakhtiar, M.Sc. dan Bapak Drs. Prapto Tri Supriyo, M.Kom. selaku dosen pembimbing, atas segala kesabaran dan masukannya selama membimbing penulis. Tak lupa kepada Bapak Drs. Siswandi, M.Si. selaku penguji, saran dan kritikan beliau sangat berharga buat penulis. 2. Ibunda Sinah dan bapak Kamso atas doa, nasehat, dan pengorbanan yang telah diberikan sampai saat ini yang tidak mungkin penulis balas dengan kebaikan apapun. Mbah (Alm.) Martawireja dan Mbok Sarkem atas kasih sayang dan bimbangan yang sangat berharga bagi kehidupan penulis. Adiku Siska dan Firman atas kasih sayang dan dukungan yang telah diberikan. 3. Teman-teman mahasiswa matematika angkatan 41: Udin, Grit, Aji, Fred, Racil, Idris, Triyadi, Yaya, Deni, Chubby, Mimin, Fariz, Zali, Mazid, Iboy, Amin, Dika, Racum, Yos, Mora, Hendri, Fitrie, Endhit, Sita, Rita, Diah, Dian, Liay, Sifa, Mukti, penny, Uwie, Ani, Liam, darwisah, Jannah, Ami, Intan, Enyon, Echi, Ria, Enny, Roma, Titis, Tia, Febrina., Ayu, Ika, Mahar, Eli, Rina Z, Eva, Roro, Nidia, atas segenap dukungan, suka-duka dan kebahagiaan selama penulis menempuh studi di Departemen Matematika IPB. 4. Sumar”dD”Wati atas dukungan dan bantuan yang telah diberikan. Teh Mayang atas bantuan yang telah diberikan. Warno, Sapto, dan Iput selaku pembahas, semoga cepat menyusul. Danar, Jaukhul, dan Sai atas persahabatan dan suka duka yang telah kita lalui bersama selama kurang lebih tiga tahun. 5. Teman-temanku di Wisma At-Tauhid : Hasan, Angga, Dimas, Ari, Abrar, Huri, Akhid, Yusuf, Dian, dan Mas Eko; di Wisma Al-Ghuroba : Rusmanto, Iksani, Fauzi, Aris, Joko, ngaToif, Risma, Irsal, dan Sarwanto; di Wisma Al-Furqon : Frendy, Bombai, Sugara, Mas Anri, Mas Wiji, dan Rifki; di wisma Al-Izzah : Auriza, dan Abdul atas persahabatan yang telah kalian berikan. Semoga tetap terjalin dan senantiasa dalam perlindunga-NYA. 6. Keluarga besar GUMATIKA periode 2006-2008 atas berbagai pengalaman yang kita lalui bersama. 7. Juga pihak-pihak lain yang telah membantu penyusunan skripsi ini, yang tidak dapat disebutkan satu persatu. Semoga Allah Azza wa Jalla mengganjar kalian dengan kebaikan. Penulis menyadari bahwa dalam tulisan ini masih terdapat kekurangan dan jauh dari kesempurnaan, oleh karena itu penulis mengharapkan kritik dan saran yang membangun dari pembaca. Semoga tulisan ini dapat bermanfaat.

Bogor, Juni 2009

Mahnuri

RIWAYAT HIDUP Penulis dilahirkan di Bogor pada tanggal 23 Mei 1986 dari pasangan Kamso dan Sinah. Penulis merupakan anak pertama dari tiga bersaudara. Penulis memulai pendidikan di Sekolah Dasar Negeri 1 Karanganyar pada tahun 1992-1998. Selanjutnya di Sekolah Menengah Pertama Negeri 1 Jatilawang pada tahun 1998-2001. Kemudian penulis melanjutkan pendidikan di Sekolah Menengah Umum Negeri 5 Purwokerto pada tahun 2001-2004. Pada tahun 2004-2009 penulis melanjutkan pendidikan di Institut Pertanian Bogor Fakultas Matematika dan Ilmu Pengetahuan Alam Departemen Matematika. Selama mengikuti kegiatan perkuliahan penulis aktif dalam HIMPRO (Himpunan Profesi) kemahasiswaan. Penulis aktif di HIMPRO GUMATIKA (Himpunan Profesi Gugus Mahasiswa Matematika) pada tahun 2005-2007. Penulis juga aktif dalam kegiatan kemahasiswaan diantaranya adalah Matematika Ria pada tahun 2006 (Sekretaris), Try Out SPMB Nasional pada tahun 2007 (Ketua), Matematika Ria pada tahun 2007 (Ketua). Pada tahun 2006-2007 penulis menjadi asisten tutorial mata kuliah Pengantar Matematika dan Kalkulus.

DAFTAR ISI

Halaman DAFTAR TABEL ........................................................................................................................ viii DAFTAR GAMBAR ................................................................................................................... viii DAFTAR LAMPIRAN ................................................................................................................. viii 1 PENDAHULUAN Latar Belakang ......................................................................................................................... 1 Tujuan ...................................................................................................................................... 1 2 LANDASAN TEORI Fungsi Linear dan Pertidaksamaan Linear ............................................................................... Pemrograman Linear ................................................................................................................ Pemrograman Integer ................................................................................................................ Metode Branch-and-Bound ......................................................................................................

1 2 3 3

3 DESKRIPSI DAN FORMULASI MASALAH........................................................................... 7 4 STUDI KASUS DAN PENYELESAIAN ................................................................................. 11 5 SIMPULAN DAN SARAN Simpulan ................................................................................................................................ 16 Saran ...................................................................................................................................... 16 DAFTAR PUSTAKA ................................................................................................................... 16 LAMPIRAN ................................................................................................................................... 17

DAFTAR TABEL Halaman 1 Daftar mata pelajaran untuk masing-masing kelas beserta periode waktu yang dibutuhkan ...................................................................................................................... 2 Distribusi KBM dengan 10 kelas ............................................................................................. 3 Daftar periode waktu KBM ..................................................................................................... 4 Hari guru mengajar .................................................................................................................. 5 Permintaan periode waktu mengajar ........................................................................................ 6 Jadwal KBM SMP Masa Depan untuk setiap kelas ............................................................... 7 Jadwal mengajar guru untuk setiap hari dan setiap periode waktunya ....................................

11 11 12 12 13 18 19

DAFTAR GAMBAR Halaman 1 Daerah fisibel untuk LP-relaksasi dari masalah ILP (6) ............................................................ 5 2 Daerah fisibel untuk Subproblem 2 dan Subproblem 3 .............................................................. 5 3 Seluruh pencabangan pada metode branch and bound untuk menentukan solusi optimal dari ILP .............................................................................................................. 6 4 Bobot untuk mata pelajaran inti .................................................................................................. 8 5 Bobot untuk mata pelajaran biasa ............................................................................................... 8 6 Bobot untuk guru-guru yang mengajarkan mata pelajaran inti dan mata pelajaran biasa ........................................................................................................................... 8 7 Bobot untuk mata pelajaran yang diharapkan diajarkan di awal periode waktu ....................................................................................................................................... 13 8 Bobot untuk mata pelajaran yang diharapkan diajarkan di akhir periode waktu ........................................................................................................................................ 13 9 Bobot untuk mata pelajaran yang diharapkan diajarkan di periode waktu awal dan periode waktu akhir .................................................................................................. 13 10 Bobot untuk mata pelajaran yang diharapkan diajarkan di periode waktu pertengahan .............................................................................................................................. 14 11 Bobot untuk guru dengan preferensi mengajar di akhir periode waktu, kalau tidak terpenuhi menginginkan di awal periode waktu ............................................................. 14 12 Bobot untuk guru dengan preferensi mengajar di awal periode waktu, kalau tidak terpenuhi menginginkan di akhir periode waktu ............................................................ 14 13 Bobot untuk guru dengan preferensi mengajar di awal dan di akhir periode waktu ....................................................................................................................................... 14

DAFTAR LAMPIRAN Halaman 1 Jadwal Kegiatan Belajar Mengajar (KBM) yang Terbentuk untuk SMP Masa Depan .............................................................................................................................. 18 2 Syntax Program LINGO 8.0 untuk Menyelesaikan Masalah Pemrograman Linear dengan Metode Branch-and-Bound Beserta Hasil yang Diperoleh .............................. 24 3 Syntax dan Hasil Komputasi Program LINGO 8.0 untuk Masalah Penjadwalan Sekolah Menengah Masa Depan ......................................................................... 27

viii

I PENDAHULUAN Latar Belakang Sekolah merupakan salah satu bagian penting dalam pendidikan. Oleh karena itu sekolah harus memperhatikan bagian-bagian yang ada di dalamnya. Salah satu bagian penting yang tidak dapat dipisahkan dalam sekolah adalah masalah penjadwalan mata pelajaran. Oleh sebab itu perlu dibuat sebuah penjadwalan mata pelajaran berkualitas yang memuaskan guru, murid dan sekolah. Salah satu sekolah yang mempunyai masalah penjadwalan mata pelajaran adalah Sekolah Menengah Pertama (SMP). Pada setiap SMP mata pelajaran yang diajarkan sesuai dengan kurikulum yang berlaku. Mata pelajaran yang diajarkan ada yang nantinya diujikan dalam Ujian Akhir Nasional (UAN), untuk selanjutnya kita sebut sebagai mata pelajaran inti (primary) dan ada pula mata pelajaran yang tidak diujikan dalam UAN, melainkan hanya diujikan oleh sekolah masing-masing atau biasa disebut Ujian Akhir Sekolah (UAS), untuk selanjutnya kita sebut sebagai mata pelajaran biasa (nonprimary). Begitu pula dengan gurunya, ada yang mengajar mata pelajaran inti, ataupun mata pelajaran biasa, namun ada pula yang mengajar keduanya. Setiap guru mempunyai

preferensi hari dan periode waktu dalam memberikan mata pelajaran yang akan diajarkannya. Atas dasar perbedaan di atas, masalah penjadwalan mata pelajaran akan dibuat. Masalah penjadwalan mata pelajaran di sini dapat dimodelkan sebagai masalah pemrograman linear integer (Integer Linear Programing/ILP). ILP adalah masalah optimisasi dengan fungsi objektif dan kendala yang linear serta variabel integer. Karya ilmiah ini merupakan rekonstruksi dari karya ilmiah T Birbas, S Daskalaki, dan E Housos (1997) yang berjudul “Timetabling for Greek high schools”. Dalam karya ilmiah ini akan diperlihatkan formulasi dan penyelesaian masalah penjadwalan mata pelajaran menggunakan bantuan software LINGO 8.0. Tujuan Tujuan penulisan karya ilmiah ini adalah menunjukan peranan pemrograman linear integer dalam menentukan penjadwalan mata pelajaran Sekolah Menengah Pertama yang memenuhi preferensi mata pelajaran dan preferensi guru.

II LANDASAN TEORI Dalam menyelesaikan masalah penjadwalan mata pelajaran pada karya ilmiah ini digunakan suatu model ILP untuk proses penyelesaiannya. Supaya lebih memahami dalam pembuatan model ILP dan proses penyelesaiannya, beberapa definisi dan teori yang terkait dengan ILP perlu dijelaskan terlebih dahulu. Berikut ini akan dijelaskan definisi dan teori yang digunakan Fungsi Linear dan Pertidaksamaan Linear Fungsi linear dan pertidaksamaan linear merupakan salah satu konsep dasar yang harus dipahami terkait dengan konsep pemrograman linear. Definisi 1 (Fungsi Linear) f ( x1 , x 2 ,..., x n ) Suatu fungsi

dalam

variabel-variabel x1 , x2 ,..., xn adalah suatu fungsi linear jika dan hanya jika untuk suatu

himpunan konstanta c1 , c2 ,..., cn , dapat ditulis sebagai; f ( x1 , x 2 ,..., x n ) = c1 x1 + c 2 x 2 + ... + c n x n . (Winston, 2004) Sebagai gambaran, f ( x1 , x2 ) = 3 x1 + 5 x2 merupakan fungsi linear, sementara f ( x1 , x2 ) = x12 x 23 bukan fungsi linear. Definisi 2 (Pertidaksamaan Linear) Untuk sembarang fungsi linear f ( x1 , x 2 ,..., x n ) dan sembarang bilangan b ,

f ( x1 , x 2 ,..., x n ) ≤ b dan f ( x1 , x 2 ,..., x n ) ≥ b adalah pertidaksamaan linear. (Winston, 2004)

pertidaksamaan

Pemrograman Linear Pemrograman linear (PL) adalah suatu masalah optimisasi yang memenuhi ketentuan-ketentuan sebagai berikut. a) Tujuan masalah tersebut adalah memaksimumkan atau meminimumkan suatu fungsi linear dari sejumlah variabel keputusan. Fungsi yang akan dimaksimumkan atau diminimumkan ini disebut fungsi objektif. b) Nilai variabel-variabel keputusannya harus memenuhi suatu himpunan kendala. Setiap kendala harus berupa persamaan linear atau pertidaksamaan linear. c) Ada pembatasan tanda untuk setiap variabel dalam masalah ini. Untuk sembarang variabel x i , pembatasan tanda menentukan x i harus taknegatif ( x i ≥ 0) . (Winston, 2004) Suatu PL mempunyai bentuk standar seperti yang didefinisikan sebagai berikut. Definisi 3 (Bentuk Standar PL) Suatu pemrograman linear didefinisikan mempunyai bentuk standar sebagai berikut: min z = c Tx terhadap Ax = b x ≥ 0. (1) di mana b ≥ 0. Dengan x dan c berupa vektor berukuran n, vektor b berukuran m, sedangkan A berupa matriks berukuran m x n yang disebut juga matriks kendala. (Nash & Sofer, 1996) Solusi Pemrograman Linear Suatu masalah PL dapat diselesaikan dalam berbagai teknik, salah satunya adalah metode simpleks. Metode ini dapat menghasilkan suatu solusi optimal bagi masalah PL dan telah dikembangkan oleh Dantzig sejak tahun 1947, dan dalam perkembangannya merupakan metode yang paling umum digunakan untuk menyelesaikan PL. Metode ini berupa metode iteratif untuk menyelesaikan PL berbentuk standar. Pada masalah PL (1), vektor x yang memenuhi kendala Ax = b disebut solusi PL (1). Misalkan matriks A dapat dinyatakan sebagai A = ( B N ) , dengan B adalah matriks berukuran m × m yang elemennya berupa koefisien variabel basis dan N merupakan matriks berukuran m × (n − m) yang elemen-elemennya berupa koefisien variabel nonbasis pada matriks kendala.

Dalam hal ini matriks B disebut matriks basis untuk PL (1). Misalkan x dapat dinyatakan sebagai x  vektor x =  B  , dengan xB adalah vektor  xN  variabel basis dan x N adalah vektor variabel nonbasis, maka Ax = b dapat dinyatakan sebagai : x  Ax = ( B N )  B   xN  (2) = Bx B + Nx N = b. Karena matriks B adalah matriks taksingular, maka B memiliki invers, sehingga dari (2) x B dapat dinyatakan sebagai: x B = B -1b - B -1 Nx N .

(3)

Definisi 4 (Solusi Basis) Solusi dari suatu masalah PL disebut solusi basis jika memenuhi syarat berikut: a) Solusi tersebut memenuhi kendala pada masalah PL. b) Kolom-kolom dari matriks kendala yang berpadanan dengan komponen taknol dari solusi tersebut adalah bebas linear. (Nash & Sofer, 1996) Definisi 5 (Solusi Fisibel Basis) Vektor x disebut solusi fisibel basis jika x merupakan solusi basis dan x ≥ 0. (Nash & Sofer, 1996)

Ilustrasi solusi basis dan solusi fisibel basis diberikan dalam Contoh 1. Contoh 1 Misalkan diberikan masalah LP sebagai berikut min z = -3 x1 - 2 x2

-2 x1 + x2 + x3 = 3

terhadap

-x1 + 2 x2 + x4 = 8

x1 + x5 = 5 xi ≥ 0 , i = 1, ..., 5 .

(4)

Dari masalah LP (4) diperoleh:  −2 1 1 0 0   3     A =  −1 2 0 1 0  , b =  8  .  1 0 0 0 1     5 Misalkan dipilih

xB = ( x3 x4 x5 ) dan x N = ( x1 maka matriks basisnya adalah T

x2 ) , T

1 0 0   B = 0 1 0 . 0 0 1   Dengan menggunakan matriks basis di atas didapatkan

xN = ( 0 0 ) , xB = B −1b = ( 3 8 5) . (5) Solusi (5) merupakan solusi basis, karena memenuhi kendala pada LP (4) dan kolomkolom pada matriks kendala yang berpadanan dengan komponen taknol dari (5), yaitu B bebas linear (kolom yang satu bukan merupakan kelipatan dari kolom yang lain). Solusi (5) juga merupakan solusi fisibel basis, karena nilai-nilai variabelnya lebih dari atau sama dengan nol. Hal yang juga penting dalam konsep pemrograman linear untuk model ini adalah daerah fisibel dan solusi optimal yang didefinisikan sebagai berikut. T

T

Definisi 6 (Daerah Fisibel) Daerah fisibel untuk suatu LP adalah himpunan semua titik yang memenuhi semua kendala dan pembatasan tanda pada LP tersebut. (Winston, 2004) Definisi 7 (Solusi Optimal) Untuk masalah maksimisasi, solusi optimal suatu LP adalah suatu titik dalam daerah fisibel dengan nilai fungsi objektif terbesar. Untuk masalah minimisasi, solusi optimal suatu LP adalah suatu titik dalam daerah fisibel dengan nilai fungsi objektif terkecil. (Winston, 2004) Pemrograman Integer Pemrograman integer (Integer Programing/IP) adalah suatu model pemrograman linear dengan variabel yang digunakan berupa bilangan bulat (integer). Jika semua variabel harus berupa integer, maka masalah tersebut dinamakan pure integer programming. Jika hanya sebagian yang harus berupa integer, maka disebut mixed integer programming. IP dengan semua variabelnya harus bernilai 0 atau 1 disebut 0-1 IP. (Garfinkel & Nemhauser, 1972) Definisi 8 (Linear Programming Relaksasi) Linear Programming relaksasi atau sering disebut LP-relaksasi merupakan suatu pemrograman linear yang diperoleh dari suatu

IP dengan menghilangkan kendala integer atau kendala 0-1 pada setiap variabelnya. Untuk masalah maksimisasi, nilai optimal fungsi objektif LP-relaksasi lebih besar atau sama dengan nilai optimal fungsi objektif IP, sedangkan untuk masalah minimisasi, nilai optimal fungsi objektif LP-relaksasi lebih kecil atau sama dengan nilai optimal fungsi objektif IP. (Winston, 1995) Metode Branch-and-Bound Dalam penulisan karya ilmiah ini, untuk memperoleh solusi optimal dari masalah ILP digunakan software LINGO 8.0 yaitu sebuah program yang didesain untuk aplikasi riset operasi dalam membangun dan menentukan solusi model linear, nonlinear, dan optimisasi integer dengan salah satu prinsip pemecahannya berdasarkan metode branch and bound. Branch and bound adalah algoritma umum untuk mencari solusi optimal dari berbagai masalah optimasi. Metode ini pertama kali diperkenalkan oleh A.H. Land dan A.G. Doig pada tahun 1960. Prinsip dasar metode ini adalah memecah daerah fisibel suatu masalah LP-relaksasi dengan membuat subproblem-subproblem. Ada dua konsep dasar dalam algoritme branch and bound. 1. Branching Branching adalah proses membagi-bagi permasalahan menjadi subproblemsubproblem yang mungkin mengarah ke solusi. 2. Bounding Bounding adalah suatu proses untuk mencari/menghitung batas atas (dalam masalah minimisasi) dan batas bawah (dalam masalah maksimisasi) untuk solusi optimal pada subproblem yang mengarah ke solusi, di sini dilakukan LP-relaksasi pada ILP. Metode branch and bound diawali dengan menyelesaikan LP-relaksasi dari suatu masalah integer programming. Jika semua nilai variabel keputusan solusi optimal sudah berupa integer, maka solusi tersebut merupakan solusi optimal ILP. Jika tidak, dilakukan pencabangan dan penambahan batasan pada LP-relaksasinya kemudian diselesaikan. Winston (2004) menyebutkan bahwa nilai fungsi objektif optimal untuk ILP ≤ nilai fungsi objektif optimal untuk LP-relaksasi (masalah maksimisasi), sehingga nilai fungsi objektif optimal LP-relaksasi merupakan batas

atas bagi nilai fungsi objektif optimal untuk masalah ILP. Diungkapkan pula oleh Winston (2004) bahwa nilai fungsi objektif optimal untuk suatu kandidat solusi merupakan batas bawah nilai fungsi objektif optimal untuk masalah ILP asalnya. Suatu kandidat solusi diperoleh jika solusi dari suatu subproblem sudah memenuhi kendala integer pada masalah ILP, artinya semua variabelnya sudah bernilai integer. Berikut ini adalah langkah-langkah penyelesaian suatu masalah maksimisasi dengan metode branch-and-bound. 1) Langkah 0 Didefinisikan z sebagai batas bawah dari nilai fungsi objektif (solusi) ILP yang optimal. Pada awalnya ditetapkan z = −∞ dan i = 0. 2) Langkah 1 Subproblem LP(i ) dipilih sebagai bagian masalah berikutnya untuk Subproblem LP(i ) diselesaikan.

dipecahkan.

a) Jika LP(i ) terukur dan solusi PL yang ditemukan lebih baik maka batas bawah z diperbarui. Jika tidak, bagian masalah (subproblem) baru i dipilih dan langkah 1 diulangi. Jika semua subproblem telah dipecahkan, maka proses dihentikan. b) Jika LP(i ) tidak terukur, proses dilanjutkan ke langkah 2 untuk melakukan pencabangan LP(i ) . Suatu subproblem dikatakan terukur (fathomed) jika terdapat kondisi sebagai berikut. 1. Subproblem tersebut takfisibel, sehingga tidak dapat menghasilkan solusi optimal untuk ILP. 2. Subproblem tersebut menghasilkan suatu solusi optimal dengan semua variabelnya bernilai integer. Jika solusi optimal ini mempunyai nilai fungsi objektif yang lebih baik daripada solusi fisibel yang diperoleh sebelumnya, maka solusi ini menjadi kandidat solusi optimal dan nilai fungsi objektifnya menjadi batas bawah nilai fungsi objektif optimal bagi masalah ILP pada saat itu. Bisa jadi subproblem ini menghasilkan solusi optimal untuk masalah ILP.

3. Nilai fungsi objektif optimal untuk subproblem tersebut tidak melebihi batas bawah saat itu, maka subproblem ini dapat dieliminasi. 3). Langkah 2 Dipilih salah satu variabel x j yang nilai optimalnya adalah x*j yang tidak memenuhi batasan integer dalam solusi LPi . Bidang

[ x *j ] < x j < [ x *j ] + 1

disingkirkan

dengan

membuat dua subproblem PL, yaitu x j < [ x *j ] dan x j > [ x *j ] + 1 , sehingga diperoleh kendala subproblem baru sebagai berikut: • Subproblem baru 1: kendala subproblem lama + kendala x j ≤ [ x*j ] • Subproblem baru 2: kendala subproblem lama + kendala x j ≥ [ x*j ] + 1 dengan [ x *j ] didefinisikan sebagai integer terbesar yang kurang dari atau sama dengan x *j . Selanjutnya kembali ke langkah 1. (Winston, 1975) Untuk memudahkan pemahaman metode branch-and-bound diberikan contoh sebagai berikut. Contoh 2 (Metode Branch-and-Bound) Misalkan diberikan masalah ILP sebagai berikut : max z = 4 x1 + 7 x2 terhadap x1 + x2 ≤ 7 5 x1 + 9 x2 ≤ 45

xi ≥ 0 , i = 1, 2 .

(6)

Setelah diselesaiakan menggunakan software LINGO 8.0 didapatkan solusi optimal LPrelaksasi dari masalah ILP (6) adalah x1 = 4.5 , x2 = 2.5 , dan z = 35.5 (lihat Lampiran 2). Batas atas nilai optimal fungsi objektif masalah ini adalah 35.5. Daerah fisibel LPrelaksasi masalah (6) ditunjukkan pada Gambar 1. Solusi optimal berada pada titik perpotongan dua garis yang berasal dari kendala pertidaksamaan masalah (6).

Sekarang dipilih subproblem yang belum diselesaikan. Misalkan dipilih Subproblem 2, solusi optimal untuk Subproblem 2 adalah x1 = 5 , x2 = 2 , dan z = 34 (lihat Lampiran 2). Semua variabel bernilai integer (solusinya memenuhi kendala bilangan bulat), maka tidak perlu dilakukan pencabangan di Subproblem 2. Solusi dari Subproblem 2 menjadi batas bawah yaitu sama dengan 34. Saat ini Subproblem yang belum diselesaiakan adalah Subproblem 3. Solusi optimal untuk Subproblem 3 adalah x1 = 3.6 , Gambar 1 Daerah fisibel untuk LPrelaksasi dari masalah ILP (6).

Langkah berikutnya adalah memartisi daerah fisibel LP-relaksasi menjadi dua bagian berdasarkan variabel yang berbentuk pecahan (non integer). Karena nilai dari kedua variabel yang diperoleh bukan integer, maka dipilih salah satu variabel untuk dasar pencabangan. Misalkan dipilih x2 sebagai dasar pencabangan. Jika masalah LP-relaksasi diberi nama Subproblem 1, maka pencabangan tersebut menghasilkan 2 subproblem, yaitu: • Subproblem 2: Subproblem 1 ditambah kendala x2 ≤ 2 ; • Subproblem 3: Subproblem 1 ditambah kendala x2 ≥ 3. Secara grafis dapat dilihat pada gambar di bawah ini.

Gambar 2 Daerah fisibel Subproblem 2 dan Subproblem 3.

untuk

Setiap titik (solusi) fisibel dari IP (6) termuat dalam daerah fisibel Subproblem 2 atau Subproblem 3. Setiap subproblem ini saling lepas. Subproblem 2 dan Subproblem 3 dikatakan dicabangkan oleh x2 .

x2 = 3 , dan z = 35.4 (lihat Lampiran 2). Karena solusi optimal Subproblem 3 bukan solusi integer dan masih mempunyai kemungkinan solusi lebih besar dari batas bawah, maka dipilih pencabangan pada Subproblem 3 pada x1 , sehingga diperoleh dua subproblem lagi. • Subproblem 4: Subproblem 3 ditambah kendala x1 ≤ 3 • Subproblem 5: Subproblem 3 ditambah kendala x1 ≥ 4 Sekarang dipilih Subproblem yang belum diselesaikan yaitu Subproblem 4 atau Subproblem 5. Subproblem 5 takfisibel (lihat Lampiran 2), maka subproblem ini tidak dapat optimal. menghasilkan solusi Subprolem yang belum diselesaiakan adalah Subproblem 4. Setelah diselesaiakan solusi optimal yang didapatkan untuk Subproblem 4 adalah x1 = 3 , x2 = 3.3 , dan z = 35.3 . Solusi dari subproblem 4 tidak integer dan lebih baik dari batas bawah, maka dipilih pencabangan pada Subproblem 4 sehingga diperoleh subproblem baru lagi • Subproblem 6: Subproblem 4 ditambah kendala x2 ≤ 3 • Subproblem 7: Subproblem 4 ditambah kendala x2 ≥ 4 Solusi optimal untuk Subproblem 6 adalah x1 = 3 , x2 = 3 , z = 33 (lihat Lampiran 2). Solusi optimal untuk Subproblem 6 memenuhi solusi integer, akan tetapi solusi pada Subproblem ini lebih kecil (tidak lebih baik) dari batas bawah sehingga solusi pada Subproblem 6 tidak menjadi batas bawah baru. Subproblem 7 menghasilkan solusi optimal x1 = 1.8 , x2 = 4 , z = 35.2 (lihat Lampiran 2). Solusi dari Subproblem 7 tidak integer dan lebih baik dari batas bawah, maka pada Subproblem ini dilakukan pencabangan lagi sehingga diperoleh Subproblem baru lagi

• Subproblem 8: Subproblem 7 ditambah kendala x1 ≤ 1 • Subproblem 9: Subproblem 7 ditambah kendala x1 ≥ 2 Penyelesaian dari Subproblem 9 menghasilkan solusi yang takfisibel (lihat Lampiran 2), maka subproblem ini tidak dapat menghasilkan solusi optimal. Subproblem 8 menghasilkan solusi optimal x1 = 1 , x2 = 4.4 , z = 35.1 (lihat Lampiran 2). Solusi dari Subproblem 8 tidak integer dan lebih baik dari batas bawah, maka pada Subproblem ini dilakukan pencabangan lagi sehingga diperoleh Subproblem baru lagi • Subproblem 10: Subproblem 8 ditambah kendala x2 ≤ 4 • Subproblem 11: Subproblem 8 ditambah kendala x2 ≥ 5

Subproblem 10 menghasilkan solusi optimal x1 = 1 , x2 = 4 , z = 32 . Subproblem ini menghasilkan solusi integer, akan tetapi solusi yang dihasilkan pada subproblem ini tidak lebih baik dari batas bawah sehinggga solusi pada Subproblem 10 tidak menjadi batas bawah baru. Subproblem 11 menghasilkan solusi optimal x1 = 0 , x2 = 5 , Solusi pada Subproblem ini z = 35 . menghasilkan solusi integer dan lebih baik dari batas bawah sehingga solusi pada Subproblem 11 menjadi batas bawah baru. Karena sudah tidak ada lagi subproblem baru yang dapat dibuat maka tidak perlu dilakukan pencabangan lagi. Dengan demikian, solusi optimal pada contoh 2 adalah x1 * = 0 ,

x2 * = 5 , z = 35 . Secara keseluruhan pencabangan semua Subproblem untuk masalah ILP pada contoh 2 ditunjukan pada gambar di bawah ini.

Subproblem 1 x1=4.5, x2=2.5, z=35.5 x2 ≥ 3

x2 ≤ 2

Subproblem 3

Subproblem 2

x1=3.6, x2=3, z=35.4

x1=5, x2=2, z=34

x1 ≥ 4

x1 ≤ 3

Subproblem 5

Subproblem 4

Solusi takfisibel

x1=3, x2=3.3, z=35.3 x2 ≤ 3

x2 ≥ 4

Subproblem 6

Subproblem 7

x1=3, x2=3, z=33

x1=1.8, x2=4, z=35.2 x1 ≤ 1

x1 ≥ 2

Subproblem 8

Subproblem 9

x1=1, x2=4.4, z=35.1

Solusi takfisibel

x2 ≤ 4

x2 ≥ 5

Subproblem 10

Subproblem 11

x1=1, x2=4, z=32

x1*=0, x2*=5, z=35

Gambar 3 Seluruh pencabangan pada metode branch and bound untuk menentukan solusi optimal dari ILP.

III DESKRIPSI DAN FORMULASI MASALAH Jadwal Kegiatan Belajar Mengajar (KBM) di sekolah menengah pertama merupakan bagian yang sangat penting dan harus ada supaya proses belajar mengajar dapat berjalan dengan baik sehingga siswa ataupun guru dapat menikmati kegiatan belajar mengajar tersebut. Oleh karena itu harus dibuat jadwal yang mendukung terciptanya suasana di atas. Di bawah ini akan diuraikan bagaimana suatu penjadwalan dibuat. Model penjadwalan pada karya ilmiah ini menggunakan lima parameter utama sebagai penyusun jadwal yaitu; 1. Hari, yaitu hari di mana mata pelajaran diberikan. Hari = {Senin, Selasa,...., Sabtu} 2. Periode waktu, yaitu waktu belajar di mana mata pelajaran diberikan. Periode waktu = {07.00-08.00, 08.00-09.00,......,(t – t+1)}. 3. Kelas, yaitu kelompok murid yang menghadiri mata pelajaran yang sama dan berada dalam satu ruangan. Kelas = {1A, 1B, ...,2A, 2B, ...,3A, 3B, ...}. 4. Guru, yaitu orang yang mengajar suatu mata pelajaran tertentu dalam suatu kelas. Guru = {Guru 1, ...., Guru n}. 5. Mata pelajaran, yaitu pelajaran yang diajarkan di kelas oleh seorang guru. Mata pelajaran = {mata pelajaran1, ..., mata pelajaran n}. Dalam menyusun suatu penjadwalan, ada dua macam kendala yang harus diperhatikan. Kendala yang pertama adalah kendala utama, yaitu kendala yang harus dipenuhi oleh setiap sekolah. Kendala ini dibuat oleh otorita pengelola pendidikan (Dinas Pendidikan). Kendala yang kedua adalah kendala tambahan, yaitu kendala yang diharapkan dapat dipenuhi atau dengan memasukan penalti pada fungsi objektif. Kendala ini biasanya dibuat oleh staf akademik pada setiap sekolah karena kondisi tertentu atau karena suatu peraturan yang ada dan bertujuan untuk meningkatkan prestasi murid dan guru. Berikut ini adalah beberapa contoh dari setiap kendala. Kendala Utama 1. Kurikulum untuk setiap sekolah sudah ada. 2. Dalam satu minggu jumlah periode waktu untuk memberikan mata pelajaran di setiap kelas sudah ditentukan.

3. Setiap guru mengajar sesuai bidangnya untuk kelas yang sudah ditentukan. 4. Dalam satu minggu periode waktu total untuk memberikan semua mata pelajaran di setiap kelas sudah ditentukan. 5. Guru tidak boleh mengajar lebih dari satu kelas pada periode waktu yang sama. 6. Jumlah jam mengajar setiap guru sudah ditentukan sesuai dengan kemampuannya. 7. Jumlah jam mengajar untuk setiap kelas sudah ditetapkan. 8. Setiap guru harus mengajar minimal satu periode waktu untuk beberapa hari di mana guru tersebut telah dijadwalkan. Kendala Tambahan 1. Distribusi periode waktu mengajar guru harus sama dalam seminggu. 2. Perbedaan periode waktu mengajar harian seorang guru paling banyak satu periode waktu dari periode waktu mengajar ratarata di mana guru tersebut ditugaskan. 3. Beberapa mata pelajaran harus diajarkan di awal jam pelajaran. 4. Beberapa mata pelajaran tidak diajarkan di akhir jam pelajaran. 5. Tidak boleh ada periode waktu kosong untuk setiap kelas. 6. Untuk keadaan khusus (contohnya; sakit, ibu yang mempunyai anak kecil), guru boleh meminta waktu untuk tidak mengajar pada periode waktu tertentu. 7. Terdapat batasan maksimal dan minimal dalam menentukan beban mengajar. Model Matematika Model matematika untuk masalah penjadwalan di sini adalah model integer linear programming (ILP). Pembuatan jadwal pada karya ilmiah ini tidak menggunakan semua kendala yang sudah disebutkan di atas, namun hanya beberapa kendala yang dipakai. Hal ini untuk menyesuaikan kondisi yang ada. Berikut ini kendala yang digunakan dalam pembuatan penjadwalan pada karya ilmiah ini. 1. Tidak boleh ada seorang guru yang mengajar di dua kelas atau lebih pada periode waktu yang sama. 2. Untuk setiap hari dan setiap periode waktunya, kecuali periode waktu terakhir, semua kelas akan diajar oleh seorang guru. 3. Terpenuhinya jumlah periode waktu total yang diperlukan setiap kelas selama seminggu.

4. Terpenuhinya jumlah periode waktu mengajar setiap guru di kelas yang di ajar. 5. Guru mengajar minimal satu periode waktu pada hari di mana guru tersebut telah dijadwalkan 6. Semua mata pelajaran akan didistribusikan dengan seimbang selama seminggu. 7. Beberapa guru tidak mengajar pada hari tertentu. Dalam karya ilmiah ini diasumsikan ruangan yang digunakan untuk kegiatan belajar mengajar memiliki kapasitas yang mencukupi.

Tujuan dari model penjadwalan ini adalah mencari penjadwalan mata pelajaran optimal dengan cara meminimumkan fungsi objektif dengan koefisien-koefisiennya merupakan bobot yang diberikan kepada guru atau mata pelajaran. Sebagai contoh : 1) Mata pelajaran inti diharapkan dapat diajarkan di awal periode waktu. Oleh karena itu mata pelajaran ini diberi bobot (koefisien) yang kecil di awal periode waktu dan bobot yang besar di akhir periode waktu. Sehingga mata pelajaran ini memiliki peluang yang lebih besar untuk dijadwalkan di awal periode waktu (lihat Gambar 4). 2) Mata pelajaran biasa diharapkan dapat diajarkan setelah jam istirahat (periode waktu akhir). Oleh karena itu mata pelajaran ini diberi bobot yang kecil di akhir periode waktu dan bobot yang besar di awal periode waktu. Sehingga mata pelajaran ini memiliki peluang yang lebih besar untuk dijadwalkan di akhir periode waktu (lihat Gambar 5). 3) Guru-guru tertentu memiliki preferensi untuk mengajarkan mata pelajaran di periode waktu pertengahan. Guru-guru tertentu merupakan guru-guru yang mengajar mata pelajaran inti dan mata yang pelajaran biasa. Guru-guru mangajarkan mata pelajaran ini diberi bobot yang kecil di periode waktu pertengahan dan bobot yang besar di awal dan di akhir periode waktu (lihat Gambar 6).

Gambar 4 Bobot untuk mata pelajaran inti.

Gambar 5 Bobot untuk mata pelajaran biasa.

Gambar 6 Bobot untuk guru-guru yang mengajarkan mata pelajaran inti dan mata pelajaran biasa.

Bobot yang diberikan terhadap guru bersesuaian dengan variabel keputusan yang akan dipilih dalam penjadwalan. Variabel

x

i , j , k ,l ,m

keputusan dalam masalah penjadwalan adalah sebagai berikut :

guru l mengajar mata pelajaran m di kelas k pada hari i diperiode ke-j = {10 ,, jika selainnya

dengan : I = himpunan hari J = himpunan periode waktu K = himpunan kelas L = himpunan guru M = himpunan mata pelajaran

Fungsi kendala yang digunakan adalah sebagai berikut : 1. Tidak boleh ada seorang guru yang mengajar dalam dua kelas atau lebih pada periode waktu yang sama.

∑∑x

i ϵ I, j ϵ J, k ϵ K, l ϵ L, m ϵ M.

i , j , k ,l , m

k∈Kl m∈M kl

Seperti telah disebutkan di atas bahwa model penjadwalan pada karya ilmiah ini bertujuan mencari penjadwalan mata pelajaran optimal dengan cara meminimumkan fungsi objektif dengan koefisien-koefisiennya merupakan bobot yang diberikan kepada guru atau mata pelajaran. Fungsi objektif untuk masalah penjadwalan ini dimodelkan sebagai berikut:

min

∑∑∑∑ ∑ c i∈ I j ∈ J k ∈ K l ∈ L m ∈ M

dengan : ci , j , k ,l , m =

i , j , k ,l , m

xi , j , k , l , m

Kendala 1 menjamin bahwa untuk setiap periode waktu setiap harinya hanya ada satu guru yang akan mengajarkan sebuah mata pelajaran. Misalkan pada hari 1 guru 2 mengajar di periode 3, maka variabel x1,3, k ,2, m akan bernilai satu, dan selain itu bernilai nol. 2. Untuk setiap hari dan setiap periode waktunya, kecuali periode waktu terakhir, semua kelas akan diajar seorang guru dan sebuah pelajaran. ∑ ∑ xi , j ,k ,l ,m = 1 ; l∈Lk m∈M kl

bobot yang diberikan kepada mata pelajaran dan guru.

∀i ∈ I , j ∈1, 2, ..., ( jn − 1) , k ∈ K dan,

∑∑x

l∈Lk m∈M kl

Pada model penjadwalan di sini untuk setiap kelas sudah ditentukan guru-guru yang akan mengajar di kelas tersebut, sehingga masing-masing guru hanya akan mengajar kelas tertentu. Begitu pula dengan mata pelajaran yang akan diajarkan oleh guru. Masing-masing guru hanya akan mengajar mata pelajaran tertentu. Atas dasar keterkaitan ini maka fungsi objektif dari model penjadwalan dapat ditulis menjadi ;

min

≤ 1 ; ∀i ∈ I , j ∈ J , l ∈ L

∑∑∑ ∑ ∑

i∈ I j ∈ J l ∈ L k ∈ K l m∈ M kl

ci , j , k , l , m xi , j , k , l , m

dengan : K l = {k ∈ K : k = kelas yang diajar oleh guru l}, ∀l ∈ L

M kl = {m ∈ M : m = pelajaran yang diajarkan di kelas k oleh guru l}, ∀k ∈ K dan l ∈ L

i , j , k ,l , m

≤ 1 ; ∀i ∈ I , j ∈ jn , k ∈ K

dengan: Lk = {l ∈ L : l = guru yang ditugasi untuk mengajar di kelas k }, ∀k ∈ K , jn = periode waktu terakhir. Kendala 2 menjamin bahwa pada setiap periode waktu setiap harinya kecuali mungkin periode waktu terakhir pasti akan diajar oleh seorang guru. 3. Terpenuhinya jumlah periode waktu total yang diperlukan setiap kelas selama seminggu.

∑∑ ∑ ∑

i∈I j∈J l∈Lk m∈M kl

xi , j , k ,l , m = ak ; ∀k ∈ K

dengan: ak = periode waktu total selama seminggu untuk kelas k . Kendala 3 menjamin bahwa selama seminggu periode waktu total yang

dibutuhkan oleh setiap kelas pasti sudah diajarkan. Misalkan untuk kelas 3 periode waktu total yang dibutuhkan selama seminggu 20, maka . x = 20 ∑∑ ∑ ∑ i , j ,3,l , m i∈I j∈J l∈Lk m∈M kl

4. Terpenuhinya jumlah periode waktu mengajar setiap guru di kelas yang di ajar

∑∑ ∑ x i∈I j∈J m∈M kl

i , j , k ,l , m

= bkl ; ∀k ∈ K , l ∈ L

dengan: bkl = jumlah jam mengajar guru l pada kelas k . Kendala 4 menjamin bahwa periode waktu mengajar guru l di kelas k sudah terpenuhi. Misalkan periode waktu mengajar guru 5 dikelas 2 sebanyak 4 maka . ∑∑ ∑ xi, j ,2,5, m = 4 i∈I j∈J m∈M kl

5. Guru mengajar minimal satu periode waktu pada hari di mana guru tersebut dijadwalkan.

∑∑ ∑

j∈J k∈Kl m∈M kl

xi , j ,k ,l ,m ≥ 1 , ∀i ∈ Il , l ∈ L

dengan : Il = hari dimana guru l dijadwalkan. Kendala 5 menjamin bahwa pada hari di mana guru dijadwalkan maka seorang guru harus mengajar sedikitnya satu periode waktu. Misalkan guru 4 mengajar pada hari 1, hari 2, dan hari 3 maka pada hari tersebut guru 4 harus mengajar paling sedikit 1 periode waktu. 6. Semua mata pelajaran akan didistribuskan dengan seimbang dalam seminggu.

∑x j∈ J

i , j , k ,l , m

≤q;

∀i ∈ I , l ∈ L, k ∈ K l , m ∈ M kl dan,

∑∑ x i∈I j∈J

i , j , k ,l , m

= d mk ;

∀l ∈ L, k ∈ K l , m ∈ M kl dengan: dmk = jumlah periode waktu yang diperlukan untuk mengajar pelajaran m di kelas k. q

= periode waktu maksimal seorang guru

memberikan sebuah mata pelajaran disetiap kelas untuk satu harinya. Kendala 6 menjamin setiap mata pelajaran akan distribusikan dengan seimbang dalam seminggunya. Misalkan mata pelajaran 7 diajarkan untuk kelas 5 sebanyak 3 periode waktu. Selama seminggu mata pelajaran tersebut akan diajarkan selama tiga hari dan setiap harinya satu periode waktu. Selain itu maka salah. 7. Untuk beberapa guru yang dijadwalkan pada beberapa hari saja dalam seminggu maka untuk hari di mana guru tersebut tidak dijadwalkan akan memenuhi kendala sebagai berikut :

∑∑ ∑ ∑

i∈Sl j∈J k ∈K l m∈M kl

xi , j ,k ,l ,m = 0

∀l ∈ Li

dengan: Sl = hari dimana guru l tidak mengajar. Li = guru l yang tidak mengajar pada hari i.

IV STUDI KASUS DAN PENYELESAIANNYA Studi kasus yang diambil dalam penelitian ini adalah menentukan penjadwalan mata pelajaran di SMP Masa Depan. Pada sekolah tersebut mata pelajaran yang akan diajarkan untuk setiap kelas sudah ditentukan berdasarkan kurikulum yang berlaku pada saat

itu. Kurikulum yang digunakan adalah Kurikulum Tingkat Satuan Pendidikan (KTSP). Tabel 1 merupakan daftar mata pelajaran untuk setiap kelas beserta jumlah periode waktu yang dibutuhkan.

Tabel 1 Daftar mata pelajaran untuk masing-masing kelas beserta periode waktu yang dibutuhkan Mata Pelajaran Kode MP Klasifikasi Banyaknya Periode Waktu Kelas 1 Kelas 2 Kelas 3 Pendidikan Agama MP1 n 2 2 2 Pendidikan Kewarganegaraan MP2 n 2 2 2 Bahasa Indonesia MP3 p 4 4 4 Matematika MP4 p 5 5 5 Ilmu Pengetahuan Alam MP5 p 5 5 5 Ilmu Pengetahuan Sosial MP6 n 4 4 4 Seni Budaya MP7 n 2 2 2 Pendidikan Jasmani MP8 n 2 2 2 Bahasa Inggris MP9 p 4 4 4 Bahasa Daerah MP10 n 2 2 2 Pendidikan Ketrampilan Keluarga MP11 n 2 2 2 Teknologi Informasi Komputer MP12 n 2 2 2 Bimbingan Konseling MP13 n 1 1 1 Keterangan: p : mata pelajaran inti (primary) n : mata pelajaran biasa (non-primary) Jumlah guru di SMP Masa Depan sebanyak 23 orang. Dari 23 orang guru beban mengajar tidaklah sama, ada yang mengajar 5

periode waktu, ada pula yang mengajar lebih dari itu. Begitu juga dengan kelas yang akan diajar, setiap guru mengajar di kelas yang sudah ditentukan. Berikut ini akan diberikan contoh distribusi kegiatan belajar mengajar (KBM) untuk setiap kelas.

Tabel 2 Distribusi KBM dengan 10 kelas Guru Kode Penugasan guru MP 1A 1B 1C 2A 2B 2C 3A GU1 MP9 4 4 4 GU2 MP13 1 1 GU3 MP4 5 5 5 5 5 GU4 MP2 2 2 2 2 MP6 4 4 4 GU5 MP2 2 2 2 MP3 4 GU6 MP5 5 GU7 MP3 4 4 4 GU8 MP6 4 4 GU9 MP1 2 2 2 2 2 2 2 GU10 MP4 5 5 GU11 MP8 2 2 2 2 2 2 2 GU12 MP9 4 4 4 GU13 MP5 5 5 5 MP11 2 2 2 GU14 MP 9 4

Total Periode Waktu 12 5 25 26

3B

3C

3D

1

1

1

2

2

2

4 5

4 5

4 5

4 2 5 2

4 2 5 2

4 2 5 2

20 12 20 20 25 20 12 21

4

4

4

16

22

GU15 GU16 GU17 GU18 GU19 GU20 GU21 GU22 GU23 Total

MP10 MP7 MP13 MP13 MP12 MP5 MP7 MP12 MP3 MP6 MP7 MP12

2

2

2

1

1

2 2 1 2 5

2 4

2 4

2 2 1 2 2 5

2 2 1 2

2

2

2

2

2 2

2 2

2 2

2 2

20 6 5 14 25

2

2

2

2

14

5

2 4

2

2

2

37

37

37

4

4

2 37

37

Maksud dari tabel di atas adalah, misalkan diambil contoh guru 4 (GU4). Guru 4 mengajar mata pelajaran 2 (PKn) dan mata pelajaran 6 (IPS), di mana mata pelajaran 2 diajarkan oleh guru 4 di kelas 1A, 1B, 1C, 3A, 3B, 3C, dan 3D. Setiap kelas diajar selama 2 periode waktu, sedangkan mata pelajaran 6 diajarkan di kelas 1A, 1B, dan 1C. Setiap kelas diajar selama 4 periode waktu. Periode waktu total mengajar guru 4 adalah 26 periode waktu. Hari untuk KBM dimulai dari hari Senin dan berakhir hari Sabtu. Periode waktu KBM dimulai pukul 07.00 dan untuk setiap periode waktunya berlangsung 40 menit. Daftar periode waktu KBM adalah sebagai berikut: Tabel 3 Daftar periode waktu KBM Periode Jam KBM Periode 1 07.00-07.40 Periode 2 07.40-08.20 Periode 3 08.20-09.00 Periode 4 09.00-09.40 Istirahat (20 menit) Periode 5 10.00-10.40 Periode 6 10.40-11.20 Periode 7 11.20-12.00 Hari mengajar setiap guru tidaklah sama, hal ini tergantung dari permintaan dan kondisi guru yang bersangkutan. Berikut ini akan diberikan tabel distribusi hari mengajar berdasarkan preferensi guru. Tabel 4 Hari guru mengajar Guru Hari mengajar GU1 Rabu, Kamis, Jumat, Sabtu GU2 Senin, Selasa, Rabu GU3 Senin, Selasa, Rabu, Kamis, Jumat, Sabtu GU4 Senin, Selasa, Rabu, Kamis, Jumat, Sabtu GU5 Senin, Selasa, Rabu, Kamis, Jumat,

12 14 2 37

GU6 GU7 GU8 GU9 GU10 GU11 GU12 GU13 GU14 GU15 GU16 GU17 GU18 GU19 GU20 GU21 GU22 GU23

37

37

37

37

4 370

Sabtu Senin, Selasa, Rabu, Kamis, Jumat, Sabtu Senin, Selasa, Rabu, Kamis Senin, Selasa, Rabu, Kamis, Jumat, Sabtu Senin, Selasa, Rabu, Kamis, Jumat, Sabtu Senin, Selasa, Rabu, Kamis, Jumat, Sabtu Senin, Selasa, Rabu, Kamis, Jumat, Sabtu Rabu, Kamis, Jumat, Sabtu Senin, Selasa, Rabu, Kamis, Jumat, Sabtu Senin, Selasa, Rabu, Kamis, Jumat Senin, Selasa, Rabu, Kamis, Jumat, Sabtu Kamis, Jumat, Sabtu Rabu, Kamis, Jumat, Sabtu Selasa, Rabu, Kamis, Jumat, Sabtu Senin, Selasa, Rabu, Kamis, Jumat, Sabtu Senin, Selasa, Rabu, Kamis Rabu, Kamis, Jumat, Sabtu Senin, Selasa, Rabu, Kamis Senin, Sabtu

Telah disebutkan di atas bahwa mata pelajaran diklasifikasikan menjadi 2 yaitu inti dan biasa. Mata pelajaran yang termasuk mata pelajaran inti yaitu Bahasa Indonesia, IPA, Matematika, dan Bahasa Inggris. Mengingat pentingnya keempat mata pelajaran tersebut maka sedapat mungkin mata pelajaran tersebut dijadwalkan di awal jam pelajaran. Dengan harapan siswa lebih mudah dalam menerima pelajaran-pelajaran tersebut. Untuk pelajaran biasa (selain keempat mata pelajaran yang telah disebutkan sebelumnya) penjadwalan sedapat mungkin ditempatkan setelah jam istirahat. Hal ini supaya siswa

sudah segar kembali dalam berfikir, sehingga siswa juga akan lebih mudah dalam memahami pelajaran. Untuk memenuhi preferensi mengajar guru, pembuatan penjadwalan sedapat mungkin memenuhi permintaan dan kondisi guru dalam penentuan waktu mengajar mereka. Permintaan periode waktu mengajar guru secara lengkap adalah sebagai berikut:

Tabel 5 Permintaan periode waktu mengajar

Guru GU1 GU2 GU3 GU4 GU5 GU6 GU7 GU8 GU9 GU10 GU11 GU12 GU13 GU14 GU15 GU16 GU17 GU18 GU19 GU20 GU21 GU22 GU23

Periode waktu Awal Akhir Awal Akhir Tengah Awal Awal Akhir Akhir Awal Awal Awal Tengah Awal Bebas Bebas Akhir Bebas Tengah Bebas Awal Akhir Bebas

Gambar 7 Bobot untuk mata pelajaran yang diharapkan diajarkan di awal periode waktu.

Gambar 8 Bobot untuk mata pelajaran yang diharapkan diajarkan di akhir periode waktu.

Keterangan; Awal : periode1, periode2, periode3 Tengah : periode3, periode4 Akhir : periode5, periode6, periode7 Bebas : available untuk semua periode Atas pertimbangan di atas, dibuatlah bobot (koefisien) yang mana penjelasan bobot telah disebutkan pada bagian sebelumnya. Penentuan bobot yang telah disebutkan pada bagian sebelumnya tidaklah mutlak harus seperti itu. Yang ada di sini hanyalah sebagai gambaran saja. Beberapa grafik bobot yang mungkin dapat digunakan diperlihatkan sebagai berikut:

Gambar 9 Bobot untuk mata pelajaran yang diharapkan diajarkan di periode waktu awal dan periode waktu akhir.

Gambar 13 Bobot untuk guru dengan preferensi mengajar di awal dan di akhir periode waktu.

Gambar 10 Bobot untuk mata pelajaran yang diharapkan diajarkan di periode waktu pertengahan.

Dari studi kasus di atas formulasi model ILP-nya adalah sebagai berikut ;

Min

∑∑∑∑ ∑ c i∈ I j ∈ J l ∈ L k ∈ K m ∈ M

i , j , k ,l , m

xi , j , k , l , m

I = 1, 2, …, 6 J = 1, 2, …, 7 K = 1, 2, …, 10 L = 1, 2, …, 23 M = 1, 2, …, 13

Gambar 11 Bobot untuk guru dengan preferensi mengajar di akhir periode waktu, kalau tidak terpenuhi menginginkan di awal periode waktu.

Terhadap fungsi kendala sebagai berikut; 1. Tidak boleh ada seorang guru yang mengajar di dua kelas atau lebih pada periode waktu yang sama.

∑∑x

i , j , k ,l , m

k∈Kl m∈M kl

≤ 1 ; ∀i ∈ I , j ∈ J , l ∈ L

2. Untuk setiap hari dan setiap periode waktunya, kecuali periode waktu terakhir, semua kelas akan diajar seorang guru dengan sebuah mata pelajaran.

∑∑

l∈Lk m∈M kl

xi , j , k ,l , m = 1 ; ∀i ∈ I , j ∈1, 2, ...,6 ..., 6 k ∈ K dan,

∑∑

l∈Lk m∈M kl

xi , j , k ,l ,m ≤ 1 ; ∀i ∈ I , j ∈ 7, k ∈ K

dengan: Lk = {l ∈ L : l = guru yang ditugasi untuk mengajar di kelas k },

Gambar 12 Bobot untuk guru dengan preferensi mengajar di awal periode waktu, kalau tidak terpenuhi menginginkan di akhir periode waktu.

∀k ∈ K , J n = periode waktu terakhir. 3. Terpenuhinya jumlah periode waktu total yang diperlukan setiap kelas selama seminggu.

∑∑ ∑ ∑

i∈I j∈J l∈Lk m∈M kl

xi , j , k ,l , m = 37 ; ∀k ∈ K

4. Terpenuhinya jumlah periode mengajar untuk guru l dikelas k.

∑∑ ∑ x i∈I j∈J m∈M kl

i , j , k ,l , m

waktu

= bkl ; ∀k ∈ K , l ∈ L

dengan: bkl = jumlah jam mengajar guru l pada kelas k . Misalkan untuk guru 1. Guru 1 mengajar di kelas 1, 2, dan 3 masing-masing 4 periode waktu.

∑∑ ∑

xi , j ,1,1,m = 4

∑∑ ∑

xi , j ,2,1,m = 4

∑∑ ∑

xi , j ,3,1, m = 4

i∈I j∈J m∈M kl



∑∑ ∑


xi , j ,k ,l ,m ≥ 1 , ∀i ∈ Il , l ∈ L

dengan : Il = hari dimana guru l dijadwalkan. Misalkan diambil contoh untuk guru 17. Guru ini mengajar pada hari 3, hari 4, hari 5 dan hari 6.

∑∑ ∑

x3, j ,k ,17,m ≥ 1

∑∑ ∑

x4, j ,k ,17,m ≥ 1

∑∑ ∑

x5, j ,k ,17, m ≥ 1

∑∑ ∑

x6, j , k ,17,m ≥ 1





6. Semua mata pelajaran akan didistribusikan dengan seragam selama seminggu. Pada karya ilmiah ini setiap mata pelajaran diajarkan paling banyak satu periode waktu untuk setiap harinya.

j∈ J

i , j , k ,l , m

≤1 ;

∀i ∈ I , l ∈ L, k ∈ K l , m ∈ M kl dan,


d mk = jumlah periode waktu yang diperlukan untuk mengajar pelajaran m di kelas k. Misalkan diambil contoh mata pelajaran 1 yang diajarkan di kelas 10.


i , j ,10, l ,1

=2;

∀l ∈ L, k ∈ K l , m ∈ M kl

7. Untuk beberapa guru yang dijadwalkan pada beberapa hari saja dalam seminggu maka untuk hari di mana guru tersebut tidak dijadwalkan akan memenuhi kendala sebagai berikut :

∑∑ ∑ ∑


5. Guru mengajar minimal satu periode waktu pada hari di mana guru tersebut dijadwalkan.

∑x

dengan:

i , j , k ,l , m

= d mk ;

∀l ∈ L, k ∈ K l , m ∈ M kl

xi , j ,k ,l ,m = 0

∀l ∈ Li Misalkan untuk guru 2. Guru 2 tidak mengajar pada hari Kamis, Jumat, dan Sabtu. Maka fungsi kendalanya adalah

∑∑ ∑ ∑


xi , j ,k ,2,m = 0

Sl = 4, 5, 6. Penyelesaian masalah penjadwalan mata pelajaran SMP Masa Depan pada karya ilmiah ini dilakukan dengan bantuan software LINGO 8.0. menggunakan metode branch and bound. Syntax program dan hasil komputasi dicantumkan pada Lampiran 3. Solusi yang didapat adalah solusi optimal dengan nilai fungsi objektifnya adalah 4760 didapatkan pada iterasi 40663. Waktu yang dibutuhkan untuk mendapatkan solusi tersebut sekitar 1,32 menit dengan menggunakan komputer Intel Pentium Dual Core CPU 2.80 GHz dengan RAM 960 MB. Hasil komputasi tidak semuanya dicantumkan, dikarenakan terlalu banyak. Hasil yang dicantumkan hanya untuk x yang bernilai satu saja. Daftar penjadwalan yang terbentuk untuk SMP Masa Depan dicantumkan pada Lampiran 1. Dari hasil yang didapatkan bisa dilihat presentase rata-rata terpenuhinya preferensi setiap mata pelajaran dan preferensi setiap guru. Untuk mata pelajaran presentase ratarata terpenuhinya preferensi sekitar 85%. Untuk guru presentase rata-rata terpenuhinya preferensi sekitar 79%. Secara keseluruhan presentase rata-rata terpenuhinya preferensi mata pelajaran dan guru sekitar 82%.

V SIMPULAN DAN SARAN

Simpulan Dalam penulisan karya ilmiah ini telah diperlihatkan penyelesaian dari masalah penjadwalan mata pelajaran yang bertujuan mencari penjadwalan mata pelajaran optimal dengan cara meminimumkan fungsi objektif dengan koefisien-koefisiennya merupakan bobot (koefisien) yang diberikan kepada guru atau mata pelajaran. Di mana masalah penjadwalan disini dipandang sebagai masalah 0-1 ILP. Penyelesaian masalah ini menggunakan software LINGO 8.0 dengan metode branch and bound. Penjadwalan yang dihasilkan sangat bergantung pada penentuan bobot yang akan diberikan terhadap mata pelajaran atau guru. Oleh karena itu semakin bagus (sesuai dengan kenyataan yang ada) penentuan bobotnya maka penjadwalan yang dihasilkan juga akan semakin memuaskan. Dalam hal ini antara guru dan murid serta pihak sekolah yang

terkait akan semakin menikmati kegiatan belajar mengajar. Penentuan penjadwalan menggunakan software LINGO 8.0 sangat memudahkan kita. Pengguna dapat dengan mudah menambahkan data maupun kendalakendala baru supaya tercipta penjadwalan yang lebih baik lagi. Saran Pada penulisan karya ilmiah ini data yang digunakan terbatas hanya pada satu sekolah saja dan tidak dilakukan penelitian secara langsung ke sekolah yang terkait. Akan lebih baik jika data yang diambil berdasarkan penelitian secara langsung dan mengadakan kuisioner untuk menentukan bobot yang akan digunakan. Penambahan kendala baru seperti guru yang menginginkan 2 periode waktu mengajar mereka secara berturutan setiap kali mengajar juga sangat menarik untuk ditambahkan.

DAFTAR PUSTAKA Aprilia, S. Aplikasi Algoritma Branch and Bound Untuk Menyelesaikan Integer Programing. http://www.informatika.org/~rinaldi/Stmi k/20062007/Makalah_2007/MakalahSTMIK200 7-076.pdf

Garfinkel, RS. & GL. Nemhauser. 1972. Integer Programming. John Willey & Sons, New York.

Birbas, T, Daskalaki, S, & Housos, E. 2000. Timetabling for Greek High Schools. The Journal of the Operational Research Society. 48: 1191-1200.

Taha, HA. 1975. Integer Programming. Academic Press, New York.

Chen, CY. 2008. Using Integer Programing to Solve School Timetabling at Chin-Min Institute of Technology. Journal of American Academy of Business. 13: 279286

Nash, SG. & A. Sofer. 1996. Linear and Nonlinear Programming McGraw-Hill, New York.

Winston, WL. 1995. Introduction to Mathematical Programming 2nded. Duxbury, New York. Winston, WL. 2004. Operations Research Applications and Algorithms 4th ed. Duxbury, New York.

LAMPIRAN

Lampiran 1 Jadwal Kegiatan Belajar Mengajar (KBM) yang Terbentuk untuk SMP Masa Depan Tabel 6 Jadwal KBM SMP Masa Depan untuk setiap kelas Hari Periode Kelas Waktu Senin Selasa Rabu Kamis 1 GU13 / MP5 GU10 / MP4 GU1 / MP9 GU13 / MP5 2 GU11 / MP8 GU20 / MP12 GU21 / MP3 GU21 / MP3 3 GU9 / MP1 GU13 / MP5 GU13 / MP5 GU1 / MP9 1A 4 GU4 / MP6 GU4 / MP2 GU22 / MP7 GU10 / MP4 5 GU20 / MP12 GU4 / MP6 GU4 / MP6 GU22 / MP7 6 GU10 / MP4 GU2 / MP13 GU15 / MP10 GU11 / MP8 7 GU4 / MP6

Jumat Sabtu GU1 / MP9 GU13 / MP5 GU21 / MP3 GU21 / MP3 GU13 / MP11 GU1 / MP9 GU4 / MP2 GU13 / MP11 GU9 / MP1 GU10 / MP4 GU10 / MP4 GU15 / MP10

1B

1 2 3 4 5 6 7

GU22 / MP7 GU13 / MP5 GU21 / MP3 GU1 / MP9 GU13 / MP5 GU4 / MP6 GU4 / MP2 GU13 / MP5 GU3 / MP4 GU1 / MP9 GU13 / MP5 GU4 / MP6 GU1 / MP9 GU21 / MP3 GU21 / MP3 GU13 / MP11 GU22 / MP7 GU13 / MP11 GU9 / MP1 GU3 / MP4 GU3 / MP4 GU3 / MP4 GU11 / MP8 GU20 / MP12 GU4 / MP6 GU15 / MP10 GU15 / MP10 GU20 / MP12 GU17 / MP13 GU11 / MP8 GU4 / MP2

GU21 / MP3 GU1 / MP9 GU13 / MP5 GU3 / MP4 GU4 / MP6 GU9 / MP1

1C

1 2 3 4 5 6 7

GU3 / MP4 GU11 / MP8 GU13 / MP5 GU21 / MP3 GU21 / MP3 GU1 / MP9 GU13 / MP5 GU13 / MP5 GU1 / MP9 GU1 / MP9 GU13 / MP5 GU13 / MP5 GU4 / MP6 GU3 / MP4 GU21 / MP3 GU3 / MP4 GU1 / MP9 GU21 / MP3 GU20 / MP12 GU9 / MP1 GU4 / MP6 GU22 / MP7 GU13 / MP11 GU11 / MP8 GU13 / MP11 GU15 / MP10 GU20 / MP12 GU4 / MP6 GU3 / MP4 GU9 / MP1 GU4 / MP2 GU22 / MP7 GU17 / MP13 GU15 / MP10 GU4 / MP2 GU3 / MP4 GU4 / MP6

2A

1 2 3 4 5 6 7


2B

1 2 3 4 5 6 7


GU7 / MP3 GU3 / MP4 GU12 / MP9 GU12 / MP9 GU3 / MP4 GU3 / MP4 GU12 / MP9 GU19 / MP5 GU3 / MP4 GU19 / MP5 GU19 / MP5 GU7 / MP3 GU7 / MP3 GU19 / MP5 GU12 / MP9 GU15 / MP10 GU9 / MP1 GU5 / MP2 GU19 / MP12 GU5 / MP2 GU22 / MP6 GU18 / MP11 GU16 / MP7 GU17 / MP13 GU19 / MP12 GU11 / MP8 GU22 / MP6 GU18 / MP11 GU15 / MP10 GU16 / MP7 GU22 / MP6

2C

1

GU7 / MP3

GU19 / MP5 GU12 / MP9 GU19 / MP5 GU19 / MP5 GU12 / MP9

2 3 4 5 6 7

GU19 / MP5 GU7 / MP3 GU3 / MP4 GU5 / MP2 GU5 / MP2 GU3 / MP4 GU15 / MP10 GU9 / MP1 GU23 / MP12 GU8 / MP6 GU11 / MP8

GU7 / MP3 GU3 / MP4 GU11 / MP8 GU8 / MP6 GU9 / MP1

GU7 / MP3 GU12 / MP9 GU3 / MP4 GU12 / MP9 GU3 / MP4 GU19 / MP5 GU18 / MP11 GU15 / MP10 GU8 / MP6 GU8 / MP6 GU18 / MP11 GU23 / MP12 GU16 / MP7 GU16 / MP7 GU17 / MP13

3A

1 2 3 4 5 6 7



GU14 / MP9 GU6 / MP5 GU6 / MP5 GU4 / MP2 GU10 / MP4 GU10 / MP4 GU5 / MP3 GU10 / MP4 GU6 / MP5 GU5 / MP3 GU10 / MP4 GU15 / MP10 GU18 / MP11 GU11 / MP8 GU14 / MP9 GU19 / MP12 GU9 / MP1 GU15 / MP10 GU19 / MP12 GU8 / MP6 GU2 / MP13 GU4 / MP2 GU8 / MP6 GU18 / MP11 GU20 / MP7

3B

1 2 3 4 5 6 7

GU5 / MP3 GU14 / MP9 GU10 / MP4 GU11 / MP8 GU4 / MP2 GU8 / MP6 GU20 / MP7


GU5 / MP3 GU5 / MP3 GU10 / MP4 GU6 / MP5 GU6 / MP5 GU14 / MP9 GU14 / MP9 GU5 / MP3 GU10 / MP4 GU6 / MP5 GU6 / MP5 GU10 / MP4 GU19 / MP12 GU4 / MP2 GU18 / MP11 GU18 / MP11 GU15 / MP10 GU19 / MP12 GU15 / MP10 GU11 / MP8 GU8 / MP6 GU9 / MP1 GU9 / MP1 GU8 / MP6

3C

1 2 3 4 5 6 7


3D

1 2 3 4 5 6 7

GU5 / MP3 GU14 / MP9 GU8 / MP6 GU10 / MP4 GU6 / MP5 GU5 / MP3 GU15 / MP10 GU8 / MP6 GU18 / MP11 GU11 / MP8 GU4 / MP2 GU6 / MP5

GU14 / MP9 GU10 / MP4 GU9 / MP1 GU6 / MP5 GU5 / MP3 GU5 / MP3 GU10 / MP4 GU14 / MP9 GU10 / MP4 GU20 / MP7 GU8 / MP6 GU6 / MP5 GU18 / MP11 GU19 / MP12 GU20 / MP7 GU8 / MP6 GU11 / MP8 GU4 / MP2

Tabel 7 Jadwal mengajar guru untuk setiap hari dan setiap periode waktunya Hari Guru Periode Waktu Senin Selasa Rabu Kamis Jumat 1 MP9 / 1A MP9 / 1B MP9 / 1A 2 MP9 / 1C MP9 / 1C MP9 / 1B GU1 3 MP9 / 1B MP9 / 1A MP9 / 1C 4 5

GU6 / MP5 GU10 / MP4 GU14 / MP9 GU19 / MP12 GU9 / MP1 GU2 / MP13 GU15 / MP10

Sabtu MP9 / 1C MP9 / 1B MP9 / 1A

6 7

GU2

GU3

1 2 3 4 5 6 7 1 2 3 4 5 6 7

MP13 / 3D

MP13 / 3B MP13 / 1A

MP13 / 3C MP13 / 3A

MP4 / 1C MP4 / 2B MP4 / 2C MP4 / 2A MP4 / 1B

MP4 / 2A MP4 / 2B MP4 / 1C MP4 / 2C MP4 / 1B

MP4 / 2B MP4 / 2A MP4 / 2C

MP4 / 2A MP4 / 2B MP4 / 2C MP4 / 1B MP4 / 1C

MP4 / 2B MP4 / 2C MP4 / 2A MP4 / 1B MP4 / 1C

GU4

1 2 3 4 5 6 7

GU5

1 2 3 4 5 6 7

MP3 / 3B MP3 / 3C MP3 / 3A MP2 / 2C

MP5 / 3D MP5 / 3A MP5 / 3C

GU6

1 2 3 4 5 6 7 1 2 3 4

MP3 / 2C MP3 / 2A MP3 / 2B

GU7

MP4 / 1B MP4 / 1C

MP2 / 3A MP6 / 1B MP6 / 1C MP6 / 1A MP2 / 3B MP2 / 1C

MP2 / 1B MP6 / 1B MP2 / 1A MP6 / 1A MP2 / 3D

MP6 / 1C MP6 / 1A MP2 / 3C

MP2 / 3B MP6 / 1C MP2 / 3A MP6 / 1A

MP2 / 1A MP6 / 1B MP2 / 1C MP2 / 1B

MP2 / 3C MP6 / 1B MP2 / 3D MP6 / 1C

MP3 / 3A MP3 / 3D MP2 / 2C MP2 / 2A

MP3 / 3B MP3 / 3D

MP3 / 3B MP3 / 3C MP3 / 3A MP2 / 2B

MP3 / 3C MP3 / 3A MP3 / 3D MP2 / 2A

MP3 / 3D MP3 / 3B MP3 / 3C MP2 / 2B

MP5 / 3C MP5 / 3A MP5 / 3B MP5 / 3D

MP5 / 3C MP5 / 3B MP5 / 3A

MP5 / 3A MP5 / 3D MP5 / 3B

MP5 / 3A MP5 / 3C MP5 / 3B

MP5 / 3B MP5 / 3C MP5 / 3D

MP5 / 3D

MP3 / 2B MP3 / 2C MP3 / 2A

MP3 / 2A MP3 / 2C MP3 / 2B

MP3 / 2A MP3 / 2C MP3 / 2B

5 6 7

GU8

1 2 3 4 5 6 7

MP6/ 3A MP6/ 3C MP6/ 3B

MP6/ 3C MP6/ 3B MP6/ 3A MP6/ 2C

MP4 / 3C MP4 / 3D MP4 / 3B

GU10

1 2 3 4 5 6 7

MP4 / 1A MP4 / 3B MP4 / 3D MP4 / 3C

MP4 / 1A

MP4 / 3A

1 2 3 4 5 6 7

MP8 / 2A MP8 / 1A

MP8 / 1C

GU12

1 2 3 4 5 6 7

GU13

1 2 3

MP6/ 3D MP6/ 2C MP6/ 3A MP6/ 3B

MP1 / 2B MP1 / 3A MP1 / 2C

MP1 / 1B MP1 / 2A MP1 / 3B

MP1 / 3C MP1 / 1A MP1 / 3B

MP1 / 2A MP1 / 1C MP1 / 1B

MP4 / 3D MP4 / 3A MP4 / 3B MP4 / 3C

MP4 / 3C MP4 / 3A MP4 / 3D MP4 / 1A

MP4 / 3B MP4 / 3D MP4 / 3A

MP4 / 3C MP4 / 3A MP4 / 3B

MP1 / 1C MP1 / 2C MP1 / 3C

GU9

1 2 3 4 5 6 7

GU11

MP6/ 2C MP6/ 3D

MP6/ 3D MP6/ 3C MP6/ 3A

MP6/ 3D MP6/ 2C MP6/ 3B MP6/ 3C

MP1 / 3D MP1 / 1A MP1 / 2B MP1 / 3D MP1 / 3A

MP4 / 1A

MP8 / 3B MP8 / 3A MP8 / 2B MP8 / 2C

MP5 / 1A MP5 / 1C MP5 / 1B

MP8 / 2A MP8 / 2B

MP5 / 1B MP5 / 1C MP5 / 1A

MP4 / 1A

MP8 / 2C MP8 / 1B MP8 / 3D

MP8 / 3A MP8 / 3C MP8 / 1A

MP8 / 3D MP8 / 1B

MP8 / 1C MP8 / 3B MP8 / 3C

MP9 / 2C MP9 / 2B MP9 / 2A

MP9 / 2B MP9 / 2A MP9 / 2C

MP9 / 2B MP9 / 2C MP9 / 2A

MP9 / 2C MP9 / 2A MP9 / 2B

MP5 / 1C MP5 / 1B MP5 / 1A

MP5 / 1A

MP5 / 1B MP5 / 1C MP11 / 1A

MP5 / 1A MP5 / 1C MP5 / 1B

4 5 6 7

MP11 / 1B MP11 / 1C

MP9 / 3A MP9 / 3B MP9 / 3D

GU14

1 2 3 4 5 6 7

GU15

1 2 3 4 5 6 7

GU16

1 2 3 4 5 6 7

GU17

GU18

GU19

MP10 / 3C MP10 / 2C MP10 / 1B MP10 / 3D

MP11 / 1B

MP9 / 3B MP9 / 3C MP9 / 3A

MP10 / 2B MP10 / 1C MP10 / 1B

1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2

MP18 / 3C MP18 / 2A

MP5 / 2B MP5 / 2C

MP5 / 2C MP5 / 2A

MP9 / 3A MP9 / 3C MP9 / 3D

MP11 / 1C

MP9 / 3D MP9 / 3B MP9 / 3C

MP11 / 1A

MP9 / 3D MP9 / 3B MP9 / 3C MP9 / 3A

MP10 / 2A MP10 / 3A MP10 / 1C

MP10 / 2C MP10 / 3B MP10 / 2B

MP10 / 3A MP10 / 3D MP10 / 3C MP10 / 1A

MP7 / 2B MP7 / 2C

MP7 / 2A MP7 / 2C

MP7 / 2A MP7 / 2B

MP13 / 1C

MP13 / 1B

MP13 / 2B MP13 / 2A

MP13 / 2B

MP18 / 3A MP18 / 2B MP18 / 2A

MP18 / 2C MP18 / 3D MP18 / 2B

MP18 / 3B MP18 / 2C MP18 / 3C

MP18 / 3B MP18 / 3D MP18 / 3A

MP5 / 2C MP5 / 2B

MP5 / 2C MP5 / 2A

MP5 / 2A MP5 / 2B

MP10 / 2A MP10 / 3B MP10 / 1A

3 4 5 6 7

GU20

1 2 3 4 5 6 7

GU21

1 2 3 4 5 6 7

GU22

1 2 3 4 5 6 7

GU23

1 2 3 4 5 6 7

MP5 / 2A MP12 / 3D

MP5 / 2B

MP12 / 3C MP12 / 3B MP12 / 3D

MP5 / 2A MP12 / 3C MP12 / 3B

MP12 / 1C MP12 / 1B

MP7 / 3D MP12 / 1B MP7 / 3C MP7 / 3A

MP3 / 1B MP3 / 1A MP3 / 1C

MP3 / 1C MP3 / 1A MP3 / 1B

MP7 / 1A MP6 / 2A MP6 / 2B

MP7 / 1C MP7 / 1A MP6 / 2A MP6 / 2B

MP5 / 2B MP12 / 2B MP12 / 3A

MP5 / 2C MP12 / 3A MP12 / 2B

MP3 / 1C MP3 / 1A MP3 / 1B

MP3 / 1B MP3 / 1A MP3 / 1C

MP12 / 1A MP12 / 1C MP12 / 1A MP7 / 3C MP7 / 3B

MP7 / 3A MP7 / 3D MP7 / 3B

MP7 / 1B

MP6 / 2B MP6 / 2A

MP7 / 1B MP6 / 2B MP7 / 1C MP6 / 2A

MP12 / 2A

MP12 / 2C

MP12 / 2C

MP12 / 2A

Lampiran 2 Syntax Program LINGO 8.0 untuk Menyelesaikan Masalah Pemrograman Linear dengan Metode Branch-and-Bound Beserta Hasil yang Diperoleh 1.

LP relaksasi masalah (6) Max Z = 4 x1 + 7 x2

terhadap

x1 + x2 ≤ 7 5 x1 + 9 x2 ≤ 45 x1 , dan x2 positif

Syntax program pada LINGO 8.0 !Fungsi Objektif; max=4*(x1)+7*(x2); !Kendala; x1+x2<=7; 5*(x1)+9*(x2)<=45; x1>=0;x2>=0; end

3.

Subproblem 3 Max Z = 4 x1 + 7 x2 terhadap

x1 + x2 ≤ 7 5 x1 + 9 x2 ≤ 45

Hasil yang diperoleh

x1 ≥ 0, x2 ≥ 3

Syntax program pada LINGO 8.0 !Fungsi Objektif; max=4*(x1)+7*(x2); !Kendala; x1+x2<=7; 5*(x1)+9*(x2)<=45; x1>=0;x2>=3; end 2.



x1 + x2 ≤ 7 5 x1 + 9 x2 ≤ 45 x1 ≥ 0, x2 ≤ 2

Syntax program pada LINGO 8.0 !Fungsi Objektif; max=4*(x1)+7*(x2); !Kendala; x1+x2<=7; 5*(x1)+9*(x2)<=45; x1>=0;x2<=2; end Hasil yang diperoleh

4.


x1 + x2 ≤ 7 5 x1 + 9 x2 ≤ 45 x1 ≥ 4, x2 ≥ 3

Syntax program pada LINGO 8.0 !Fungsi Objektif; max=4*(x1)+7*(x2); !Kendala; x1+x2<=7; 5*(x1)+9*(x2)<=45; x1>=4;x2>=3; end Hasil yang diperoleh

!Fungsi Objektif; max=4*(x1)+7*(x2); !Kendala; x1+x2<=7; 5*(x1)+9*(x2)<=45; x1<=3;x2<=3; end


5.


x1 + x2 ≤ 7

7.

Max Z = 4 x1 + 7 x2

5 x1 + 9 x2 ≤ 45 x1 ≤ 3, x2

Subproblem 7 terhadap

≥3

x1 + x2 ≤ 7 5 x1 + 9 x2 ≤ 45 x1 ≤ 3, x2 ≥ 4

Syntax program pada LINGO 8.0 !Fungsi Objektif; max=4*(x1)+7*(x2); !Kendala; x1+x2<=7; 5*(x1)+9*(x2)<=45; x1<=3;x2>=3; end

Syntax program pada LINGO 8.0 !Fungsi Objektif; max=4*(x1)+7*(x2); !Kendala; x1+x2<=7; 5*(x1)+9*(x2)<=45; x1<=3;x2>=4; end



6.


x1 + x2 ≤ 7 5 x1 + 9 x2 ≤ 45 x1 ≤ 3, x2

≤3

Syntax program pada LINGO 8.0

8.

Subproblem 9 Max Z = 4 x1 + 7 x2

terhadap

9.

x1 + x2 ≤ 7

terhadap

x1 + x2 ≤ 7

5 x1 + 9 x2 ≤ 45

5 x1 + 9 x2 ≤ 45

x1 ≥ 2, x2 ≥ 4

x1 ≤ 1, x2 ≤ 4

Syntax program pada LINGO 8.0 !Fungsi Objektif; max=4*(x1)+7*(x2); !Kendala; x1+x2<=7; 5*(x1)+9*(x2)<=45; x1>=2;x2>=4; end

Syntax program pada LINGO 8.0 !Fungsi Objektif; max=4*(x1)+7*(x2); !Kendala; x1+x2<=7; 5*(x1)+9*(x2)<=45; x1<=1;x2<=4; end




x1 + x2 ≤ 7 5 x1 + 9 x2 ≤ 45 x1 ≤ 1, x2 ≥ 4

Syntax program pada LINGO 8.0 !Fungsi Objektif; max=4*(x1)+7*(x2); !Kendala; x1+x2<=7; 5*(x1)+9*(x2)<=45; x1<=1;x2>=4; end Hasil yang diperoleh

11. Subproblem 11 Max Z = 4 x1 + 7 x2 terhadap

x1 + x2 ≤ 7 5 x1 + 9 x2 ≤ 45 x1 ≤ 1, x2 ≥ 5

Syntax program pada LINGO 8.0 !Fungsi Objektif; max=4*(x1)+7*(x2); !Kendala; x1+x2<=7; 5*(x1)+9*(x2)<=45; x1<=1;x2>=5; end Hasil yang diperoleh

10. Subproblem 10 Max Z = 4 x1 + 7 x2

Lampiran 3 Syntax dan Hasil Komputasi Program LINGO 8.0 untuk Masalah Penjadwalan Sekolah Menengah Masa Depan Berikut akan diperlihatkan syntax masalah penjadwalan Sekolah Menengah Masa Depan MODEL: TITLE JADWAL KEGIATAN BELAJAR MENGAJAR SEKOLAH MENENGAH MASA DEPAN; SETS: HARI/HR1..HR6/; PERIODE_WAKTU/PW1..PW7/; KELAS/KL1..KL10/:A; GURU/GU1..GU23/; MATA_PELAJARAN/MP1..MP13/; LINKS(HARI,PERIODE_WAKTU,KELAS,GURU,MATA_PELAJARAN):X; LINKS1(PERIODE_WAKTU,GURU,MATA_PELAJARAN):P; LINKS2(KELAS,GURU):B; LINKS3(KELAS,GURU,MATA_PELAJARAN):D; ENDSETS DATA: A= 37 37 ; P= 1000 1000 1000 1000 1000 1000 1000 160 1000 80 1000 1000 1000 1000 1000 1000 160 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000

37

1000 1000 1000 1000 0 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000

37

37

1000 1000 0 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000

37

1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 0 1000 1000 1000 1000

37

1000 1000 1000 160 1000 1000 1000 160 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 160 1000

37

37

1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 160 1000 1000 1000 160 1000 160 1000

37

1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 160 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000

0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000

1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 160 1000 1000 1000 1000 1000 1000 1000 1000

1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 80 1000 1000 1000 1000 160 1000 1000 1000 1000 1000

1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 80 160 1000 1000 160

1000 160 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 160 1000 1000 1000 1000 1000 1000

1000 1000 1000 1000 1000 1000 1000 1000 120 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 80 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000

1000 1000 1000 120 40 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 80 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000

1000 1000 1000 1000 0 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 0 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000

1000 1000 0 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000

1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 0 1000 1000 1000

1000 1000 1000 120 1000 1000 1000 120 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 120 1000 1000 1000 1000 80 1000 1000 1000 80 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 80

1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 120 1000 1000 1000 120 1000 120 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 80 1000 1000 1000 80 1000 80

1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 120 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 80 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000

0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 0 1000 1000 1000 1000 1000 1000 1000 1000

1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 120 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 80 1000 1000 1000 1000 1000 1000 1000

1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 40 1000 1000 1000 1000 120 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 80 1000 1000 1000 1000

1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 40 120 1000 1000 120 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 80 1000 1000

1000 120 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 120 1000 1000 1000 1000 1000 1000 1000 80 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 80 1000 1000 1000 1000 1000

1000 1000 1000 1000 1000 1000 1000 1000 1000 40 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000

1000 1000 1000 1000 40 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 40 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000

1000 1000 1000 1000 1000 40 1000 40 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 40 1000 1000 1000 1000 1000 1000 80 1000 80 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 80

1000 1000 1000 40 1000 1000 1000 1000 1000 1000 40 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 80 1000 1000 1000 1000 1000 1000 80 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000

1000 1000 1000 1000 1000 1000 40 1000 1000 1000 1000 1000 1000 40 1000 1000 1000 1000 1000 40 1000 1000 1000 1000 1000 1000 1000 1000 1000 80 1000 1000 1000 1000 1000 1000 80 1000 1000 1000 1000 1000 80 1000 1000

1000 1000 1000 1000 40 1000 1000 1000 40 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 40 1000 1000 1000 1000 0 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000

1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 40 1000 1000 1000 40 1000 40 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 0 1000

1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 40 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000

1000 40 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 40 1000 40 1000 1000 1000 1000 1000 1000 1000 1000 1000 80 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 80 1000 80 1000 1000 1000 1000 1000 1000 1000

1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 40 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000

1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 40 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 40 1000 1000 1000 1000 0 1000 1000 1000

80 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 40 1000 1000 40 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 40 0 1000

1000 1000 40 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 40 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000

1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000

1000 1000 1000 1000 1000 0 120 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 160 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000

1000 1000 1000 1000 1000 1000 120 1000 120 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 120 1000 1000 1000 1000 1000 1000 160 1000 160 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000

1000 1000 1000 1000 120 1000 1000 1000 1000 1000 1000 120 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 160 1000 1000 1000 1000 1000 1000 160 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000

1000 1000 1000 1000 1000 1000 1000 120 1000 1000 1000 1000 1000 1000 120 1000 1000 1000 1000 1000 120 1000 1000 1000 1000 1000 1000 1000 1000 1000 160 1000 1000 1000 1000 1000 1000 160 1000 1000 1000 1000 1000 160 1000

0 1000 1000 1000 1000 0 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 0 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000

0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 0 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 0

1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000

1000 1000 120 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 120 1000 120 1000 1000 1000 1000 1000 1000 1000 1000 1000 160 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 160 1000 160 1000 1000 1000 1000 1000 1000

1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000

1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 120 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 160 1000 1000 1000 1000 0 1000 1000

1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 120 0 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 160 0

1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000 1000 1000

1000 1000 1000 ; B= 4 1 4 0 4 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 ; D= 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0

1000 160 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 0 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 0 1000

0 5 5 5 5 5 0 0 0 0

0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0

6 6 6 0 0 0 2 2 2 2

0 0 0 2 2 2 4 4 4 4

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 5 5 5 5

0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0

0 0 0 4 4 4 0 0 0 0

0 0 0 0 0 4 4 4 4 4

0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

2 2 2 2 2 2 2 2 2 2

5 0 0 0 0 0 5 5 5 5

0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0

2 2 2 2 2 2 2 2 2 2

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 4 4 4 0 0 0 0

7 7 7 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0

0 0 0 0 0 0 4 4 4 4

2 2 2 2 2 2 2 2 2 2

4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0

0 0 0 2 2 2 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 1 1 1 1 1 0 0 0 0

0 0 0 2 2 2 2 2 2 2

0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 5 7 5 2 2 2 2

2 2 2 0 0 0 2 2 2 2

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

4 4 4 0 0 0 0 0 0 0

0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

2 2 2 4 4 0 0 0 0 0

0 0 0 2 0 2 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0

0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0

2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2

0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0

0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0

0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0

0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0

0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0

0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0

0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0

0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ; ENDDATA

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0

0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

!FUNGSI OBJEKTIF; MIN=@SUM(LINKS(I,J,K,L,M):P(J,L,M)*X); !TERHADAP KENDALA-KENDALA; !Kendala 1. Tidak boleh ada guru yang mengajar dalam dua kelas atau lebih pada periode waktu yang sama; @FOR(HARI(I):@FOR(PERIODE_WAKTU(J):@FOR(GURU(L):@SUM(KELAS(K): @SUM(MATA_PELAJARAN(M):X(I,J,K,L,M)))<=1)));

!Kendala 2. Untuk setiap hari dan setiap periode waktunya, kecuali periode waktu terakhir, semua kelas akan diajar oleh seorang guru dan sebuah mata pelajaran; @FOR(HARI(I):@FOR(PERIODE_WAKTU(J)|J#NE#7:@FOR(KELAS(K): @SUM(GURU(L):@SUM(MATA_PELAJARAN(M):X(I,J,K,L,M)))=1))); @FOR(HARI(I):@FOR(PERIODE_WAKTU(J)|J#EQ#7:@FOR(KELAS(K): @SUM(GURU(L):@SUM(MATA_PELAJARAN(M):X(I,J,K,L,M)))<=1))); !Kendala 3. Terpenuhinya jumlah periode waktu total yang dibutuhkan untuk masing-masing kelas selama seminggu; @FOR(KELAS(K):@SUM(HARI(I):@SUM(PERIODE_WAKTU(J):@SUM(GURU(L): @SUM(MATA_PELAJARAN(M):X(I,J,K,L,M)))))=A(K)); !Kendala 4. Terpenuhinya jumlah periode waktu mengajar guru L dikelas K; @FOR(KELAS(K):@FOR(GURU(L):@SUM(HARI(I):@SUM(PERIODE_WAKTU(J): @SUM(MATA_PELAJARAN(M):X(I,J,K,L,M))))=B(K,L))); !Kendala 5. Guru mengajar minimal satu periode waktu pada hari dimana guru tersebut telah dijadwalkan; @FOR(HARI(I):@FOR(GURU(L)|L#EQ#1:@SUM(PERIODE_WAKTU(J):@SUM(KELAS( K):@SUM(MATA_PELAJARAN(M):X(I,J,K,L+2,M)+X(I,J,K,L+3,M)+X(I,J,K,L+ 4,M)+X(I,J,K,L+5,M)+ X(I,J,K,L+7,M)+X(I,J,K,L+8,M)+X(I,J,K,L+9,M)+ X(I,J,K,L+10,M)+X(I,J,K,L+12,M)+X(I,J,K,L+14,M)+X(I,J,K,L+18,M)))) >=1)); @FOR(HARI(I)|I#GE#3:@FOR(GURU(L)|L#EQ#1:@SUM(PERIODE_WAKTU(J): @SUM(KELAS(K):@SUM(MATA_PELAJARAN(M):X(I,J,K,L,M))))>=1)); @FOR(HARI(I)|I#LE#3:@FOR(GURU(L)|L#EQ#2:@SUM(PERIODE_WAKTU(J): @SUM(KELAS(K):@SUM(MATA_PELAJARAN(M):X(I,J,K,L,M))))>=1)); @FOR(HARI(I)|I#LE#4:@FOR(GURU(L)|L#EQ#7:@SUM(PERIODE_WAKTU(J): @SUM(KELAS(K):@SUM(MATA_PELAJARAN(M):X(I,J,K,L,M))))>=1)); @FOR(HARI(I)|I#GE#3:@FOR(GURU(L)|L#EQ#12:@SUM(PERIODE_WAKTU(J): @SUM(KELAS(K):@SUM(MATA_PELAJARAN(M):X(I,J,K,L,M))))>=1)); @FOR(HARI(I)|I#NE#6:@FOR(GURU(L)|L#EQ#14:@SUM(PERIODE_WAKTU(J): @SUM(KELAS(K):@SUM(MATA_PELAJARAN(M):X(I,J,K,L,M))))>=1)); @FOR(HARI(I)|I#GE#4:@FOR(GURU(L)|L#EQ#16:@SUM(PERIODE_WAKTU(J): @SUM(KELAS(K):@SUM(MATA_PELAJARAN(M):X(I,J,K,L,M))))>=1)); @FOR(HARI(I)|I#GE#3:@FOR(GURU(L)|L#EQ#17:@SUM(PERIODE_WAKTU(J): @SUM(KELAS(K):@SUM(MATA_PELAJARAN(M):X(I,J,K,L,M))))>=1)); @FOR(HARI(I)|I#GE#2:@FOR(GURU(L)|L#EQ#18:@SUM(PERIODE_WAKTU(J): @SUM(KELAS(K):@SUM(MATA_PELAJARAN(M):X(I,J,K,L,M))))>=1)); @FOR(HARI(I)|I#LE#4:@FOR(GURU(L)|L#EQ#20:@SUM(PERIODE_WAKTU(J): @SUM(KELAS(K):@SUM(MATA_PELAJARAN(M):X(I,J,K,L,M))))>=1)); @FOR(HARI(I)|I#GE#3:@FOR(GURU(L)|L#EQ#21:@SUM(PERIODE_WAKTU(J): @SUM(KELAS(K):@SUM(MATA_PELAJARAN(M):X(I,J,K,L,M))))>=1)); @FOR(HARI(I)|I#LE#4:@FOR(GURU(L)|L#EQ#22:@SUM(PERIODE_WAKTU(J): @SUM(KELAS(K):@SUM(MATA_PELAJARAN(M):X(I,J,K,L,M))))>=1)); @FOR(HARI(I)|I#EQ#1#AND#I#EQ#6:@FOR(GURU(L)|L#EQ#23:@SUM(PERIODE_W AKTU(J):@SUM(KELAS(K):@SUM(MATA_PELAJARAN(M):X(I,J,K,L,M))))>=1));

!Kendala 6. Dalam seminggu setiap mata pelajaran akan diajarkan secara merata;

@FOR(HARI(I):@FOR(KELAS(K):@FOR(GURU(L):@FOR(MATA_PELAJARAN(M): @SUM(PERIODE_WAKTU(J):X(I,J,K,L,M))<=1)))); !Jumlah periode waktu yang dibutuhkan kelas K untuk mata pelajaran M; @FOR(GURU(L):@FOR(KELAS(K):@FOR(MATA_PELAJARAN(M):@SUM(HARI(I): @SUM(PERIODE_WAKTU(J):X(I,J,K,L,M)))=D(K,L,M))));

!Kendala 7. Untuk beberapa guru yang dijadwalkan pada beberapa hari saja dalam seminggu maka untuk hari di mana guru tersebut tidak dijadwalkan akan memenuhi kendala sebagai berikut; @FOR(GURU(L)|L#EQ#1:@SUM(HARI(I)|I#LE#2:@SUM(PERIODE_WAKTU(J): @SUM(KELAS(K):@SUM(MATA_PELAJARAN(M):X(I,J,K,L,M)))))=0); @FOR(GURU(L)|L#EQ#2:@SUM(HARI(I)|I#GE#4:@SUM(PERIODE_WAKTU(J): @SUM(KELAS(K):@SUM(MATA_PELAJARAN(M):X(I,J,K,L,M)))))=0); @FOR(GURU(L)|L#EQ#7:@SUM(HARI(I)|I#GE#5:@SUM(PERIODE_WAKTU(J): @SUM(KELAS(K):@SUM(MATA_PELAJARAN(M):X(I,J,K,L,M)))))=0); @FOR(GURU(L)|L#EQ#12:@SUM(HARI(I)|I#LE#2:@SUM(PERIODE_WAKTU(J): @SUM(KELAS(K):@SUM(MATA_PELAJARAN(M):X(I,J,K,L,M)))))=0); @FOR(GURU(L)|L#EQ#14:@SUM(HARI(I)|I#EQ#6:@SUM(PERIODE_WAKTU(J): @SUM(KELAS(K):@SUM(MATA_PELAJARAN(M):X(I,J,K,L,M)))))=0); @FOR(GURU(L)|L#EQ#16:@SUM(HARI(I)|I#LE#3:@SUM(PERIODE_WAKTU(J): @SUM(KELAS(K):@SUM(MATA_PELAJARAN(M):X(I,J,K,L,M)))))=0); @FOR(GURU(L)|L#EQ#17:@SUM(HARI(I)|I#LE#2:@SUM(PERIODE_WAKTU(J): @SUM(KELAS(K):@SUM(MATA_PELAJARAN(M):X(I,J,K,L,M)))))=0); @FOR(GURU(L)|L#EQ#18:@SUM(HARI(I)|I#EQ#1:@SUM(PERIODE_WAKTU(J): @SUM(KELAS(K):@SUM(MATA_PELAJARAN(M):X(I,J,K,L,M)))))=0); @FOR(GURU(L)|L#EQ#20:@SUM(HARI(I)|I#GE#5:@SUM(PERIODE_WAKTU(J): @SUM(KELAS(K):@SUM(MATA_PELAJARAN(M):X(I,J,K,L,M)))))=0); @FOR(GURU(L)|L#EQ#21:@SUM(HARI(I)|I#LE#2:@SUM(PERIODE_WAKTU(J): @SUM(KELAS(K):@SUM(MATA_PELAJARAN(M):X(I,J,K,L,M)))))=0); @FOR(GURU(L)|L#EQ#22:@SUM(HARI(I)|I#GE#5:@SUM(PERIODE_WAKTU(J): @SUM(KELAS(K):@SUM(MATA_PELAJARAN(M):X(I,J,K,L,M)))))=0); @FOR(GURU(L)|L#EQ#23:@SUM(HARI(I)|I#NE#1#AND#I#NE#6:@SUM(PERIODE_W AKTU(J):@SUM(KELAS(K):@SUM(MATA_PELAJARAN(M):X(I,J,K,L,M)))))=0); !Kendala 8. X adalah variabel biner; @FOR(LINKS:@BIN(X)); END Hasil yang diperoleh adalah sebagai berikut; (Tidak semua hasil ditampilkan, hanya untuk variable x yang bernilai 1 saja yang ditampilkan) Global optimal solution found at iteration: Objective value:

40663 4760.000

Model Title: JADWAL KEGIATAN BELAJAR MENGAJAR SEKOLAH MENENGAH MASA DEPAN Variable A( KL1) A( KL2) A( KL3) A( KL4) A( KL5)

Value 37.00000 37.00000 37.00000 37.00000 37.00000

Reduced Cost 0.000000 0.000000 0.000000 0.000000 0.000000

A( KL6) A( KL7) A( KL8) A( KL9) A( KL10) X( HR1, PW1, KL1, GU13, MP5) X( HR1, PW1, KL2, GU22, MP7) X( HR1, PW1, KL3, GU3, MP4) X( HR1, PW1, KL4, GU11, MP8) X( HR1, PW1, KL5, GU19, MP5) X( HR1, PW1, KL6, GU7, MP3) X( HR1, PW1, KL7, GU14, MP9) X( HR1, PW1, KL8, GU5, MP3) X( HR1, PW1, KL9, GU10, MP4) X( HR1, PW1, KL10, GU6, MP5) X( HR1, PW2, KL1, GU11, MP8) X( HR1, PW2, KL2, GU4, MP6) X( HR1, PW2, KL3, GU13, MP5) X( HR1, PW2, KL4, GU7, MP3) X( HR1, PW2, KL5, GU3, MP4) X( HR1, PW2, KL6, GU19, MP5) X( HR1, PW2, KL7, GU6, MP5) X( HR1, PW2, KL8, GU14, MP9) X( HR1, PW2, KL9, GU5, MP3) X( HR1, PW2, KL10, GU10, MP4) X( HR1, PW3, KL1, GU9, MP1) X( HR1, PW3, KL2, GU13, MP5) X( HR1, PW3, KL3, GU4, MP6) X( HR1, PW3, KL4, GU19, MP5) X( HR1, PW3, KL5, GU7, MP3) X( HR1, PW3, KL6, GU3, MP4) X( HR1, PW3, KL7, GU5, MP3) X( HR1, PW3, KL8, GU10, MP4) X( HR1, PW3, KL9, GU6, MP5) X( HR1, PW3, KL10, GU14, MP9) X( HR1, PW4, KL1, GU4, MP6) X( HR1, PW4, KL2, GU13, MP11) X( HR1, PW4, KL3, GU20, MP12) X( HR1, PW4, KL4, GU3, MP4) X( HR1, PW4, KL5, GU9, MP1) X( HR1, PW4, KL6, GU5, MP2) X( HR1, PW4, KL7, GU8, MP6) X( HR1, PW4, KL8, GU11, MP8) X( HR1, PW4, KL9, GU15, MP10) X( HR1, PW4, KL10, GU19, MP12) X( HR1, PW5, KL1, GU20, MP12) X( HR1, PW5, KL2, GU3, MP4) X( HR1, PW5, KL3, GU13, MP11) X( HR1, PW5, KL4, GU23, MP12) X( HR1, PW5, KL5, GU22, MP6) X( HR1, PW5, KL6, GU15, MP10) X( HR1, PW5, KL7, GU11, MP8) X( HR1, PW5, KL8, GU4, MP2) X( HR1, PW5, KL9, GU8, MP6) X( HR1, PW5, KL10, GU9, MP1) X( HR1, PW6, KL1, GU10, MP4) X( HR1, PW6, KL2, GU15, MP10) X( HR1, PW6, KL3, GU4, MP2) X( HR1, PW6, KL4, GU22, MP6) X( HR1, PW6, KL5, GU11, MP8) X( HR1, PW6, KL6, GU23, MP12) X( HR1, PW6, KL7, GU9, MP1) X( HR1, PW6, KL8, GU8, MP6) X( HR1, PW6, KL9, GU20, MP7) X( HR1, PW6, KL10, GU2, MP13)

37.00000 37.00000 37.00000 37.00000 37.00000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000

0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 160.0000 0.000000 160.0000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 120.0000 120.0000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 80.00000 0.000000 80.00000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 40.00000 0.000000 40.00000 40.00000 40.00000 0.000000 40.00000 40.00000 40.00000 0.000000 0.000000 80.00000 40.00000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 120.0000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000

X( HR1, PW7, KL6, GU11, MP8) X( HR1, PW7, KL8, GU20, MP7) X( HR1, PW7, KL10, GU15, MP10) X( HR2, PW1, KL1, GU10, MP4) X( HR2, PW1, KL2, GU13, MP5) X( HR2, PW1, KL3, GU11, MP8) X( HR2, PW1, KL4, GU3, MP4) X( HR2, PW1, KL5, GU7, MP3) X( HR2, PW1, KL6, GU19, MP5) X( HR2, PW1, KL7, GU5, MP3) X( HR2, PW1, KL8, GU14, MP9) X( HR2, PW1, KL9, GU6, MP5) X( HR2, PW1, KL10, GU9, MP1) X( HR2, PW2, KL1, GU20, MP12) X( HR2, PW2, KL2, GU4, MP2) X( HR2, PW2, KL3, GU13, MP5) X( HR2, PW2, KL4, GU19, MP5) X( HR2, PW2, KL5, GU3, MP4) X( HR2, PW2, KL6, GU7, MP3) X( HR2, PW2, KL7, GU6, MP5) X( HR2, PW2, KL8, GU10, MP4) X( HR2, PW2, KL9, GU14, MP9) X( HR2, PW2, KL10, GU5, MP3) X( HR2, PW3, KL1, GU13, MP5) X( HR2, PW3, KL2, GU4, MP6) X( HR2, PW3, KL3, GU3, MP4) X( HR2, PW3, KL4, GU7, MP3) X( HR2, PW3, KL5, GU19, MP5) X( HR2, PW3, KL6, GU5, MP2) X( HR2, PW3, KL7, GU14, MP9) X( HR2, PW3, KL8, GU6, MP5) X( HR2, PW3, KL9, GU8, MP6) X( HR2, PW3, KL10, GU10, MP4) X( HR2, PW4, KL1, GU4, MP2) X( HR2, PW4, KL2, GU22, MP7) X( HR2, PW4, KL3, GU9, MP1) X( HR2, PW4, KL4, GU5, MP2) X( HR2, PW4, KL5, GU15, MP10) X( HR2, PW4, KL6, GU3, MP4) X( HR2, PW4, KL7, GU20, MP7) X( HR2, PW4, KL8, GU8, MP6) X( HR2, PW4, KL9, GU10, MP4) X( HR2, PW4, KL10, GU6, MP5) X( HR2, PW5, KL1, GU4, MP6) X( HR2, PW5, KL2, GU3, MP4) X( HR2, PW5, KL3, GU15, MP10) X( HR2, PW5, KL4, GU11, MP8) X( HR2, PW5, KL5, GU22, MP6) X( HR2, PW5, KL6, GU9, MP1) X( HR2, PW5, KL7, GU8, MP6) X( HR2, PW5, KL8, GU2, MP13) X( HR2, PW5, KL9, GU18, MP11) X( HR2, PW5, KL10, GU20, MP7) X( HR2, PW6, KL1, GU2, MP13) X( HR2, PW6, KL2, GU15, MP10) X( HR2, PW6, KL3, GU22, MP7) X( HR2, PW6, KL4, GU18, MP11) X( HR2, PW6, KL5, GU11, MP8) X( HR2, PW6, KL6, GU8, MP6) X( HR2, PW6, KL7, GU10, MP4) X( HR2, PW6, KL8, GU20, MP7) X( HR2, PW6, KL9, GU9, MP1) X( HR2, PW6, KL10, GU4, MP2) X( HR2, PW7, KL4, GU22, MP6) X( HR3, PW1, KL1, GU1, MP9)

1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000

0.000000 0.000000 0.000000 0.000000 0.000000 160.0000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 160.0000 120.0000 120.0000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 80.00000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 80.00000 0.000000 40.00000 40.00000 40.00000 0.000000 40.00000 40.00000 40.00000 40.00000 40.00000 40.00000 0.000000 80.00000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 120.0000 0.000000 0.000000 0.000000 0.000000 0.000000


1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000

0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 40.00000 0.000000 40.00000 40.00000 40.00000 40.00000 40.00000 0.000000 40.00000 40.00000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 40.00000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000


1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000

0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 40.00000 40.00000 40.00000 40.00000 0.000000 40.00000 40.00000 40.00000 0.000000 40.00000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 40.00000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000


1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000

0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 40.00000 40.00000 0.000000 0.000000 0.000000 40.00000 40.00000 40.00000 40.00000 40.00000 0.000000 0.000000 80.00000 0.000000 0.000000 0.000000 40.00000 0.000000 0.000000 0.000000 120.0000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 120.0000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 160.0000 0.000000 0.000000 0.000000 0.000000

X( HR6, PW2, KL2, GU1, MP9) X( HR6, PW2, KL3, GU13, MP5) X( HR6, PW2, KL4, GU12, MP9) X( HR6, PW2, KL5, GU19, MP5) X( HR6, PW2, KL6, GU3, MP4) X( HR6, PW2, KL7, GU10, MP4) X( HR6, PW2, KL8, GU5, MP3) X( HR6, PW2, KL9, GU6, MP5) X( HR6, PW2, KL10, GU8, MP6) X( HR6, PW3, KL1, GU1, MP9) X( HR6, PW3, KL2, GU13, MP5) X( HR6, PW3, KL3, GU21, MP3) X( HR6, PW3, KL4, GU3, MP4) X( HR6, PW3, KL5, GU12, MP9) X( HR6, PW3, KL6, GU19, MP5) X( HR6, PW3, KL7, GU15, MP10) X( HR6, PW3, KL8, GU10, MP4) X( HR6, PW3, KL9, GU5, MP3) X( HR6, PW3, KL10, GU6, MP5) X( HR6, PW4, KL1, GU13, MP11) X( HR6, PW4, KL2, GU3, MP4) X( HR6, PW4, KL3, GU11, MP8) X( HR6, PW4, KL4, GU9, MP1) X( HR6, PW4, KL5, GU5, MP2) X( HR6, PW4, KL6, GU8, MP6) X( HR6, PW4, KL7, GU19, MP12) X( HR6, PW4, KL8, GU18, MP11) X( HR6, PW4, KL9, GU4, MP2) X( HR6, PW4, KL10, GU15, MP10) X( HR6, PW5, KL1, GU10, MP4) X( HR6, PW5, KL2, GU4, MP6) X( HR6, PW5, KL3, GU9, MP1) X( HR6, PW5, KL4, GU16, MP7) X( HR6, PW5, KL5, GU19, MP12) X( HR6, PW5, KL6, GU23, MP12) X( HR6, PW5, KL7, GU8, MP6) X( HR6, PW5, KL8, GU11, MP8) X( HR6, PW5, KL9, GU15, MP10) X( HR6, PW5, KL10, GU18, MP11) X( HR6, PW6, KL1, GU15, MP10) X( HR6, PW6, KL2, GU9, MP1) X( HR6, PW6, KL3, GU3, MP4) X( HR6, PW6, KL4, GU23, MP12) X( HR6, PW6, KL5, GU16, MP7) X( HR6, PW6, KL6, GU17, MP13) X( HR6, PW6, KL7, GU18, MP11) X( HR6, PW6, KL8, GU8, MP6) X( HR6, PW6, KL9, GU11, MP8) X( HR6, PW6, KL10, GU4, MP2) X( HR6, PW7, KL3, GU4, MP6)

1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000 1.000.000

0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 120.0000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 80.00000 0.000000 0.000000 0.000000 0.000000 40.00000 40.00000 40.00000 0.000000 40.00000 0.000000 40.00000 40.00000 40.00000 80.00000 0.000000 0.000000 0.000000 40.00000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 120.0000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000

PENYELESAIAN MASALAH PENJADWALAN MATA PELAJARAN SEKOLAH MENENGAH PERTAMA MENGGUNAKAN PEMROGRAMAN LINEAR INTEGER MAHNURI

Recommend Documents