Penggunaan Integer Linear Programming dengan Metode Heuristik untuk Optimasi Penjadwalan Paruh Waktu

JURNAL TEKNIK POMITS Vol. 2, No. 1, (2013) ISSN: 2337-3539 (2301-9271 Print)

1

Penggunaan Integer Linear Programming dengan Metode Heuristik untuk Optimasi Penjadwalan Paruh Waktu Agri Kridanto, Ahmad Saikhu, dan Rully Soelaiman Jurusan Teknik Informatika, Fakultas Teknologi Informasi, Institut Teknologi Sepuluh Nopember (ITS) Jl. Arief Rahman Hakim, Surabaya 60111 Indonesia e-mail: [email protected]

Abstrak—Permasalahan penjadwalan pegawai paruh waktu sangatlah menarik untuk diselesaikan karena terdapat begitu banyak batasan, terutama batasan dari segi pegawai yang tersedia. Batasan tersebut antara lain perbedaan kemampuan yang dimiliki oleh setiap pegawai, ketersediaan setiap pegawai untuk bekerja pada waktu tertentu, dan target jam kerja yang dimiliki oleh setiap pegawai dalam suatu periode penjadwalan. Tujuan utama dari permasalahan penjadwalan pegawai paruh waktu adalah untuk memenuhi tuntutan jam kerja (permintaan pasar) dengan berbagai batasan yang ada. Selain itu, penjadwalan pegawai paruh waktu harus dapat menghasilkan penjadwalan yang efektif agar dapat meminimalkan kelebihan pegawai (overstaff) dan juga meminimalkan total deviasi antara jam kerja yang dijadwalkan dan target jam kerja setiap pegawai. Permasalahan penjadwalan pegawai paruh waktu sangat sulit untuk diselesaikan karena membutuhkan integer linear programming (ILP) yang sangat besar. Oleh karena itu, permasalahan ini akan dibagi menjadi 2 sub masalah yaitu: menentukan shift yang baik dan memberikan shift yang telah didapat kepada pegawai yang tersedia dengan menggunakan ILP untuk menyelesaikan kedua sub masalah tersebut. Kata Kunci— heuristik, integer linear programming, optimasi, penjadwalan. I. PENDAHULUAN

P

ERMASALAHAN penjadwalan adalah bagian yang sangat penting dalam sebuah industri, sebagai contoh pada perusahaan layanan jasa, seperti bank, restoran, call center, dan lain sebagainya. Pada perusahaan layanan jasa, biasanya mempekerjakan pegawai paruh waktu, karena perusahaan memiliki tuntutan jam kerja yang tinggi sementara para pegawai memiliki batasan berupa kemampuan serta jam kerja mereka. Para pegawai paruh waktu tersebut, memiliki kecenderungan untuk bekerja pada waktu tertentu, memiliki kemampuan untuk melakukan tugas tertentu dan memilki target jam kerja yang berbeda pula dalam suatu periode penjadwalan. Sementara itu, perusahaan penyedia layanan jasa, memiliki tuntutan kerja yang harus dipenuhi selama periode kerja. Tuntutan jam kerja umumnya fluktuatif terhadap waktu sesuai dengan permintaan konsumen. Terdapat tiga langkah dalam melakukan permasalahan penjadwalan seperti ini. Langkah pertama, untuk memprediksi tuntutan kerja untuk setiap jam kerja selama periode penjadwalan. Kedua, mewujudkan prediksi tuntutan kerja tersebut pada kebutuhan pegawai untuk setiap jam kerja supaya dapat memenuhi permintaan konsumen. Ketiga, untuk

mendapatkan ketersediaan setiap pegawai dengan menentukan hari kerja dan shift pada setiap pegawai. Tujuan utama dari proses penjadwalan ini untuk menghasilkan penjadwalan pegawai yang dapat memenuhi tuntutan kerja dengan meminimalkan total jam kerja para pegawai serta memenuhi target jam kerja pegawai dalam suatu periode penjadwalan. Permasalahan penjadwalan seperti ini sangat sulit untuk diselesaikan karena membutuhkan Integer Linear Programming (ILP) yang sangat besar sehingga penyelesaian permasalahan ini membutuhkan waktu komputasi yang sangat lama. Mehran Hojati dan Ashok S Patil [1] mengajukan sebuah solusi untuk menyelesaikan permasalahan penjadwalan ini yaitu dengan membagi permasalahan ini menjadi 2 sub masalah, yaitu: menentukan shift yang baik dan memberikan shift yang didapat pada pegawai yang tersedia dengan menggunakan ILP untuk menyelesaikan setiap sub masalah tersebut. ILP tahap pertama untuk menghasilkan shift yang baik. Shift yang baik adalah shift yang meminimalkan total jam kerja yang akan dijadwalkan serta memaksimalkan jumlah pegawai yang bisa melaksanakannya. ILP tahap pertama ini bertujuan untuk mereduksi kemungkinan shift yang ada. ILP tahap kedua digunakan untuk memberikan shift yang telah didapat sebelumnya kepada para pegawai yang tersedia . Permasalahan penjadwalan yang diangkat pada artikel ini adalah permasalahan penjadwalan pada restoran cepat saji. Terdapat beberapa batasan tambahan yaitu pekerja harus bekerja maksimal pada 5 hari kerja dalam seminggu dan pekerja minimal bekerja minimal 3 jam dan maksimal 8 jam pada hari kerja. Dalam studi ini akan mengimplementasikan metode yang diajukan oleh Mehran Hojati dan Ashok S Pathil [1] dengan menggunakan data ujicoba untuk dapat membandingkan hasil yang didapat serta beberapa data ujicoba acak untuk menguji kebenaran model yang telah dibangun. II. METODOLOGI PENELITIAN A. Notasi  h Indeks jam kerja pada setiap hari kerja ( h  1,...,18 ).  d Indeks hari kerja dalam 1 minggu. ( d  1,...,7 ).  e

JURNAL TEKNIK POMITS Vol. 2, No. 1, (2013) ISSN: 2337-3539 (2301-9271 Print) Indeks pegawai yang tersedia. ( e  1,...,40 ).  s Indeks dari shift yang memungkinkan setiap harinya ( s  1,...,81 ), dimana setiap indeks shift yang memiliki durasi minimal 3 jam dan maksimal 8 jam, contoh: s=1 (1,2,3), s=2 (1,2,3,4)  t Indeks dari tugas yang ada serta kemampuan yang dimiliki oleh pegawai, t=1(Grill/Gr), 2(Drive Thru/DT), 3(French Fries/FF), 4(Bin Call/BC), 5(Counter/Co) .  y std Jumlah pegawai yang dijadwalkan pada shift s, untuk tugas t pada hari d.  a hstd Bernilai 1 jika jam h terdapat dalam shift s. Jika tidak maka bernilai 0.  rhtd Jumlah pegawai yang dibutuhkan pada jam h untuk tugas t pada hari d .  hrs s Durasi dalam jam pada shift s.  hdreq Jumlah jam kerja yang dibutuhkan pada hari d.  htd

req

Jumlah jam kerja yang dibutuhkan untuk tugas t pada hari d.  Trgte Target jam kerja pegawai e dalam 1 minggu.  Trgtw Target jumlah shift yang dijadwalkan dalam 1 minggu.  Trgtd Target jumlah shift yang dijadwalkan dalam hari d.  Trgttd Target jumlah shift untuk tugas t yang dijadwalkan pada hari d.  E std Jumlah pegawai yang tersedia dan memenuhi syarat untuk shift s, tugas t, hari d.  utd Jumlah shift yang dibawah target Trgttd .  otd Jumlah shift yang diatas target Trgttd . r  S ed Jumlah dari shift yang tersisa pada hari d, dimana pegawai e tersedia dan memenuhi syarat untuk shift-shift tersebut.  S er Jumlah dari shift-shift yang tersisa dalam 1 minggu, dimana pegawai e tersedia dan memenuhi syarat untuk shift-shift r tersebut. S er  d S ed r  E ed

2

Bernilai 1 jika pegawai e yang tersedia dan memenuhi syarat setidaknya untuk 1 shift pada hari d. Jika tidak maka bernilai 0  E dr Jumlah dari pegawai yang tersisa dimana pegawai tersebut tersedia dan memenuhi syarat setidaknya untuk 1 shift pada r hari d. E dr  e pegawai tersisa Eed  Er Jumlah total dari hari kerja semua pegawai yang tersisa dengan maksimal 5 hari kerja untuk tiap pegawai. r E r  e pegawai tersisa min(d Eed ,5) r  E std Jumlah dari pegawai yang tersisa dimana para pegawai tersebut tersedia dan memenuhi syarat untuk shift s, tugas t, pada hari d  E ldr Jumlah minimum dari pegawai yang tersisa dimana para pegawai tersebut tersedia dan memenuhi syarat untuk shift yang berdurasi L jam pada hari d. r Eldr  min(E std : hrs s  L)

 S dr Jumlah dari shift yang tersisa pada hari d   ur Konstanta heuristik yang menyatakan total jam kerja yang masih kurang dari target jam kerja mingguan selama pencarian solusi berlangsung.   or Konstanta heuristik yang menyatakan total jam kerja yang melebihi selama pencarian solusi berlangsung.   ur Total jam kerja yang masih kurang dari target jam kerja mingguan pegawai ( Trgte ).   ro Total jam kerja yang melebihi target jam kerja mingguan pegawai ( Trgte ).  du

r

Sisa hari kerja pegawai terhadap batas maksimal hari kerja  x Ld Bernilai 1 jika shift dengan durasi L jam tersedia dan cocok untuk diberikan kepada pegawai e . Bernilai 0 jika shift dengan durasi L jam tersebut tidak tersedia dan cocok untuk diberikan kepada pegawai e. B. Proses Menentukan Shift yang Baik Menggunakan ILP Proses ini bertujuan untuk memilih shift-shift yang baik yang dapat meminimalkan total jam kerja yang akan dijadwalkan dan memaksimalkan jumlah pegawai yang dapat melaksanakannya. Proses ini digunakan untuk mereduksi jumlah shift yang nantinya akan diberikan kepada para pegawai. Dalam proses ini tetap melibatkan para pegawai agar shift-shift yang terpilih bisa diberikan kepada para pegawai yang tersedia. Oleh karena itu, dalam menentukan shift yang baik akan dihitung berapa jumlah pegawai yang dapat

JURNAL TEKNIK POMITS Vol. 2, No. 1, (2013) ISSN: 2337-3539 (2301-9271 Print) melaksanakan shift tersebut dan shift yang akan dipilih adalah shift yang memiliki jumlah maksimal pegawai yang bisa melaksanakan shift tersebut. Terdapat 3 langkah dalam proses menentukan shift yang baik, yaitu: 1. Tentukan target shift untuk setiap tugas t pada hari d. Asumsikan, pegawai bekerja rata-rata dalam 4 hari kerja seminggu. Sehingga, untuk 40 pekerja akan terdapat 160 target shift untuk periode penjadwalan 1 minggu. (1) Trgt  4 * e



w

Target shift untuk setiap hari d didapatkan dengan menghitung jumlah jam kerja yang dibutuhkan pada hari d dibagi total jam kerja dalam 1 minggu dikali dengan target shift per minggu.

hdreq * Trgtw , d  hdreq

Trgtd 

(2)

d

Target shift untuk tugas t pada hari d didapatkan dengan menghitung jumlah jam kerja yang dibutuhkan untuk tugas t pada hari d dibagi target shift pada hari tersebut. (3) h req Trgttd  tdreq * Trgtd , d , t hd 2. Tentukan jumlah pegawai yang tersedia dan memenuhi syarat untuk melaksanakan setiap shift s untuk tugas t pada hari d. 3. Formulasikan ILP1 untuk setiap tugas t pada hari d. Meminimalkan : Z   hrss . ystd  0td    Estd .hrss . ystd s

(4)

s

Batasan :

a

hstd

. y std  rhtd , h

(5)

s

y

std

  0td  utd  Trgttd ,

(6)

s

ystd  nonNegatif _ Integer , s

0td , utd  0

(7) (8)

Koefisien yang digunakan dalam fungsi objektif pada model ILP1 ,  =1 dan  =0.1. Fungsi objektif ILP1 pada (4), dapat dibagi menjadi 3 bagian, yaitu: i.  hrs s . y std , (9) s

untuk meminimalkan total jam kerja dari pegawai yang akan dijadwalkan. ii.  0td , (10) untuk memperbolehkan adanya shift yang melebihi target shift untuk tugas t pada hari d ( Trgttd ) tetapi tetap menjaga untuk meminimalkan adanya shift yang melebihi Trgttd . iii.    E std .hrs s . y std , s

(11)

3

untuk memaksimalkan jumlah pegawai yang tersedia dan memenuhi syarat untuk shift yang terpilih. Batasan ILP1 dalam (5) digunakan untuk memastikan bahwa setiap shift yang terpilih nanti akan memiliki jumlah pegawai minimal sebanyak pegawai yang dibutuhkan pada jam kerja tersebut. Batasan ILP1 dalam (6) digunakan agar jumlah shift yang terpilih ditambah shift yang melebihi target, dikurangi shift yang dibawah target sama dengan target shift untuk tugas t pada hari d Trgttd  . Batasan ILP1 dalam (7) digunakan untuk memastikan bahwa nilai dari variabel keputusan y std adalah bilangan non negatif integer. Batasan ILP1 dalam (8) digunakan untuk memastikan shift yang melebihi target dan shift yang kurang dari target adalah bilangan non negatif. Pemodelan ILP1 yang telah dijelaskan diatas diharapkan mencapai hasil yang optimal, sehingga kita bisa mendapat nilai dari setiap variabel keputusan y std . Shift yang akan digunakan adalah shift yang memiliki nilai y std yang positif. Jika nilai y std  2 maka perlu dilakukan replikasi sebanyak nilai y std sehingga akan terdapat shift sebanyak nilai y std untuk shift s, tugas t, pada hari d yang bisa dijadwalkan kepada para pegawai dalam tahap selanjutnya. Hasil akhir dari seluruh tahapan ini adalah daftar shift yang baik yang akan digunakan pada tahapan selanjutnya. C. Proses Pemberian Shift kepada Pegawai Menggunakan ILP dengan Metode Heuristik Pada proses pemberian shift kepada pegawai akan digunakan ILP2 dengan metode heuristik untuk memberikan shift yang telah didapat kepada pegawai yang tersedia. Berikut ini adalah langkah-langkah untuk proses pemberian shift kepada para pegawai. Sebagai inisialisai,  u  0 dan r

 or  0 . 1. Cari pegawai dengan ketersediaan terendah pada daftar shift (selanjutnya disebut ei). 2. Untuk setiap ei i. Untuk setiap shift yang tersisa dalam daftar shift, periksa apakah ei tersedia untuk shift tersebut, jika ya, E std = jumlah pegawai yang bisa melaksanakan shift tersebut. Jika tidak, E std  0 . ii. Untuk setiap shift dengan durasi L jam pada hari d, r

dapatkan nilai minimal dari nilai E std yang telah





didapat sebelumnya. Eld  min Estd : hrss  L . r

r

iii. Untuk setiap hari penjadwalan, hitung jumlah pegawai yang tersedia dan memenuhi syarat r

setidaknya untuk 1 shift pada hari tersebut ( E d ). iv. Hitung jumlah total dari ketersediaan pegawai dalam periode panjadwalan 1 minggu, dengan penjadwalan maksimal 5 hari kerja dalam 1 minggu ( E r ).

JURNAL TEKNIK POMITS Vol. 2, No. 1, (2013) ISSN: 2337-3539 (2301-9271 Print)

4

v. Hitung jumlah shift pada setiap hari d ( S d ).

oe

vi. Selesaikan ILP2 untuk pegawai ei.

meminimalkan total deviasi deviasi antara

r

ue dan oe dari target jam kerja mingguan pegawai ( Trgte ).

Meminimalkan: Z 

ii.

(1   ur )ue  (1   or )oe 

 1 d eu

E  d S   r

r d

cenderung semakin mengecil sehingga dapat

 1d eu E r  d S dr  

,

(21)

Nilai E r  d S dr   akan semakin mengecil ketika



E r mendekati nilai d S dr   . Sehingga u koefisien dari d e akan semakin meningkat. Karena nilai

  x Ld    2   r E  ( 1   ) d L Ld  

fungsi tujuan meminimalkan nilai variabel keputusan

  x Ld    3 d  r L r  Ed  S d     

d eu , maka diharapkan nilai d eu akan semakin mengecil sehingga solusi diharapkan akan semakin memenuhi target kerja mingguan pegawai ( Trgte ). (12)

Batasan:

  x , (22) iii.   2    r Ld  d L E  (1 )  Ld   r Nilai E Ld  (1 ) akan semakin mengecil ketika

u   xLd  d e  5, d , L

(13)

u o   xLd L  e  e  Trgte

(14)

dari x Ld akan menjadi bilangan negatif yang besar.

 x Ld  1, d

(15)

Hal ini diharapkan dapat menjadikan pemilihan variabel x Ld menjadi lebih baik.

x Ld 

(16)

d L

r nilai E Ld mendekati nilai (1 ) . Sehingga koefisien

d L

L

r E Ld ,d , L

 x iv.  3 d  r L Ld r 

 ,   Ed  S d   

(23)

Nilai Edr  S dr   akan semakin mengecil

ketika

x Ld  biner ,d , L

(17)

nilai E mendekati nilai

d eu , ue , oe

(18)

dari x Ld akan menjadi bilangan negatif yang besar.

vii. Berikan shift yang terpilih ( x Ld  1 ) kepada pegawai

Hal ini diharapkan dapat menjadikan pemilihan variabel x Ld menjadi lebih baik.

0

ei. Hapus pegawai ei dari daftar pegawai dan hapus shift yang tepilih dari daftar shift. viii. Perbarui konstanta heuristik, (19)  ur   ur  ue dan  or   or  oe . Gunakan langkah 1, 2 hingga semua pegawai telah dijadwalakan dan tidak ada pegawai yang tersisa dalam daftar pegawai. Koefisien yang digunakan dalam fungsi objektif pada model ILP2 ,  0.1 dan  1   2   3 =3. Fungsi objektif ILP2 dalam persamaan 9 dapat dibagi menjadi 4 bagian, yaitu : (20) i. (1   ur )ue  (1   er )oe , koefisien dari

ue

dan

oe

akan meningkat seiring

dengan meningkatnya  u dan  o . Persamaan (20) r

r

diharapkan dapat menyeimbangkan antara 



r o

r u

dan

selama pencarian solusi berlangsung. Karena

fungsi tujuannya meminimalkan, maka nilai

ue

dan

r d

S dr

  . Sehingga koefisien

Batasan ILP2 dalam (13) mengharuskan solusi yang dihasilkan harus memenuhi target maksimal 5 hari kerja. Batasan ILP2 dalam (14) mengharuskan bahwa solusi yang dihasilkan memenuhi target jam kerja pegawai. Batasan ILP2 dalam (15) mengharuskan hanya ada satu shift yang terpilih setiap harinya. Batasan ILP2 pada (16) mengharuskan nilai dari variabel keputusan x Ld sama dengan 0, jika pegawai ei tidak tersedia dan memenuhi syarat untuk setiap shift dengan durasi L jam pada hari d. Karena batas atas dari batasan ini r adalah variabel E Ld , akan memiliki nilai 0 jika pegawai ei tidak tersedia dan memenuhi syarat untuk setiap shift dengan durasi L jam pada hari d. Batasan ILP2 pada (17) mengharuskan nilai variabel keputusan x Ld adalah variabel biner. Batasan ILP2 pada (15) mengharuskan nilai dari variabel keputusan d eu , ue , oe adalah bilangan non negatif.

JURNAL TEKNIK POMITS Vol. 2, No. 1, (2013) ISSN: 2337-3539 (2301-9271 Print) Tabel 1 Perbandingan Hasil Uji Coba untuk Data Uji Coba Utama

III. HASIL UJI COBA Dalam uji coba ini model dibangun pada lingkungan pemodelan MATLAB dengan TOMLAB Optimization untuk menyelesaikan ILP. Data uji coba berasal dari paper [1] . Data uji coba terdiri dari data uji coba utama dan data uji coba acak. Dalam bagian ini akan diberikan perbandingan antara hasil penjadwalan dari model yang telah dibangun dan hasil dari penulis. Sebagai informasi tambahan, Mehran Hojati dan Ashok S Pathil (2008) menggunakan Excel VBA dengan Standard Solver untuk menyelesaikan ILP. Dalam data uji coba utama terdapat 40 pegawai yang tersedia dengan jam kerja tertentu, 5 jenis tugas dan kemampuan pegawai serta tuntutan jam kerja yang ada. Proses menetukan shift yang baik membutuhkan 35 ILP1 (7 hari kerja, 5 tugas). Proses memberikan shift kepada menggunakan 40 ILP2 yang digunakan dalam 40 kali iterasi karena terdapat 40 pegawai yang tersedia. Perbandingan untuk data uji coba utama dapat dilihat pada Tabel 1. Uji coba juga dilakukan untuk 10 data uji coba acak [1]. Dari data tersebut didapatkan hasil yaitu: rata-rata kelebihan jam kerja hanya 0,3 jam untuk setiap data uji coba, rata-rata total deviasi antara target jam kerja dan jam kerja yang dijadwalkan adalah 6,4 jam untuk setiap data uji coba atau hanya 0,16 jam untuk setiap pegawai, dan rata-rata waktu komputasi yang dibutuhkan untuk menyelesaikan permasalahan penjadwalan yaitu 3,5 detik untuk setiap data uji coba. IV. KESIMPULAN/RINGKASAN Berdasarkan hasil uji coba, keseluruhan model yang telah dibangun dapat menyelesaikan permasalahan penjadwalan paruh waktu dengan waktu komputasi yang cukup singkat. Model ILP1 dapat menghasilkan shift yang baik, dimana shift tersebut dapat memaksimalkan jumlah pegawai yang melaksanakannya sehingga shift tersebut dapat diberikan kepada pegawai yang tersedia. Model ILP2 dengan menggunakan metode heuristik dapat memberikan shift yang telah didapat kepada pegawai yang tersedia dengan meminimalkan total deviasi antara jam kerja yang dijadwalkan dan target jam kerja mingguan pegawai. Keseleruhan proses penjadwalan pegawai paruh waktu dapat memberikan hasil yang cukup baik, dengan memenuhi tuntutan jam kerja yang ada, dan mampu meminimalkan adanya kelebihan jam kerja (overstaff). UCAPAN TERIMA KASIH Penulis A.K. mengucapkan terima kasih kepada dosen pembimbing yang telah banyak memberikan bantuan dan bimbingan kepada penulis dalam melakukan penelitian ini.

5

Parameter perbandingan Kelebihan jam kerja Total deviasi Waktu Komputasi

Mehran Hojati dan Ashok S Pathil. 4 jam 20 jam 18 menit

Hasil Uji Coba 4 jam 12 jam 5,44 detik

DAFTAR PUSTAKA [1]

Hojati, M., Patil A. S. “An integer linear programming-based heuristic for scheduling heterogeneous part-time service employees” European Journal of Operational Research 209, 37-50, 2011