PENGOPTIMUMAN BERBASIS DUAL MASALAH PENJADWALAN TIGA HARI KERJA DALAM SEMINGGU SECARA SIKLIS
NUR HADI
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2014
PERNYATAAN MENGENAI SKRIPSI DAN SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA Dengan ini saya menyatakan bahwa skripsi berjudul Pengoptimuman Berbasis Dual Masalah Penjadwalan Tiga Hari Kerja dalam Seminggu Secara Siklis adalah benar karya saya dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apa pun kepada perguruan tinggi mana pun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir skripsi ini. Dengan ini saya melimpahkan hak cipta dari karya tulis saya kepada Institut Pertanian Bogor. Bogor, November 2014 Nur Hadi NIM G54080039
4
ABSTRAK NUR HADI. Pengoptimuman Berbasis Dual Masalah Penjadwalan Tiga Hari Kerja dalam Seminggu Secara Siklis. Dibimbing oleh FARIDA HANUM dan BIB PARUHUM SILALAHI. Solusi dual dapat digunakan untuk menyelesaikan masalah optimasi penjadwalan tiga hari kerja dengan empat hari libur secara turut-turut dalam seminggu. Pertama masalah dual diselesaikan untuk meminimumkan banyaknya total pekerja. Setelah itu solusi dual digunakan untuk menetapkan pola kerja yang meminimumkan biaya total pekerja. Dari kedua tahap itu dirumuskan algoritme solusi dual untuk menyelesaikan masalah optimasi penjadwalan tersebut. Kata kunci: dual, integer programming, optimasi, penjadwalan tenaga kerja.
ABSTRACT NUR HADI. Dual-Based Optimization of Cyclic Three-Day Workweek Scheduling. Supervised by FARIDA HANUM dan BIB PARUHUM SILALAHI. The dual solution can be utilized in solving optimization problem of labor scheduling for three consecutive workdays and four consecutive off days per week. Firstly, the dual solution is used to minimize the number of workers. Then, the solution provides the calculation to set work load that minimizes labor cost. An algorithm of dual solution is formulated to solve optimization problem of labor scheduling. Keywords: dual, integer programming, optimization, workforce scheduling.
5
PENGOPTIMUMAN BERBASIS DUAL MASALAH PENJADWALAN TIGA HARI KERJA DALAM SEMINGGU SECARA SIKLIS
NUR HADI
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika
DEPARTEMEN MATEMATIKA FAKULATAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2014
6
7
Judul Skripsi : Pengoptimuman Berbasis Dual Masalah Penjadwalan Tiga Hari Kerja dalam Seminggu Secara Siklis Nama : Nur Hadi NIM : G54080039
Disetujui
Dra Farida Hanum, MSi Pembimbing I
Dr Ir Bib Paruhum Silalahi, MKom Pembimbing II
Diketahui oleh
Dr Toni Bakhtiar, MSc Ketua Departemen
Tanggal Lulus:
8
9
PRAKATA Puji dan syukur penulis panjatkan kepada Allah subhanahu wa ta’ala atas segala berkah-Nya sehingga karya ilmiah ini berhasil diselesaikan dengan baik. Terima kasih banyak dan penghargaan penulis sampaikan kepada Ibu Dra Farida Hanum, MSi dan Bapak Dr Ir Bib Paruhum Silalahi, MKom selaku pembimbing serta Drs Prapto Tri Supriyo, MKom sebagai penguji yang telah banyak memberi saran. Di samping itu, terima kasih juga penulis sampaikan kepada semua dosen dan staf di Departemen Matematika atas segala ilmu yang diberikan dan bantuannya selama masa perkuliahan. Ungkapan terima kasih juga disampaikan kepada ayah, ibu, serta seluruh keluarga, atas segala dukungannya, doa dan kasih sayangnya. Tak lupa ucapan terima kasih juga kepada teman-teman Matematika 45, kakak/adik kelas dan seluruh pihak yang telah mendukung penulis menyelesaikan karya ilmiah ini. Mohon maaf penulis tidak dapat menyebutkannya satu per satu. Akhir kata, semoga karya ilmiah ini bermanfaat bagi yang membutuhkannya.
Bogor, November 2014
Nur Hadi
10
11
DAFTAR ISI DAFTAR TABEL
v
PENDAHULUAN
1
Latar Belakang
1
Tujuan Penelitian
1
LANDASAN TEORI
1
MODEL PENJADWALAN
3
SOLUSI DUAL MASALAH (3,7)
5
Penentuan Total Pekerja Minimum
6
Penetapan Pola Kerja Berdasarkan Biaya
7
Algoritme Solusi Dual
10
CONTOH KASUS
12
SIMPULAN
14
DAFTAR PUSTAKA
14
LAMPIRAN
15
RIWAYAT HIDUP
24
12
DAFTAR TABEL 1. Pola penjadwalan masalah (3,7)
3
2. Hasil penyelesaian model dengan LINGO 11.0
4
3. Empat variabel berurutan
7
4. Biaya pekerja
8
5. Nilai
untuk semua kemungkinan nilai W
11
6. Hasil penjadwalan Contoh 2
12
7. Hasil penjadwalan Contoh 3
13
DAFTAR LAMPIRAN 1. Sintak dan hasil komputasi program LINGO 11.0 untuk masalah (3,7)
15
2. Bentuk lain persamaan (9) 3. Penetapan pola kerja untuk 4. Penetapan pola kerja untuk
16 ∑
17 18
1
PENDAHULUAN Latar Belakang Masalah penjadwalan pekerja merupakan masalah praktis yang muncul dalam sebuah perusahaan yang beroperasi tujuh hari dalam seminggu. Karena itu pekerja perlu diberikan pola penjadwalan kerja yang jelas dan terperinci. Secara umum masalah penjadwalan pekerja dapat diklasifikasikan menjadi tiga jenis, yaitu days-off, shift, dan tour scheduling (Baker 1976). Days-off scheduling ialah masalah menentukan hari kerja dan waktu istirahat pekerja dalam waktu tertentu. Sementara itu shift scheduling ialah masalah menentukan waktu awal kerja, lamanya shift, interval dan waktu awal istirahat pekerja. Bila dalam days-off dan shift scheduling harus ditentukan dalam suatu pola, maka masalahnya menjadi masalah menentukan rute penjadwalan atau tour scheduling. Dalam karya ilmiah ini penjadwalan pekerja yang digunakan adalah days-off scheduling. Secara umum days-off scheduling yang banyak diterapkan oleh sebuah perusahaan yang beroperasi tujuh hari dalam seminggu adalah pola penjadwalan kerja dengan lima hari kerja dan dua hari libur secara berturut-turut (Alfares 2001) atau atau empat hari kerja dan tiga hari libur secara berturut-turut (Alfares 2000). Masalah days-off scheduling dapat diselesaikan dengan beberapa cara, di antaranya integer programming (IP) dan solusi dual. Dengan merujuk jurnal yang berjudul Dual-based optimization of cycling three-day workweek scheduling, yang ditulis oleh Hesham K. Alfares, karya ilmiah ini selanjutnya akan membahas pola penjadwalan kerja dengan tiga hari kerja dan empat hari libur dalam seminggu secara burturut-turut dengan solusi dual.
Tujuan Penelitian Tujuan dari karya ilmiah ini ialah meminimumkan banyaknya total pekerja dan menetapkan pola kerja yang meminimumkan biaya total pekerja dengan menggunakan solusi dual.
LANDASAN TEORI Untuk memahami masalah dalam karya ilmiah ini diperlukan beberapa pengertian sebagai berikut. Pemrograman Linear Integer Pemrograman integer atau Integer Programming (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
2 integer, maka disebut mixed integer programming. IP dengan semua variabelnya harus bernilai 0 atau 1 disebut 0-1 IP. (Winston 2004) Dualitas Terkait dengan suatu masalah optimasi linear, terdapat masalah optimasi linear lain yang berpadanan. Kedua masalah ini dikenal dengan masalah primal dan masalah dual dari suatu optimasi linear. Bentuk standar dari masalah primal untuk kasus maksimisasi adalah: max ∑ terhadap
∑
Bentuk standar dari masalah dual untuk masalah primal di atas adalah: min ∑ terhadap
∑
(Chvatal 1983) Bila dibandingkan, maka dua hubungan antara masalah primal dan dual, yaitu: 1. Koefisien fungsi tujuan pada primal menjadi konstanta ruas kanan pada dual. Sebaliknya, konstanta ruas kanan pada primal menjadi koefisien fungsi tujuan pada dual. 2. Tanda ketidaksamaan pada pembatas menjadi terbalik, jika pada primal berubah menjadi pada dual. 3. Fungsi tujuan berubah bentuk, maksimisasi pada primal akan berubah menjadi minimisasi pada dual. 4. Setiap kolom kendala pada primal berhubungan dengan baris kendala pada dual. Sebaliknya, setiap baris kendala pada primal akan menjadi kolom kendala pada dual. 5. Dual dari dual adalah primal. Teorema 1 (Complementary Slackness) Solusi fisibel masalah primal hanya jika terdapat bilangan-bilangan ∑
bila
adalah solusi optimal jika dan sehingga
3 bila ∑ dan ∑
(Chvatal 1983)
MODEL PENJADWALAN Secara umum pola penjadwalan pekerja yang banyak digunakan oleh sebuah perusahaan yang beroperasi tujuh hari kerja dalam seminggu adalah lima hari kerja dengan dua hari libur berturut-turut atau empat hari kerja dengan tiga hari libur berturut-turut. Namun dalam karya ilmiah ini pola penjadwalan pekerja yang digunakan adalah pola penjadwalan tiga hari kerja dengan empat hari libur secara beturut-turut dalam seminggu atau biasa disebut dengan masalah (3,7). Jadi, pekerja hanya bekerja selama tiga hari secara berturut-turut dalam seminggu kemudian libur selama empat hari berturut-turut. Pola penjadwalan masalah (3,7) dapat dilihat pada Tabel 1 berikut: Misalkan hari 1 = Senin, 2 = Selasa, 3 = Rabu, 4 = Kamis, 5 = Jumat, 6 = Sabtu, 7 = Minggu. Tabel 1 Pola penjadwalan masalah (3,7) Pola ke 1 2 3 4 5 6 7
Hari Kerja 5, 6, 7 1, 6, 7 1, 2, 7 1, 2, 3 2, 3, 4 3, 4, 5 4, 5, 6
Hari Libur 1, 2, 3, 4 2, 3, 4, 5 3, 4, 5, 6 4, 5, 6, 7 1, 5, 6, 7 1, 2, 6, 7 1, 2, 3, 7
Masalah (3,7) dapat diformulasikan ke dalam integer programming, dengan menyatakan indeks untuk hari , ialah indeks untuk pola kerja , menyatakan banyaknya pekerja yang dibutuhkan pada hari , dan menyatakan banyaknya pekerja yang bekerja pada pola kerja . Formulasi integer programming (IP) masalah (3,7) ialah sebagai berikut: min
∑
4 terhadap (banyaknya pekerja yang bekerja pada hari Senin harus lebih besar atau sama dengan banyak pekerja yang dibutuhkan pada hari Senin) (banyaknya pekerja yang bekerja pada hari Selasa harus lebih besar atau sama dengan banyak pekerja yang dibutuhkan pada hari Selasa) (banyaknya pekerja yang bekerja pada hari Rabu harus lebih besar atau sama dengan banyak pekerja yang dibutuhkan pada hari Rabu) (banyaknya pekerja yang bekerja pada hari Kamis harus lebih besar atau sama dengan banyak pekerja yang dibutuhkan pada hari Kamis) (banyaknya pekerja yang bekerja pada Jumat harus lebih besar atau sama dengan banyak pekerja yang dibutuhkan pada hari Jumat) (banyaknya pekerja yang bekerja pada hari Sabtu harus lebih besar atau sama dengan banyak pekerja yang dibutuhkan pada hari Sabtu) (banyaknya pekerja yang bekerja pada hari Minggu harus lebih besar atau sama dengan banyak pekerja yang dibutuhkan pada hari Minggu) Sebagai ilustrasi diberikan contoh IP masalah (3,7) Contoh 1 Misalkan
,
,
,
,
,
,
Dengan bantuan software LINGO 11.0 (Lampiran 1), solusi masalah (3,7) adalah seperti pada Tabel 2. Tabel 2 Hasil penyelesaian model dengan LINGO 11.0 Hari Kerja Jumat-Sabtu-Minggu Senin-Sabtu-Minggu Senin-Selasa-Minggu Senin-Selasa-Rabu Selasa-Rabu-Kamis Rabu-Kamis-Jumat Kamis-Jumat-Sabtu W
Hari Libur Senin-Selasa-Rabu-Kamis Selasa-Rabu-Kamis-Jumat Rabu-Kamis-Jumat-Sabtu Kamis-Jumat-Sabtu-Minggu Senin-Jumat-Sabtu-Minggu Senin-Selasa-Sabtu-Minggu Senin-Selasa-Rabu-Minggu
Jumlah Pekerja 2 7 0 0 3 5 0 17
Berdasarkan ilustrasi di atas diketahui bahwa masalah (3,7) dapat diselesaikan dengan bantuan software LINGO 11.0. Meski begitu, masalah (3,7) juga dapat diselesaikan dengan penyelesaian lain, yaitu solusi dual. Solusi dual memiliki dua keunggulan dibandingkan dengan integer programming (IP).
5 Pertama, jika diselesaikan secara manual, algoritme yang dihasilkan dari solusi dual lebih cepat menyelesaikan masalah (3,7) karena diselesaikan tanpa iterasi (Alfares 2001). Kedua, jika ada kasus yang sama dengan masalah yang lebih besar, solusi dual mempunyai kelebihan efisiensi komputasi yang signifikan (Alfares dan Bailey 1997). Karena itu karya ilmiah ini selanjutnya akan membahas penyelesaian masalah (3,7) dengan solusi dual.
SOLUSI DUAL MASALAH (3,7)
Untuk menyelesaikan masalah (3,7) dengan solusi dual digunakan pemrograman linear dual dan hubungan primal-dual (complementary slackness). Pemrograman linear masalah (3,7) adalah sebagai berikut. Indeks i = hari, i = 1, 2, ..., 7 j = pola kerja, j = 1, 2, ..., 7. Parameter banyaknya pekerja yang dibutuhkan pada hari i = banyaknya pekerja yang libur pada hari i Variabel Keputusan = banyaknya pekerja yang bekerja pada pola kerja j Fungsi Objektif Fungsi objektif dari masalah (3,7) adalah meminimumkan banyaknya total ∑ (1) pekerja selama seminggu (W), yaitu min . Kendala Kendala-kendala masalah (3,7) adalah sebagai berikut: 1 Banyaknya pekerja yang bekerja pada hari i harus lebih besar atau sama dengan banyaknya pekerja yang dibutuhkan pada hari i . ∑
.
(2)
Karena masalah (3,7) bersifat siklis, yaitu dalam seminggu hanya ada tujuh pola kerja dan berulang setiap minggunya, maka untuk semua subscript dari berlaku kelipatan 7. Misalkan jika , maka dari (2) diperoleh . Karena bersifat siklis, maka pertaksamaan tersebut dapat dituliskan . Demikian pula untuk (menjadi ) dan (menjadi ). Hal itu juga berlaku pada variabel dualnya.
6 2 Banyaknya pekerja yang bekerja pada pola kerja j harus lebih besar atau sama dengan nol, (3) Dengan demikian secara umum pemrograman linear primal masalah (3,7) adalah sebagai berikut:
terhadap
∑
min ∑
. Masalah dual dari masalah (3,7) adalah sebagai berikut: max ̂
∑
terhadap
. Secara umum pemrograman linear dual masalah (3,7) adalah sebagai berikut: (4) max ̂ ∑ ∑ terhadap (5)
Penentuan Total Pekerja Minimum Ada dua kemungkinan solusi dual untuk menentukan banyaknya total pekerja, dan kemungkinan tersebut dipengaruhi oleh banyaknya pekerja yang dibutuhkan pada hari i Kedua kemungkinan tersebut selanjutnya akan dibahas sebagai berikut: 1 Karena fungsi objektif dual masalah (3,7) adalah maksimisasi, maka solusi masalah dual dapat diperoleh dengan membuat kendala dual masalah (3,7) dalam bentuk persamaan. ∑
.
(6)
Karena setiap kendala (5) hanya terdiri atas tiga variabel dual, maka dimungkinkan untuk memperoleh solusi dengan cara memberi nilai setiap variabel dual dengan 1/3 dari nilai ruas kanan. Dengan begitu diperoleh semua
7 variabel dual optimal, nilai
masalah (3,7) bernilai 1/3. Dengan demikian dalam kondisi ∑ , sehingga ∑ .
2 Mengingat pola penjadwalan masalah (3,7) hanya terdiri atas tiga hari kerja dalam tujuh hari, maka sedikitnya ada satu dari empat variabel berurutan harus } { Empat variabel termasuk dalam himpunan berurutan tersebut merupakan variabel yang merepresentasikan empat hari libur berturut-turut. Dengan demikian sedikitnya terdapat satu dari empat variabel berurutan yang tidak terdapat dalam kendala dual tapi termasuk ke dalam himpunan (lihat Tabel 3). Tabel 3 Empat variabel berurutan {
Variabel Berurutan
Kendala Dual
}
Karena setiap kendala dual masalah (3,7) hanya terdapat satu variabel dual anggota himpunan , maka dimungkinkan memberi nilai 1 untuk kedua variabel dual anggota himpunan pada kendala dual, yaitu .
(7)
Bila
didefinisikan maka akan dipilih dengan { } yang memaksimalkan yaitu Kemudian nilai lainnya sama dengan 0, dan banyaknya total variabel dual pekerja minimum adalah Berdasarkan dua kemungkinan tersebut, banyaknya pekerja total (W) dapat diperoleh dengan rumus sebagai berikut: {⌈ ∑
⌉
},
(8)
dengan ⌈ ⌉
min {
{
}
}.
Penetapan Pola Kerja Berdasarkan Biaya Penetapan pola kerja masalah (3,7) dipengaruhi oleh beberapa hal. Salah satu di antaranya adalah biaya pekerja. Bila diasumsikan bahwa biaya pekerja yang bekerja di hari biasa adalah A dan di akhir pekan (Sabtu-Minggu) adalah A(1+B) maka biaya setiap pola kerja bisa dilihat pada Tabel 4.
8 Tabel 4 Biaya pekerja Pola 1 2 3 4 5 6 7
Hari kerja 5, 6, 7 1, 6, 7 1, 2, 7 1, 2, 3 2, 3, 4 3, 4, 5 4, 5, 6
Biaya pekerja per minggu (3+2B)A (3+2B)A (3+B)A 3A 3A 3A (3+B) A
Dari Tabel 4 diketahui bahwa biaya pekerja termurah adalah pola kerja 4, 5, dan 6, kemudian disusul pola 3 dan 7, sedangkan pola kerja paling mahal adalah pola kerja 1 dan 2. Selain biaya pekerja, penetapan pola kerja juga dipengaruhi oleh banyaknya total pekerja (W) atau dalam hal ini dipengaruhi nilai ruas kanan dari (8). Selanjutnya akan dibahas sebagai berikut: 1 Bila {⌈ ∑ ⌉ } ⌈ ∑ ⌉, maka berlaku persamaan (6) yaitu semua variabel dual masalah (3,7) adalah bernilai positif ( Berdasarkan teorema complementary slackness, jika suatu variabel dual bernilai , maka kendala primal yang berpadanan akan berbentuk suatu persamaan pada keadaan optimum. ∑
.
(9)
Persamaan (9) dapat dinyatakan dalam bentuk lain. Misalkan adalah banyaknya pekerja yang libur pada hari i dan , maka persamaan (9) dapat dituliskan sebagai berikut: ∑ ∑ ∑ ∑
∑ .
(10)
(Bukti dapat dilihat di Lampiran 2) Dengan menggunakan persamaan (10), penetapan pola kerja dapat diketahui sebagai berikut: Bila
, maka ∑
9 Dengan cara yang sama untuk ⌉ adalah ⌈ ∑
, penetapan pola kerja untuk
(Bukti dapat dilihat di Lampiran 3) 2 Bila ⌉ } {⌈ ∑ maka berlaku persamaan (7) yaitu dan sama dengan 1. Berdasarkan teorema complementary nilai slackness, maka pada keadaan optimum kendala primal dan adalah dalam bentuk persamaan. Selain itu, karena biaya pekerja di akhir pekan lebih mahal, maka untuk meminimumkan banyaknya pekerja yang bekerja di hari itu, kendala primal untuk selalu dibuat dalam bentuk persamaan. Dengan demikian penetapan pola kerja untuk kasus Bila kemungkinan yang terpilih, yaitu dan kendala primal bentuk lain (10) untuk persamaan.
ada tujuh maka dalam bentuk (11.a) (11.b) (11.c) (11.d) (11.e) (11.f) (11.g)
Karena
, maka W didapat dengan menjumlahkan (11.a) dan (11.d)
Sementara pengurangan (11.f) dari penjumlahan (11.a) dan (11.d) adalah
Dari (11.b) diperoleh
. Dengan mengeksplorasi (11.a) sampai (11.h), penetapan pola kerja untuk adalah:
(11.h)
10 { {
untuk
}
}
Dengan cara yang sama untuk adalah seperti pada Tabel 5.
, penetapan pola kerja
(Bukti dapat dilihat di Lampiran 4)
Algoritme Solusi Dual Berdasarkan pembahasan di atas algoritme solusi dual untuk menyelesaikan masalah (3,7) adalah sebagai berikut: 1. Tentukan total pekerja minimum W dengan menggunakan rumus {⌈ ∑ ⌉ }. {⌈∑ ⌉ } ∑ 2. Jika , maka ∑ a) Jika bukan bilangan bulat, tambahkan nilai terkecil (hindari ∑ untuk membuat ∑ menjadi memilih dan ) dengan kelipatan 3. b) Hitung dengan menggunakan rumus , lalu hitung ∑ sebagaimana dalam Tabel 5. {⌈∑ ⌉ } 3. Jika , maka lakukan langkah 2b, lalu hitung sebagaimana dalam Tabel 5.
11 Tabel 5 Nilai
untuk semua kemungkinan nilai W
W ⌈∑
⌉ 0 {
0
} {
0
{ }
{
{
} {
}
} { }
} {
0
{
}
{ }
} { } { }
{ } {
0
{
{
0
} } {
}
{
0
} 11
12
CONTOH KASUS
Contoh 2 Misalkan
,
,
,
,
,
,
.
∑ ∑ {⌈ ∑ Karena ∑ terkecil ( adalah
⌉
{
}
}
bukan bilangan bulat, maka harus dibulatkan dengan menambah dengan 1 untuk membuat ∑ menjadi kelipatan 3. Jadi terbaru ,
Dari Tabel 5, nilai ,
,
,
,
untuk ∑ ,
,
,
adalah ,
,
,
,
Tabel 6 Hasil penjadwalan Contoh 2 Pekerja 1 2 3 4 5 6 7 8 9 10 11 12 13
Senin Selasa Rabu 0 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 1 0 0 0 9 7 6 Keterangan: 0 = Libur dan 1 = Masuk
Kamis 0 0 0 0 0 0 0 0 0 0 1 1 1 2
Jumat 1 0 0 0 0 0 0 0 0 0 0 1 1 3
Sabtu 1 1 1 1 0 0 0 0 0 0 0 0 1 5
Minggu 1 1 1 1 1 1 0 0 0 0 0 0 0 6
13
Contoh 3 Misalkan
,
,
,
,
,
,
.
∑ ∑ {⌈ ∑
⌉
Dengan menghitung
,
}
diperoleh ,
,
untuk
adalah
, Dari Tabel 5, nilai
{
}
,
,
,
,
,
,
,
,
Tabel 7 Hasil penjadwalan Contoh 3 Pekerja 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Senin 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 9
Selasa 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 7
Rabu 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 2
Kamis 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 6
Jumat 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 8
Sabtu 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 7
Minggu 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3
14
SIMPULAN Masalah penjadwalan tiga hari kerja dan empat hari libur secara berturutturut atau biasa disebut masalah (3,7) dapat diselesaikan dengan solusi dual. Algoritme optimasi yang dihasilkan dari masalah dual (3,7) dapat digunakan untuk meminimumkan banyaknya total pekerja dan menetapkan pola kerja untuk meminimumkan biaya total pekerja secara manual tanpa menggunakan software.
DAFTAR PUSTAKA Alfares HK and Bailey JE. 1997. Integrated project task and manpower scheduling. IIE Transactions. 29: 711-718. doi: 10.1080/07408179708966381. Alfares HK. 2000. Dual-based optimization of cycling three-day workweek scheduling. Asia-Pacific Journal of Operational Research. 17: 137-148. doi: 10.1002/mcda.420. Alfares HK. 2001. Efficient optimization of cyclic labor days-off scheduling. OR Spektrum. 23: 283-294. doi: 10.1007/PL00013353. Alfares HK. 2000. Dual-based optimization of cyclic four-day workweek scheduling. IMA Journal of Mathematics Applied in Business & Industry. 11: 269-283. doi: 10.1093/imaman/11.4.269. Baker KR. 1976. Workforce allocation in cyclical scheduling problem: a survey. Operational Research Quarterly. 27: 155-167. doi: 10.1057/jors.1976.30. Chvatal V. 1983. Linear Programming. New York (US): WH Freeman & Company. Nash SG and Sofer A. 1996. Linear and Nonlinear Programming. New York (US): McGraw-Hill. Winston WL. 2004. Operations Research Applications and Algorithms 4thed. New York (US): Duxbury.
15
Lampiran 1 Sintaks dan hasil komputasi program LINGO 11.0 untuk masalah (3,7) x2+x3+x4>=9; x3+x4+x5>=7; x4+x5+x6>=2; x5+x6+x7>=6; x6+x7+x1>=8; x7+x1+x2>=7; x1+x2+x3>=3; min=x1+x2+x3+x4+x5+x6+x7; @gin(x1);@gin(x2);@gin(x3);@gin(x4);@gin(x5);@gin(x6);@gin(x7); !xj=banyaknya pekerja yang bekerja pada pola kerja j !ri=banyaknya pekerja yang dibutuhkan pada hari i
Hasil yang diperoleh sebagai berikut: Global optimal solution found. Objective value: Objective bound: Infeasibilities: Extended solver steps: Total solver iterations: Variable X2 X3 X4 X5 X6 X7 X1 Row 1 2 3 4 5 6 7 8
17.00000 17.00000 0.000000 0 4 Value 2.000000 7.000000 0.000000 0.000000 3.000000 5.000000 0.000000 Slack or Surplus 0.000000 0.000000 1.000000 2.000000 0.000000 0.000000 6.000000 17.00000
Reduced Cost 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 DualPrice 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 -1.000000
16
Lampiran 2 Bentuk lain persamaan (9) Bila
, maka ∑
∑
∑ Bila
, maka ∑
∑
∑ Bila
, maka ∑
∑
17
∑ Bila
, maka ∑
∑
∑ Bila
, maka ∑
∑
∑ Bila
, maka ∑
∑
∑
Bila
, maka ∑
∑
∑
Lampiran 3 Penetapan pola kerja untuk Bila
, maka ∑
Bila
, maka ∑
∑
18
Bila
, maka ∑
Bila
, maka ∑
Bila
, maka ∑
Bila
, maka ∑
Lampiran 4 Penetapan pola kerja untuk Bila , maka dalam bentuk persamaan.
dan kendala primal untuk
adalah
(12.a) (12.b) (12.c) (12.d) (12.e) (12.f) (12.g)
19
Karena
, maka W didapat dengan menjumlahkan (12.b) dan (12.e)
Sementara pengurangan (12.g) dari penjumlahan (12.b) dan (12.e) adalah
Dari (12.d) diperoleh
(12.h) Dengan mengeksplorasi (12.a) sampai (12.h), penetapan pola kerja untuk adalah: { {
Bila persamaan.
} }
, maka
dan kendala primal untuk
dalam bentuk
(13.a) (13.b) (13.c) (13.d) (13.e) (13.f) (13.g) Karena
, maka W didapat dengan menjumlahkan (11.c) dan (11.f)
20
Sementara pengurangan (13.g) dari penjumlahan (13.c) dan (13.f) adalah
Dari (13.d) diperoleh
(13.h) Dengan mengeksplorasi (13.a) sampai (13.h), penetapan pola kerja untuk adalah: {
}
{ {
Bila persamaan.
}
, maka
}
dan kendala primal untuk
dalam bentuk
(14.a) (14.b) (14.c) (14.d) (14.e) (14.f) (14.g) Karena
, maka W didapat dengan menjumlahkan (14.d) dan (14.g)
Sementara pengurangan (14.f) dari penjumlahan (14.d) dan (11.g) adalah
Dari (14.b) diperoleh
21
(14.h) Dengan mengeksplorasi (14.a) sampai (14.h), penetapan pola kerja untuk adalah: { {
}
{
} }
Bila , maka bentuk persamaan.
dan kendala primal untuk
dalam (15.a) (15.b) (15.c) (15.d) (15.e) (15.f) (15.g)
Karena
, maka W didapat dengan menjumlahkan (15.a) dan (15.e)
Sementara pengurangan (15.g) dari penjumlahan (15.a) dan (15.e) adalah
Dari (15.d) diperoleh
(15.h) Dengan mengeksplorasi (15.a) sampai (15.h), penetapan pola kerja untuk adalah:
22
{ {
Bila persamaan.
}
}
dan kendala primal untuk
, maka
dalam bentuk (16.a) (16.b) (16.c) (16.d) (16.e) (16.f) (16.g)
Karena
, maka W didapat dengan menjumlahkan (16.b) dan (11.f)
Sementara pengurangan (16.g) dari penjumlahan (16.b) dan (16.f) adalah
Dari (16.d) diperoleh
(16.h) Dengan mengeksplorasi (16.a) sampai (16.h), penetapan pola kerja untuk adalah: { { {
}
} }
23
Bila persamaan.
, maka
dan kendala primal untuk
dalam bentuk (17.a) (17.b) (17.c) (17.d) (17.e) (17.f) (17.g)
Karena
, maka W didapat dengan menjumlahkan (17.c) dan (17.g)
Sementara pengurangan (17.f) dari penjumlahan (17.c) dan (14.g) adalah
Dari (17.b) diperoleh
(17.h) Dengan mengeksplorasi (17.a) sampai (17.h), penetapan pola kerja untuk adalah: { { {
} }
24
RIWAYAT HIDUP Penulis dilahirkan di kampung pesisir Bulu, Kabupaten Tuban, Jawa Timur, pada 10 Oktober 1990. Penulis merupakan anak bungsu dari lima bersaudara dari pasangan Bapak Abdul Rahman dan Ibu Nur Rahmah. Tahun 2008 penulis lulus dari SMA Negeri 1 Tuban kemudian diterima sebagai mahasiswa Institut Pertanian Bogor (IPB) melalui jalur Undangan Seleksi Masuk IPB (USMI). Penulis tercatat sebagai mahasiswa Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA). Semasa menjadi mahasiswa, penulis tidak banyak aktif di organisasi kemahasiswaan. Di tingkat pertama penulis sempat aktif di BEM KM IPB dan UKM BKIM IPB, sebelum kemudian keluar lantaran kemerdekaan berpikir penulis dibatasi. Selanjutnya penulis bebas beraktivitas penulis sendiri. Dalam aktivitas yang tak jelas itu penulis menelurkan sebuah buku berjudul “Nabi Drop Out Mahasiswa Cumlaude” dan sejumlah artikel yang tersebar di beberapa media massa.
