PRESENTASI TUGAS AKHIR KI091391

PRESENTASI TUGAS AKHIR – KI091391 PENGGUNAAN INTEGER LINEAR PROGRAMMING DENGAN METODE HEURISTIK UNTUK OPTIMASI PENJADWALAN PEGAWAI PARUH WAKTU

(Kata kunci: penjadwalan, optimasi, integer linear programming, heuristik)

Penyusun Tugas Akhir : Agri Kridanto (NRP : 5109.100.140)

Dosen Pembimbing : Ahmad Saikhu, S.Si., M.T. Rully Soelaiman, S.Kom., M.Kom. 25 Juli 2013

Tugas Akhir – KI091391

1

Agenda

Kesimpulan

Pendahuluan

Uji Coba

Metode Penyelesaian

LATAR BELAKANG

 Permasalahan penjadwalan pegawai paruh waktu adalah

permasalahan penjadwalan pada sebuah industri dimana para pegawai nya merupakan pegawai paruh waktu yang memiliki:   

Kecenderungan untuk bekerja pada waktu tertentu Kemampuan untuk melaksanakan tugas tertentu Target Jam kerja yang berbeda dalam periode penjadwalan

 Penjadwalan yang efektif dan efisien sangat penting agar perusahaan dapat memenuhi permintaan pasar yang tersedia sehingga bisa memberikan keuntungan pada perusahaan.  Permasalahan penjadwalan seperti ini sangat sulit diselesaikan karena membutuhkan ILP yang sangat besar sehingga membutuhkan waktu komputasi yang lama.

25 Juli 2013


3

LATAR BELAKANG

 Sebagai Contoh, untuk data uji coba utama [1] tidak dapat diselesaikan menggunakan ILP konvensional dengan waktu komputasi hingga 9 jam dengan menggunakan CPLEX, karena terdapat begitu banyak variabel dan batasan-batasan yang ada.

25 Juli 2013


4

RUMUSAN MASALAH

1. Bagaimana konsep penerapan ILP untuk menentukan shift yang baik? 2. Bagaimana konsep penerapan ILP dengan metode heuristik untuk pembagian shift yang didapat pada pegawai? 3. Bagaimana melakukan implementasi konsep tersebut ? 4. Bagaimana melakukan uji coba metode di atas untuk menyelesaikan penjadwalan pegawai paruh waktu ?

25 Juli 2013


5

BATASAN MASALAH

1. Data uji coba terdiri dari data uji coba utama dan data uji coba acak [1] untuk membandingkan hasil yang didapat. 2. Penjadwalan akan dilakukan dalam periode penjadwalan 1 minggu dengan total hari kerja maksimal 5 hari 3. Penjadwalan dilakukan dengan sistem shift dengan durasi shift minimal 3 jam dan durasi maksimal 8 jam.

25 Juli 2013


6

TUJUAN

1. Memenuhi tuntutan jam kerja pada ketersediaan pegawai dengan total jam kerja yang minimum. 2. Memenuhi target jam kerja untuk setiap pegawai. 3. Mengimplemetasikan ILP dengan metode heuristik untuk optimasi pada penjadwalan pegawai paruh waktu.

25 Juli 2013


7

Agenda

Kesimpulan

Pendahuluan

Uji Coba

Metode Penyelesaian

DESAIN APLIKASI

Data Masukan

Proses Penentuan Shift yang Baik menggunakan ILP1

Proses Pemberian Shift kepada pegawai yang tersedia menggunakan ILP2 dengan metode heuristik

Proses Penghitungan kelebihan jam kerja dari penjadwalan yang dihasilkan

Proses Penghitungan total deviasi jam kerja pegawai

Hasil Penjadwalan 25 Juli 2013


9

PROSES PENENTUAN SHIFT YANG BAIK DENGAN MENGGUNAKAN ILP1

Data Ketersediaan Pegawai, Data Kemampuan Pegawai, Data Tuntutan Jam Kerja

Penentuan Target Shift untuk setiap tugas t pada hari d

Perhitungan jumlah pegawai yang tersedia untuk setiap shift tersebut

Penentuan Shift yang Baik dengan menggunakan model ILP 1 untuk setiap shift tersebut

Pengolahan hasil ILP1

Daftar Shift yang Baik

25 Juli 2013


10

ILP2 dengan METODE HEURISTIK

• • •

Dengan menempatkan konstanta heuristik dalam fungsi objektif ILP2 Konstanta heuristik sebagai nilai penalti akan semakin meningkat selama proses pencarian solusi berlangsung Sebagai inisialisasi , ur  0, or  0

25 Juli 2013


11

PROSES PEMBERIAN SHIFT KEPADA PEGAWAI MENGGUNAKAN ILP2 DENGAN METODE HEURISTIK Daftar Shift yang baik

Pencarian shift yang cocok untuk ei dengan ILP2

Update Data Penjadwalan

Pencarian Pegawai dengan Ketersediaan Terendah pada daftar Shift (ei)

Data Pegawai

Ya

Tidak Masih ada pegawai yang tersisa ?

Hapus Pegawai ei Hapus Shift yang terpilih

Update Konstanta Heuristik

 ur   ur  ue  or   or  oe

Data Penjadwalan 25 Juli 2013


12

Agenda

Kesimpulan

Pendahuluan

Uji Coba

Metode Penyelesaian

SKENARIO UJI COBA

1. Uji kebenaran: Melakukan penjadwalan untuk data uji coba utama dan data uji coba acak [1] dan membandingkan hasil yang didapat dengan Mehran et al [1]. 2. Uji Performa : Membandingkan waktu komputasi yang dibutuhkan untuk menyelesaikan hasil penjadwalan untuk data uji coba utama dan data uji coba acak [1].

25 Juli 2013


14

TINGKAT KEBERHASILAN

Hasil Penjadwalan harus bisa memenuhi tuntutan jam kerja (overstaff≥0)  Semakin kecil nilai overstaff, semakin efektif penjadwalan tersebut Semakin kecil nilai total deviasi yang dihasilkan, semakin baik penjadwalan yang dilakukan

25 Juli 2013


15

Uji Kebenaran

Perbandingan Hasil Penjadwalan* Nama dataset

Kelebihan Jam Kerja *

Total Deviasi *

data uji coba utama

0

-8

dataset1

0

-2

dataset2

0

-14

dataset3

0

-14

dataset4

0

-16

dataset5

0

-22

dataset6

0

-20

dataset7

0

-6

dataset8

0

-32

dataset9

0

-4

dataset10

0

-16

25 Juli 2013

• Hasil Uji Coba menunjukkan penjadwalan yang dilakukan dapat memenuhi tuntuntutan jam kerja yang ada (kelebihan jam kerja sama dengan yang dihasilkan Mehran et.al) •Hasil Uji Coba menunjukkan penjadwalan yang dilakukan dapat menghasilkan total deviasi yang lebih kecil dari Mehran et al

* Perbandingan dengan Mehran et al.


16

Uji Performa

Perbandingan Waktu Komputasi Perbandingan Waktu Komputasi 1200

Berdasarkan Uji Performa, hasil uji coba memiliki waktu komputasi yang jauh lebih singkat

1000

detik

800 600 400

Hasil Uji Coba Mehran et al

200 0

Nama Dataset

25 Juli 2013


17

Agenda

Kesimpulan

Pendahuluan

Uji Coba

Metode Penyelesaian

KESIMPULAN

1. Model ILP1 dan model ILP2 dengan metode heuristik dapat

menyelesaikan permasalahan penjadwalan pegawai paruh waktu. 2. 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) serta meminimalkan total deviasi jam kerja pegawai 3. Model ILP1 dan model ILP2 dapat dibangun pada MATLAB dengan menggunakan solver TOMLAB, dan memiliki waktu komputasi yang cukup singkat.

25 Juli 2013


19

SARAN

1. Permasalahan penjadwalan pegawai paruh waktu disini

menggunakan batasan-batasan yang telah ditetapkan yaitu: 5 hari kerja dengan panjang shift shift minimal 3 jam dan panjang shift maksimal 8 jam. Tentunya akan terdapat berbagai batasan lainnya yang harus ditambahkan dalam proses penjadwalan pegawai paruh waktu. 2. Perlu dipertimbangkan untuk dilakukan pengembangan pada aplikasi ini sehingga dapat lebih aplikatif dan interaktif untuk pengguna.

25 Juli 2013


20

SELESAI

TERIMA KASIH

25 Juli 2013


21

PENENTUAN TARGET SHIFT

Penentuan Target Shift

Trgtw  4 *  e hdreq Trgtd  * Trgtw req  hd

Target jumlah shift dalam 1 minggu

d

Target jumlah shift untuk setiap hari

d

htdreq Trgttd  req * Trgtd hd

25 Juli 2013

d, t

Target jumlah shift untuk setiap tugas t pada hari d


23

Target Shift per Hari Trgtw  4 *  e hdreq Trgtd  * Trgtw req  hd

Target jumlah shift dalam 1 minggu

d

Target jumlah shift untuk setiap hari

d

Jam yang dibutuhkan Jumlah Proporsi Shift

Minggu Senin Selasa Rabu Kamis Jumat Sabtu Total 110 116 117 120 123 141 151 878 20 21 21 22 26 26 25 160

110 *160  20 878

Target Shift untuk Tugas t pada hari d htdreq Trgttd  req * Trgtd hd

Target jumlah shift untuk setiap tugas t pada hari d

d, t Minggu

Jam yang dibutuhkan

110

Jumlah Proporsi Shift

20

Jam yang dibutuhkan untuk setiap tugas Gr

37

DT

27

FF

11

BC

13

CO

22

Jumlah Shift untuk setiap tugas Gr

7

DT

5

FF

2

BC

2

CO

4

37 * 20  7 110

MODEL ILP 1

ILP 1

Notasi

hrss

Durasi dalam jam untuk shift s

a hstd

Bernilai 1 jika jam h berada dalam shift s

rhtd

Jumlah pegawai yang dibutuhkan pada jam h untuk tugas t pada hari d

Trgttd

Target jumlah shift untuk tugas t yang dijadwalkan pada hari d

E std

Jumlah pegawai yang tersedia dan memenuhi Untuk shift s tugas t pada hari d

25 Juli 2013


27

ILP 1

Variabel Keputusan

y std

Jumlah pegawai yang dijadwalkan untuk shift s , tugas t , pada hari d

utd

Jumlah shift yang kurang dari target shift, untuk tugas t pada hari d

otd

Jumlah shift yang melebihi target shift, untuk tugas t pada hari d

25 Juli 2013


28

ILP 1

Fungsi Objektif ILP1 Meminimalkan :

Z   hrss . ystd  0td    Estd .hrss . ystd s

  0.1,   1

s

hrss


y std

Jumlah pegawai yang dijadwalkan untuk shift s ,tugas t , pada hari d

Untuk meminimalkan total jam kerja dari pegawai yang akan dijadwalkan 25 Juli 2013


29

ILP 1



  0.1,   1

s

otd

Jumlah shift yang melebihi target shift, untuk tugas t pada hari d

Untuk meminimalkan shift yang melebihi target

25 Juli 2013


30

ILP 1



  0.1,   1

s

untuk memaksimalkan jumlah pegawai yang tersedia dan memenuhi syarat untuk shift yang terpilih.

hrss


y std


E std 25 Juli 2013

Jumlah pegawai yang tersedia dan memenuhi syarat Untuk shift s tugas t pada hari d Tugas Akhir – KI091391

31

ILP 1

Batasan 1 ILP1

a

hstd

. y std  rhtd , h,

s

a hstd

y std rhtd

Bernilai 1 jika jam h berada dalam shift s Jumlah pegawai yang dijadwalkan untuk shift s ,tugas t , pada hari d Jumlah pegawai yang dibutuhkan pada jam h untuk tugas t pada hari d

untuk memastikan bahwa setiap shift yang terpilih nanti akan memiliki jumlah pegawai minimal sebanyak pegawai yang dibutuhkan pada jam kerja tersebut 25 Juli 2013


32

ILP 1

Batasan 2 ILP1 u 0 y      std td td  Trgttd , s

y std

otd utd Trgttd

Jumlah pegawai yang dijadwalkan untuk shift s ,tugas t , pada hari d Jumlah shift yang melebihi target shift, untuk tugas t pada hari d Jumlah shift yang dibawah target shift, untuk tugas t pada hari d Target jumlah shift untuk setiap tugas t pada hari d

Jumlah dari shift yang terpilih sesuai dengan target shift yang telah ditentukan 25 Juli 2013


33

ILP 1

Batasan 3,4 ILP1 ystd  nonNegatif Integer s,

0td , utd  0 y std

otd utd

25 Juli 2013


Jumlah shift yang melebihi target shift, untuk tugas t pada hari d Jumlah shift yang dibawah target shift, untuk tugas t pada hari d


34

MODEL ILP 2

ILP 2

Notasi ( bagian 1)  ur  or E edr E dr

Konstanta heuristik yang menyatakan total jam kerja yang kurang dari target selama pencarian solusi berlangsung Konstanta heuristik yang menyatakan total jam kerja yang melebihi target selama pencarian solusi berlangsung Bernilai 1 jika pegawai e yang tersedia dan memenuhi syarat setidaknya untuk 1 shift pada hari d. Jika tidak maka bernilai 0 Jumlah dari pegawai yang tersisa dimana pegawai tersebut tersedia dan memenuhi syarat setidaknya untuk 1 shift pada hari d

Edr  epegawai tersisa Eedr

Er

Jumlah total hari kerja untuk semua pegawai yang tersisa dengan maksimal 5 hari kerja untuk setiap pegawai

E r  epegawai tersisa min( d Eedr ,5) 25 Juli 2013


36

ILP 2

Notasi ( bagian 2) r E std

E

r ld

Jumlah dari pegawai yang tersisa dimana para pegawai tersebut tersedia dan memenuhi syarat untuk shift s, tugas t, pada hari d 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( Estd : hrss  L)

S dr

25 Juli 2013

Jumlah dari shift yang tersisa pada hari d


37

ILP 2

Variabel Keputusan x Ld

Variabel ini bernilai 1 jika shift dengan durasi L jam pada hari d terpilih untuk diberikan kepada pegawai ei

d eu

Variabel untuk jumlah hari kerja yang masih dibawah total hari kerja maksimal ( 5 hari)

ue

Jumlah jam kerja yang masih kurang dari target jam kerja mingguan pegawai ei

oe

Jumlah jam kerja yang diatas target jam kerja mingguan pegawai ei

25 Juli 2013


38

ILP 2


meminimalkan total deviasi deviasi antara shift yang melebihi target dan kurang dari target jam kerja mingguan pegawai

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

 1 d eu

E  d S   r

r d



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

  0.1, 1   2   3  3 25 Juli 2013

 ur

Konstanta heuristik yang menyatakan total jam kerja yang kurang dari target selama pencarian solusi berlangsung

 or

Konstanta heuristik yang menyatakan total jam kerja yang melebihi target selama pencarian solusi berlangsung

ue oe

Jumlah jam kerja yang masih kurang dari target jam kerja mingguan pegawai Jumlah jam kerja yang diatas target jam kerja mingguan pegawai ei


39

ILP 2


meminimalkan nilai days under taget , agar memenuhi target jam kerja pegawai

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

1d eu

E r  d S dr  



  xLd    2    r ( 1 ) E    Ld  d L    xLd    3 d  r L r  E  S   d  d 

  0.1, 1   2   3  3

25 Juli 2013

d eu

Variabel untuk jumlah hari kerja yang masih dibawah total hari kerja maksimal ( 5 hari)

Er

Jumlah total hari kerja untuk semua pegawai yang tersisa dengan Maksimal 5 hari kerja untuk setiap pegawai

S dr Tugas Akhir – KI091391

Jumlah dari shift yang tersisa pada hari d 40

ILP 2


E Z 

r ld

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

 1 d eu

E r  d S dr  



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

  0.1, 1   2   3  3 25 Juli 2013

Jumlah minimum dari pegawai yang tersisa dimana para pegawai tersebut tersedia dan memenuhi syarat untuk shift yang berdurasi L jam pada hari d.

E dr

Jumlah dari pegawai yang tersisa dimana pegawai tersebut tersedia dan memenuhi syarat setidaknya untuk 1 shift pada hari d

S dr

Jumlah dari shift yang tersisa pada hari d

x Ld

Variabel ini bernilai 1 jika shift dengan durasi L jam pada hari d terpilih untuk diberikan kepada pegawai ei Membuat pemilihan xLd menjadi lebih baik


41

ILP 2

Batasan 1 ILP2

 x d

Ld

 d eu  5

Batasan untuk 5 hari kerja

L

x Ld

d eu

25 Juli 2013

Variabel ini bernilai 1 jika shift dengan durasi L jam pada hari d terpilih untuk diberikan kepada pegawai ei Variabel untuk jumlah hari kerja yang masih dibawah total hari kerja maksimal ( 5 hari)


42

ILP 2

Batasan 2 ILP2

 x d

Ld

L  ue  oe  Trgte

L

x Ld

Batasan untuk agar durasi jam yang dijadwalkan sesuai dengan target jam kerja mingguan


ue

Jumlah jam kerja yang masih kurang dari target jam kerja mingguan pegawai

oe

Jumlah jam kerja yang diatas target jam kerja mingguan pegawai ei

25 Juli 2013


43

ILP 2

Batasan 3 ILP2

x

Ld

 1, d

Batasan agar hanya 1 shift terpilih per harinya

L

x Ld

25 Juli 2013



44

ILP 2

Batasan 4 ILP2 xLd  ELdr , d, L

x Ld

Eldr

25 Juli 2013

Batasan agar xLd mendapat nilai 1 jika pegawai tersedia untuk shift dengan durasi L jam pada hari d

Variabel ini bernilai 1 jika shift dengan durasi L jam pada hari d terpilih untuk diberikan kepada pegawai ei Jumlah minimum dari pegawai yang tersisa dimana para pegawai tersebut tersedia dan memenuhi syarat untuk shift yang berdurasi L jam pada hari d.


45

ILP 2

Batasan 5,6 ILP2

xLd  biner , d, L d eu , ue , oe  0

25 Juli 2013


46

VERIFIKASI MODEL

VERIFIKASI MODEL

Verifikasi batasan 1 ILP1

a

hstd

. y std  rhtd ,

s

• Patut diperhatikan pada

indeks jam ke-4, nilai ahstd =1, tetapi ystd =0, disinilah nilai shift yang melebihi target =1. Hal Ini disebabkan nilai ystd ke-7 = 1 (dimana indeks shift ke-7 untuk jam kerja 2, 3, 4) karena panjang shift minimal adalah 3 jam.

25 Juli 2013


48

VERIFIKASI MODEL

Verifikasi batasan 2,3,4 ILP1 Batasan 2 u 0 y      std td td  Trgttd , s

Batasan 3

3  0 1  2 Batasan 4

 0td ,  utd  0 25 Juli 2013


49

VERIFIKASI MODEL

Verifikasi batasan 1,2,3 ILP2 Batasan 2 ILP2

Nilai Variabel Keputusan ILP2

 x d

Ld

L  ue  oe  Trgte

L

4  5  5  4  0  0  18 Batasan 3 ILP2

Batasan 1 ILP2

 x d

Ld

x

 d eu  5

25 Juli 2013

 1, d

L

L

4 1  5

Ld

Contoh ini adalah hasil ILP 2 pada iterasi ke-20 untuk data uji coba utama dimana pegawai terpilih adalah pegawai ke-6 Tugas Akhir – KI091391

50

VERIFIKASI MODEL

Verifikasi batasan 4,5,6 ILP2 Batasan 4 ILP2

Batasan 5 ILP2

Batasan 6 ILP2

d eu , ue , oe  0

25 Juli 2013


51

Hasil Penjadwalan untuk data uji coba utama

Parameter Mehran et al. perbandingan Kelebihan jam 4 jam kerja

Hasil Uji Coba

Total deviasi

20 jam

12 jam

Waktu Komputasi

18 menit

5,44 detik

4 jam

Hasil Uji Coba menunjukkan kelebihan jam kerja yang dihasilkan sama, total deviasi yang dihasilkan lebih kecil, dan waktu komputasi yang lebih singkat

25 Juli 2013


52

Hasil Penjadwalan dan Komparasi untuk data uji coba acak

Nama Data Uji Coba

dataset1 dataset2 dataset3 dataset4 dataset5 dataset6 dataset7 dataset8 dataset9 dataset10

rata-rata

Overstaff (jam)

Hasil Uji Coba Total Deviasi/ deviasi pegawai (jam) (jam)

Waktu Komputasi (detik)

Mehran et al. Total Deviasi/ deviasi pegawai (jam) (jam)

Overstaff (jam)

Waktu Komputasi (detik)

2 0 0 1 0 1 0 0 0 0

8 8 4 1 8 3 12 6 10 4

0,2 0,2 0,1 0,025 0,2 0,075 0,3 0,15 0,25 0,1

3,62 3,54 3,45 3,49 3,35 3,82 3,48 3,29 3,49 3,45

2 0 0 1 0 1 0 0 0 0

22 22 20 23 28 9 44 10 26 20

0,55 0,55 0,5 0,575 0,7 0,225 1,1 0,25 0,65 0,5

310 303 295 299 287 327 298 282 299 295

0,5

9,9

0,2475

3,498

0,5

19,7

0,4925

299,5

Hasil Uji Coba menunjukkan bahwa total deviasi lebih kecil hampir di semua data uji coba, overstaff yang dihasilkan sama, dan waktu komputasi yang lebih singkat

25 Juli 2013


53

PRESENTASI TUGAS AKHIR KI091391

Recommend Documents