PENGEMBANGAN MODEL KEPUTUSAN PENERIMAAN ORDER BERBASIS PENJADWALAN MESIN PARALEL NON IDENTIK DENGAN ALGORITMA GENETIKA

PENGEMBANGAN MODEL KEPUTUSAN PENERIMAAN ORDER BERBASIS PENJADWALAN MESIN PARALEL NON IDENTIK DENGAN ALGORITMA GENETIKA Rizal Arryadi1; Ami Amalia Behardi2 ABSTRACT Article focused on the implementation of genetic algorithms in scheduling parallel, non-identical machines in a make-to-order environment, with the objective of maximizing profit. Eventually, the model will further be used for an order acceptance model in a garment company. A new chromosome representation has beens developed in order to simplify the crossover and mutation in the algorithm. Performance investigation of the genetic algorithm is provided for the purpose of avoiding local optima and accelerating the algorithm in reaching a good solution. Keywords: genetic algorithm, parallel machine, order acceptance model

ABSTRAK Artikel membahas penggunaan algoritma genetika dalam memecahkan masalah penjadwalan mesin paralel non identik dengan kriteria minimasi memaksimasi keuntungan, yang selanjutnya akan digunakan dalam model keputusan peneriman order. Sebuah representasi kromosom baru dikembangkan guna menyederhanakan proses operator persilangan dan mutasi. Investigasi atas kinerja algoritma genetika disajikan, terutama dalam menghindari optima lokal dan meningkatkan kecepatan pencapaian solusi. Algoritma dijalankan dengan perangkat lunak spreadsheet MS Excel/VB yang umum digunakan, sehingga dengan mudah dapat diimplementasikan pada perusahaan kecil dan menengah. Kata kunci: algoritma genetika, mesin paralel, model keputusan

1,2

Jurusan Teknik Industri, Fakultas Teknik, Universitas Bina Nusantara Jl. K.H. Syahdan No. 9, Kemanggisan/Palmerah, Jakarta Barat 11480 [email protected]

144

INASEA, Vol. 8 No.2, Oktober 2007: 144-152

PENDAHULUAN Sebuah perusahaan manufaktur garmen skala kecil menengah sering kali dihadapkan pada keputusan penerimaan order. Order yang datang memiliki karakteristik yang hanya dimungkinkan untuk dijadwalkan di mesin tertentu. Sebuah order baru akan diterima, jika hasil penjadwalan ulang ternyata memberikan keuntungan lebih bagi perusahaan dan tidak menimbulkan ongkos penalti keterlambatan yang ternyata lebih besar daripada keuntungan baru yang diterima. Keputusan yang dihasilkan perlu mencakup: Apakah order tersebut akan diterima; Di mesin mana order tersebut akan dijadwalkan; Bagaimana seluruh order akan dijadwalkan. Penelitian didasarkan atas studi kasus di sebuah perusahaan garmen make-toorder yang salah satu divisinya mengkhususkan diri pada pengerjaan bordir. Perusahaan memiliki puluhan mesin bordir yang bersifat non-identik. Tidak seluruh order yang datang dapat dijadwalkan ke mesin bordir tertentu karena tiap mesin memiliki jumlah kepala dan mata benang yang tertentu; Mesin yang mampu menyelesaikan sebuah order ialah yang memiliki jumlah mata benang setidaknya sama dengan jumlah benang yang digunakan dalam bordir tersebut. Di lain pihak, pengerjaan suatu order ke mesin yang berbeda akan memakan biaya yang berbeda, berdasarkan waktu pengerjaan yang berimplikasi pada sumber daya manusia yang dibutuhkan, depresiasi mesin, penggunaan energi, dan komponen biaya yang lain. Satu pekerjaan hanya akan dijadwalkan pada satu mesin; Pemecahan pekerjaan (job splitting) tidak diperkenankan. Order datang secara simultan dan dapat memiliki waktu tenggat (due date) yang berbeda, dengan nilai penjualan maupun besar penalti yang berbeda-beda pula.

PEMBAHASAN Penggunaan Algoritma Genetika dalam penjadwalan mesin telah dilakukan sejak dua dekade terakhir. Mulai dari Goldberg (1989) yang mengkompilasikan dasar penggunaan algoritma genetika dalam masalah penjadwalan; Fox (1991) dan Bruns (1993) memfokuskan pembahasannya pada operator genetika untuk masalah sequencing; Lee (1997) berhasil mengimplementasikannya untuk masalah penjadwalan job shop; dan Arryadi (1999) yang menggunakannya dalam memecahkan masalah penjadwalan fuzzy pada industri kimia multiproduk. Algoritma Genetika merupakan salah satu algoritma pencarian terstruktur yang didasarkan pada analogi mekanisme seleksi dan informasi genetika, dengan meniru beberapa proses yang ditemukan pada proses evolusi.

Pengembangan Model Keputusan… (Rizal Arryadi; Ami Amalia Behardi)

145

Secara umum, tahap yang akan ditempuh dalam algoritma genetika adalah sebagai berikut: Inisialisasi, yaitu penentuan populasi awal secara acak sebagai langkah awal pencarian; Evalusi, yaitu penentuan fungsi suaian tiap individu berdasarkan tujuan yang ingin dicapai; Pembangkitan operator genetika untuk menentukan alternatif solusi baru; Pemilihan populasi baru, lalu kembali ke tahap 2. Evolusi terjadi pada kromosom, alat organik yang mengkodekan struktur makhluk hidup. Kodifikasi solusi penjadwalan ke dalam bentuk kromosom yang tepat dan efisien merupakan tantangan tersendiri dalam perancangan algoritma genetika. Pada masalah penjadwalan, representasi kromosom dapat digolongkan menjadi dua jenis: Representasi langsung, yaitu kromosom langsung merepresentasikan suatu solusi dari permasalahan dan representasi tidak langsung, yaitu jika untuk memperoleh solusi diperlukan prosedur tambahan. David (1985), Nakano (1990), Syswerda (1991), dan Bagchi (1991) telah mengembangkan penelitian yang didasarkan pada representasi tidak langsung; Sementara Kanet (1991) mengembangkan representasi langsung. Penentuan ruang sampling dan mekanisme sampling memegang peranan penting dalam efektivitas dan efisiensi algoritma genetika dalam mencapai solusi terbaiknya. Gen & Cheng (1997) dan Arryadi (1999) telah memaparkan perkembangan dan perbandingan penelitian sebelumnya yang telah dilakukan pada penentuan ruang sampling. Tantangan lain adalah pemilihan dan/atau pengembangan operator genetika. Secara garis besar, operator genetika dibagi menjadi dua kelas, yaitu unary operator dan binary operator. Konsep unary operator adalah mengambil urutan awal dan menyusun kembali sebagian urutan tersebut dengan mempertahankan urutan yang lain. Walaupun terbilang lebih sederhana, namun binary operator lebih disukai karena kapabilitasnya dalam menghasilkan atribut yang lebih baik sebagai campuran dari dua induk (Fox & McMahon, 1991).Meskipun demikian, unary operator sering dianggap ampuh dalam mereduksi kemungkinan algoritma terjebak dengan cepat ke dalam lokal optima. Unary operator, atau mutasi, yang telah dikembangkan untuk masalah penjadwalan diantaranya adalah position-based mutation, order-based mutation, splice operator, dan inversion operator. Binary operator yang telah dikembangkan untuk masalah penjadwalan, diantaranya adalah PMX (Goldberg, 1989), Position-based Crossover (Davis, 1991), dan Cycle Crossover (Goldberg, 1989).

146

INASEA, Vol. 8 No.2, Oktober 2007: 144-152

Perancangan Algoritma Mulai

Generate populasi secara acak

Tentukan ruang seleksi

Persilangan

Cek legalitas kromosom

Mutasi

Y Evaluasi

Pembentukan populasi baru

Kriteria pemberhentian terpenuhi

Berhenti

Gambar 1 Langkah Implementasi Algoritma Genetika

Representasi Kromosom dan Tahap Kodifikasi Tiap kromosom merepresentasikan sebuah alternatif solusi dari permasalahan yang diangkat pada algoritma genetika. Adalah tantangan tersendiri dalam masalah penjadwalan, bahwa selalu terjadi trade-off pada representasi kromosom yang dirancang, yaitu dari segi kesederhanaan dan singkatnya kromosom, kemudahan penentuan fungsi suaian, kemudahan operator genetika beroperasi, dan kemudahan pengembangan kromosom pada saat terjadi tambahan sumber daya yang perlu dijadwalkan.

Pengembangan Model Keputusan… (Rizal Arryadi; Ami Amalia Behardi)

147

. Waktu

1

2

3

4

5

6

7

1

2

3

4

5

6

7

1

2

3

4

5

6

7

Mesin

1

1

1

1

1

1

1

2

2

2

2

2

2

2

3

3

3

3

3

3

3

Kromosom

1

1

1

0

6

6

6

7

0

9

9

2

2

5

0

0

4

3

3

3

0

Gambar 2 Representasi Kromosom

Dalam penelitian ini, tiap lokus merepresentasikan pekerjaan yang akan dijadwalkan pada mesin tertentu dan pada waktu tertentu. Kombinasi mesin dan waktu diurutkan, seperti terlihat pada Gambar 2 Representasi ini mengasumsikan bahwa seseorang dapat menjadwalkan pekerjaan untuk 7 hari secara maksimal. Angka 0 (nol) menunjukkan tidak adanya pekerjaan yang dijadwalkan pada mesin dan slot waktu tersebut.

Inisialisasi Di tahap awal algoritma, satu set populasi dibangkitkan dengan mengindahkan kendala penjadwalan yang telah ditetapkan, termasuk memungkinkan tidaknya pekerjaan tersebut dijadwalkan di mesin tertentu dan jumlah slot waktu yang dibutuhkan untuk tiap pekerjaan untuk tiap mesin. Ukuran populasi yang terlalu besar atau terlalu kecil berpotensi untuk mengurangi efektivitas dan efisiensi algoritma dalam mencapai solusi yang baik (Arryadi, 1999). Dalam penelitian ini, ukuran populasi yang digunakan adalah 10.

Ruang Sampling/Seleksi Guna mencegah hilangnya kromosom terbaik dari populasi, seleksi dirancang sedemikian hingga beberapa kromosom terbaik langsung diturunkan menjadi kandidat populasi turunan. Proporsi kromosom terbaik yang akan dipertahankan adalah 30%.

Operator Genetika Secara umum, operator genetika yang digunakan terdiri dari dua, meliputi operator mutasi dan operator persilangan. Operator mutasi yang dikembangkan didasarkan pada Order-based Mutation yang dimodifikasi sementara operator persilangan yang dipakai dikembangkan dari Partially Mapped Crossover (PMX). Induk 1

A B C D E

F G H

Induk 2

K A G F B D H

I

I

J

K

J

C E

A E C F

Turunan 1

B D H G

Turunan 2

K A H D E

F G

I

I

J

K

J

C B

Gambar 3 Partially-Mapped Crossover

148

INASEA, Vol. 8 No.2, Oktober 2007: 144-152

Dalam operator persilangan PMX, turunan diciptakan dengan menentukan dua cutpoint. Posisi gen yang berada diantara dua cutpoint tersebut diturunkan pada individu baru (namun dipertukarkan antara turunannya) sedangkan sisanya merupakan pertukaran dari mapping section tadi. Modifikasi PMX dilakukan, terutama untuk menjamin bahwa turunan yang dihasilkan selalu legal, yaitu memenuhi kendala penjadwalan yang ditentukan. A

Induk

B C D E

F

G H

I

J

A H

I

Turunan

D E

F

G B C

J

Gambar 4 Order-based Mutation

Order-based mutation merupakan operator di mana sekelompok gen ditukarkan dengan sekelompok gen yang lain, dengan mempertahankan urutan di dalam kelompok tersebut. Seperti halnya operator persilangan, modifikasi order-based mutation dilakukan untuk menjamin bahwa turunan yang dihasilkan selalu legal. Probabilitas persilangan dan mutasi merupakan parameter yang umum didefinisikan untuk meningkatkan kinerja algoritma genetika tanpa membuat algoritma terjebak kepada optima lokal. Dalam penelitian ini, probabilitas persilangan dan mutasi ditentukan 70%.

Evaluasi Kromosom terbaik, kromosom hasil persilangan, kromosom hasil mutasi, beserta induk yang tidak mengalami persilangan maupun mutasi dikumpulkan ke dalam ruang evaluasi, dan kromosom terbaik sejumlah ukuran populasi akan dipilih untuk diwariskan menjadi kromosom turunan. Evaluasi atas tiap kromosom ditentukan berdasarkan kriteria maksimasi keuntungan total. Tabel 1 Evaluasi Durasi Batas Jumlah Upah Durasi Durasi Jumlah Pengerjaan Mulai Waktu Pesanan Tipe Pesanan Pengerjaan Pengerjaan Pengerjaan Benang pada Mesin Pengerjaan Pengiriman (m) (xRp.1000) Total (jam) Total (hari) (jam) (hari) 1 2 3 4 5 6 7 8 9

FO HI FO FO HI FO FO HI HI

3 4 3 3 3 3 3 3 3

1,198,000.0 719,900.0 1,199,000.0 959,780.0 479,700.0 1,199,500.0 958,900.0 479,800.0 719,900.0

9,290.0 3,900.0 9,300.0 7,440.0 2,600.0 9,300.0 7,430.0 2,610.0 3,910.0

99.8 60.0 99.9 80.0 40.0 100.0 79.9 40.0 60.0

119.8 72.0 119.9 96.0 48.0 120.0 95.9 48.0 72.0

5 3 5 4 2 5 4 2 3

01/06/07 01/06/07 01/06/07 01/06/07 01/06/07 01/06/07 01/06/07 01/06/07 01/06/07

06/06/07 05/06/07 06/06/07 05/06/07 03/06/07 06/06/07 05/06/07 06/06/07 05/06/07

Biaya Keterlambatan/hari (xRp.1000) 7% biaya maks 5% biaya maks 7% biaya maks 6% biaya maks 4% biaya maks 7% biaya maks 6% biaya maks 4% biaya maks 5% biaya maks

65.0 27.9 65.1 44.6 14.9 65.1 44.6 14.9 27.9

Pengembangan Model Keputusan… (Rizal Arryadi; Ami Amalia Behardi)

Tidak Biaya Dapat Maksimum Dikerjakan (xRp.1000) pada M1 -

149

928.7 557.9 929.4 743.9 371.8 929.7 743.3 371.9 557.9

Hasil Algoritma Genetika diimplementasikan dengan spreadsheet Microsoft Excel dan Visual Basic Macro. Gambar 5 memperlihatkan kinerja algoritma dalam 100 generasi. Populasi pertama, yang dibangkitkan secara acak, memiliki pendapatan tertinggi 60.936.020 dengan biaya terendah sebesar Rp 6.003.979, sementara setelah generasi ke 100, pendapatan tertinggi sebesar Rp 61.256.799 dengan biaya terendah sebesar Rp 5.683.200. Seperti diharapkan, tidak didapatkan pola yang menarik dari sebaran biaya dalam populasi dengan digunakannya mekanisme seleksi dalam penelitian ini. Perubahan Pendapatan dalam 100 Generasi 61,500,000.0 61,400,000.0 61,300,000.0

Biaya (Rp.)

61,200,000.0 61,100,000.0 61,000,000.0 60,900,000.0 60,800,000.0 60,700,000.0 60,600,000.0 0

5

10

15

20

25

30

35

40

45

50

55

60

65

70

75

80

85

90

95 100

Generasi Terbaik

Rata-rata

Gambar 5 Kinerja Algoritma atas Pendapatan Standar Deviasi Biaya 200.0 180.0 160.0 140.0 120.0 100.0 80.0 60.0 40.0 20.0 0.0 0

5

10

15

20

25

30

35

40

45

50

55

60

65

70

75

80

85

90

95

100

Generasi

Gambar 6 Standar Deviasi Biaya terhadap generasi

Populasi awal diurutkan sedemikian rupa sehingga menyerupai sebuah worst case scenario dan pasti terjadi keterlambatan. Tabel 2 menjelaskan perbandingan antara situasi terburuk tersebut dengan penerimaan pesanan ke-10 dengan situasi baik dengan penerimaan hanya sembilan pesanan. Hal itu membuktikan bahwa walaupun dengan

150

INASEA, Vol. 8 No.2, Oktober 2007: 144-152

situasi yang terburuk sekalipun, menerima pesanan ke-10 dibandingkan dengan hanya sembilan masih lebih menguntungkan. Faktor tingginya pendapatan itu dapat mengantar perusahaan untuk membuat keputusan dalam menerima pesanan ke-10, walaupun pasti akan menimbulkan keterlambatan. Situasi itu mungkin terjadi karena besarnya upah yang diberikan oleh pesanan ke-10 yang jauh nilainya dibandingkan dengan pesanan yang lain. Tabel 2 Perbandingan Antara Penerimaan Jumlah Pesanan Menerima 9 Pesanan Biaya (Rp.) Pendapatan (Rp.)

Menerima 10 Pesanan

4,614,000.0 Biaya Tertinggi (Rp.) 6,269,580.4 51,166,000.0 Pendapatan Terrendah (Rp.) 60,670,419.6 Perbedaan Pendapatan (Rp.) 9,504,419.6

Dalam penelitian ini, hanya tiga kromosom terbaik pada setiap populasi akan diturunkan menjadi kandidat. Semakin banyak kromosom yang diambil untuk diturunkan melalui seleksi maka semakin tinggi pula kemungkinan populasi setelahnya untuk menyerupainya. Angka itu ditetapkan supaya populasi berikutnya tidak sama dengan populasi yang diproses, namun masih memberikan kesempatan untuk gen yang dibangkitkan menyerupai induknya. Peluang persilangan ialah 0.7, dan semakin tinggi peluang, semakin besar kemungkinan kromosom untuk “kawin”. Bila peluang adalah 1, dengan jelas semua kromosom akan disilangkan. Jika ini diterapkan maka proses optimasi akan sangat lambat. Peluang persilangan ditetapkan sedemikian sehingga menekan waktu yang diperlukan untuk mencapai titik optimal. Operator terakhir yang digunakan ialah mutasi dan peluangya sebanyak 0.3. Secara teoritis, operator persilangan dan seleksi saja mampu untuk menghasilkan optimasi karena cenderung memilih dan menurunkan hanya yang terbaik. Akan tetapi, tanpa mutasi, sangat mungkin bahwa titik optimal yang tercapai hanyalah local optimum. Dengan adanya mutasi, gen mampu untuk diacak secara random sehingga mengubah populasi untuk menjadi lebih variatif. Variasi berarti memberikan pilihan yang lebih banyak untuk diturunkan dan dapat dicapai global optimum.

PENUTUP Algoritma Genetika dapat digunakan dengan fleksibel untuk kasus penjadwalan di industri garmen dengan banyak kendala dibandingkan dengan algoritma heuristik penjadwalan yang telah tersedia. Kebijakan untuk mempertahankan sebagian kromosom terbaik untuk bertahan di dalam populasi dapat mencegah hilangnya individu terbaik. Meskipun demikian, penelitian lanjutan perlu dilakukan untuk membuktikan peran kebijakan tersebut dalam memperlambat kinerja algoritma dan mendorong algoritma ke jebakan optimal lokal.

Pengembangan Model Keputusan… (Rizal Arryadi; Ami Amalia Behardi)

151

DAFTAR PUSTAKA Arryadi, Rizal. 1999. Pengembangan Model Keputusan Penjadwalan Fuzzy Berdasarkan Prinsip Keandalan pada Industri Proses Kimia Batch Multiproduk dengan Algoritma Genetika. Bandung: Institut Teknologi Bandung. Bagchi, Sugato. Serdar Uckun, Yutaka Miyabe, and Kazuhiko Kawamura. 1991. “Exploring Problem-Specific Recombination Operators for Job Shop Scheduling.” Proceedings of the Forth International Conference of Genetic Algorithms. California: Morgan Kaufmann Publishers. Bruns, Ralf .1993. “Direct Chromosome Representation and Advanced Genetic Operators for Production Scheduling.” Proceedings of the Fifth International Conference of Genetic Algorithms. California: Morgan Kaufmann Publishers. Coley, David A. 1999. An Introduction to Genetic Algorithms for Scientists and Engineers. Singapore: World Scientific Publishing. Davis, Lawrence. 1991. Handbook of Genetic Algorithms. New York: Van Nostrand Reinhold. Fox, B.R., and M.B. McMahon. 1991. Foundation of Genetic Algorithms: Genetic Operators for Sequencing Problems. California: Morgan Kaufmann Publishers. Gen, Mitsuo and R. Cheng. 1996. Genetic Algorithm and Engineering Design. New York: John-Wiley & Sons Inc. Goldberg, David E. 1989. Genetic Algorithms in Search, Optimization and Machine Learning. Redwood City: Addison-Wesley. Lee, C.Y., S. Piramuthu, Y.K. Tsai. 1997. “Job Shop Scheduling with a Genetic Algorithm and Machine Learning.” International Journal of Production Research, Vol 35 no. 44 pp. 1171-1191. Nakano, Ryohei. 1990. Conventional Genetic Algorithm for Job Shop Problems. Proceedings of the Forth International Conference of Genetic Algorithms. California: Morgan Kaufmann Publishers. Syswerda, Gilbert. 1991. Foundation of Genetic Algorithm: A Study of Reproduction in Generational and Steady State Genetic Algorithms. California: Morgan Kaufmann Publishers.

152

INASEA, Vol. 8 No.2, Oktober 2007: 144-152