penjadwalan tepat waktu pada mesin tunggal
TRANSCRIPT
Penjadwalan Tepat Waktu pada Mesin Tunggal
Mempertimbangkan Konsumsi Energi
1st Bobby Kurniawan
Jurusan Teknik Industri
Universitas Sultan Ageng Tirtayasa
Serang, Indonesia
Abstrak—Permintaan energi yang meningkat akibat
pertumbuhan ekonomi dan populasi dapat membawa masalah
kelangkaan energi disebabkan sumber energi yang dipakai saat ini
merupakan sumber daya yang tidak dapat diperbaharui. Selain
itu, gas karbon dioksida efek samping dari industrialisasi dapat
membahayakan lingkungan. Oleh karena itu, metode atau
prosedur yang ramah lingkungan menjadi sangat penting.
Penelitian ini membahas penjadwalan tepat waktu (just-in-time)
mesin tunggal yang memperhitungkan konsumpsi energi.
Konsumsi energi merupakan fungsi dari kecepatan mesin. Tujuan
dari penjadwalan adalah meminimasi jumlah earlines/tardiness
dan konsumpsi energi. Model penjadwalan merupakan masalah
optimisasi multi-obyektif. Algoritma NSGA-II digunakan untuk
memecahkan masalah penjadwalan. Model penjadwalan dapat
digunakan oleh pemangku keputusan untuk menentukan
alternatif solusi yang mempertimbangkan energi dan lingkungan.
Kata Kunci—earliness/tardiness, energi, NSGA-II, penjadwalan
mesin tunggal, tepat waktu
I. PENDAHULUAN
Energi telah menjadi kebutuhan primer dalam kehidupan manusia. Energi merupakan penggerak ekonomi dan penunjang aktivitas kehidupan. Oleh karena itu, pertumbuhan populasi dan perkembangan ekonomi akan menyebabkan kenaikan konsumsi energi. Berdasarkan laporan tahunan Energy Information Administration (EIA), konsumsi energi hingga 2050 akan meningkat sebesar 50% dan sektor industri merupakan pengguna energi terbesar dengan proporsi sekitar 50% [1]. Saat ini, bahan bakar fosil yang tidak dapat diperbaharui merupakan sumber energi yang dominan digunakan untuk menghasilkan energi. Dengan demikian, pertumbuhan konsumsi energi yang tinggi akan menyebabkan cepatnya bahan bakar fosil habis. Selain itu, pembakaran bahan bakar fosil menghasilkan gas karbon dioksida yang bertanggung jawab terhadap pemanasan global dan perubahan iklim. Oleh karena itu, pertumbuhan kebutuhan energi dapat menimbulkan dua masalah penting yang berdampak terhadap kehidupan manusia: energi dan lingkungan.
Untuk mengurangi dampak negatif tersebut, pemerintah berbagai negara telah mengeluarkan kebijakan-kebijakan untuk pemakaian energi yang efisien. Sebagai contoh adalah menambah proporsi sumber daya energi terbaharui secara bertahap dan memberlakukan tarif listrik sesuai dengan jumlah permintaan. Insentif kepada pengguna untuk merubah pola konsumpsi energi.
Sektor industri sebagai pengguna energi terbesar dituntut untuk dapat meningkatkan efisiensi dan mereduksi konsumsi. Salah satu upaya yang dilakukan dalam rangka efisiensi dan reduksi konsumsi adalah dengan cara perencanaan dan penjadwalan aktifitas dengan efektif.
Penggunaan metode penjadwalan untuk mereduksi konsumsi energi juga telah dilakukan dalam beberapa penelitian. Mouzon, Yildirim, dan Twomey [2] melakukan studi penjadwalan mesin tunggal dengan mekanisme mematikan mesin apabila dalam keadaan idle dan menyalakan kembali apabila job akan diproses. Mematikan mesin akan mengurangi biaya listrik akan tetapi akan menimbulkan biaya setup. Oleh karena itu, trade-off antara biaya listrik dan biaya setup menjadikan masalah ini menjadi masalah optimisasi multi-obyektif. Penelitian serupa (penjadwalan mesin dengan mekanisme on/off) dilakukan pada penjadwalan batch [3]. Shrouf, Ordieres-Meré, García-Sánchez, dan Ortega-Mier [4] melakukan penelitian penjadwalan mesin tunggal dengan mempertimbangkan konsumpsi listrik yang mengikuti tarif time-of-use (TOU), di mana tarif listrik di suatu periode berbeda dengan tarif di periode lain. Prinsip dasar dari penjadwalan dengan tarif TOU adalah menggeser proses dari periode yang memiliki tarif mahal ke periode yang memiliki tarif murah [5, 7]. Penelitian-penelitian pada penjadwalan tarif TOU antara lain dapat ditemukan pada [8, 10].
Mekanisme lain yang digunakan dalam penjadwalan untuk mereduksi energi adalah dengan menggunakan mekanisme pengaturan kecepatan mesin. Kecepatan mesin dapat diatur untuk merubah waktu proses job. Mesin dapat bekerja dalam mode cepat sehingga membuat waktu proses sebuah job menjadi kecil. Akan tetapi, mesin membutuhkan lebih banyak energi. Trade-off yang terjadi adalah waktu proses yang semakin cepat dengan kebutuhan energi. Penelitian-penelitian yang dilakukan dengan mekanisme ini antara lain dapat dilihat pada [11, 12].
Terinspirasi oleh pentingnya energi dan penjadwalan sebagai metode untuk mereduksi konsumsi energi, penelitian ini membahas mengenai penjadwalan tepat waktu mesin tunggal dengan mempertimbangkan konsumsi energi. Konsumpsi energi merupakan fungsi dari kecepatan mesin. Perbedaan penelitian ini dengan penelitian sebelumnya adalah terletak pada fungsi tujuan. Penelitian sebelumnya memiliki fungsi tujuan makespan dan konsumsi energi. Sedangkan penelitian ini memiliki fungsi tujuan earliness/tardiness dan konsumsi energi.
RO-12
TIDAK D
IPRESENTASIK
AN
Mengingat bahwa model penjadwalan memiki fungsi tujuan lebih dari satu, metode non-dominated sorting algorithm (NSGA-II) yang telah dimodifikasi sesuai dengan karakteristik masalah digunakan untuk menentukan himpunan solusi tidak didominasi (non-dominated solutions) atau dikenal sebagai Pareto front. Percobaan numerik dilakukan pada berbagai masalah yang dibangkitkan secara acak.
Adapun struktur dari penelitian ini adalah sebagai berikut. Bagian I menjelaskan pendahuluan. Bagian II mendeskripsikan masalah. Bagian III menjelaskan proses modifikasi NSGA-II. Bagian IV menjelaskan mengenai percobaan numerik. Bagian V mengakhiri penelitian ini dengan kesimpulan dan penelitian lanjutan
II. FORMULASI MASALAH
Adapun masalah penjadwalan tepat waktu mesin tunggal dengan mempertimbangkan konsumsi energi adalah sebagai berikut. Sebuah lantai produksi memiliki sebuah mesin untuk memproses N buah job. Kecepatan mesin dapat diatur menjadi tiga buah mode: cepat, normal, sedang. Apabila mesin dioperasikan dalam mode cepat, waktu proses sebuah job akan menjadi lebih singkat dibandingkan apabila mesin bekerja dalam mode normal atau lambat. Mesin membutuhkan energi lebih banyak pada mode cepat dibandingkan apabila mesin dalam mode normal atau lambat.
Energi mesin menggunakan mode tertentu dilambangkan dengan ei. Apabila mesin bekerja pada suatu mode, energi yang dikonsumsi tetap selama mesin mengerjakan suatu job dengan mode tertentu.
Waktu proses sebuah job dinotasikan sebagai pij, di mana i merupakan indeks mode mesin dan j merupakan indeks job. Setiap job memiliki waktu tenggat (due date), dj. Waktu sebuah job selesai diproses dinotasikan sebagai Cj. Sebuah job harus selesai tepat waktu. Apabila job selesai diproses sebelum tenggat waktu, job tersebut akan dikenakan penalti earliness. Sebaliknya, apabila job tersebut terlambat, maka job akan dikenakan penalti tardiness. Fungsi tujuan dari masalah penjadwalan dinyatakan sebagai
Min
M
i
N
j
iji
N
j
jj peTE1 11
(1)
di mana Ej dan Tj adalah earliness dan tardiness dari job j. Earliness dinyatakan sebagai Ej = max{0, dj – Cj}, sedangkan tardiness dinyatakan sebagai Tj = max{0, Cj – dj}.
Dengan demikian, masalah penjadwalan ini termasuk optimisasi multi-obyektif. Metode NSGA-II yang telah dimodifikasi diusulkan untuk mencari himpunan solusi tidak didominasi. Metode NSGA-II merupakan salah satu metode multi-obyektif algoritma evolusioner yang sangat populer digunakan untuk masalah optimisasi multi-obyektif [13].
III. METODE SOLUSI
A. Encoding
Skema encoding yang digunakan adalah dua buah vektor dengan ukuran N. Vektor pertama menyatakan job, sedangkan
vektor kedua menyatakan mode kecepatan yang dipakai oleh mesin dalam memproses sebuah job.
Gambar 1. Skema encoding dari individu
Gambar 1 merupakan sebuah individu atau kromosom terdiri dari 8 job dan mesin yang memiliki 3 buah mode kecepatan. Mode 1 menyatakan mesin beroperasi dengan kecepatan lambat, mode 2 menyatakan mode normal, dan mode 3 menyatakan mesin menggunakan mode cepat. Pada Gambar 1, job 7 dikerjakan pada urutan ke-4 dengan menggunakan mode 2.
B. Ranking dan crowding distance
Pada masalah optimisasi satu obyektif, kualitas individu dapat ditentukan melalui nilai dari fungsi obyektif. Untuk masalah optimisasi multi-obyektif, hal ini tidak dapat dilakukan. Oleh karena itu, kualitas suatu individu dapat dinilai berdasarkan peringkat atau ranking dan crowding distance.
Individu-individu dalam sebuah populasi dapat dikategorikan atau dibagi berdasarkan ranking. Individu-individu yang tidak didominasi oleh individu lain diberikan ranking 1. Selanjutnya, individu-individu diberikan ranking 2 apabila individu-individu tersebut hanya didominasi oleh individu-individu yang memiliki ranking 1. Pemberian ranking digunakan berdasarkan algoritma dari Deb, Pratap, Agarwal, dan Meyarivan [13].
Gambar 2. Kualitas individu: (a) ranking, (b) crowding distance
Setelah tiap individu dikelompokan berdasarkan ranking, maka individu-individu dalam populasi diberikan nilai crowding distance. Semakin besar nilai crowding distance yang dimiliki oleh sebuah individu, semakin baik individidu tersebut karena individu tersebut terletak di lokasi yang tidak padat.
C. Seleksi, crossover, dan mutasi
Seleksi individu yang akan melakukan perkawinan silang (crossover) dengan individu lain menggunakan seleksi turnamen biner. Setelah turnamen biner dilakukan, crossover dilakukan menggunakan metode single point crossover.
Sedangkan untuk mutasi, dua buah jenis mutasi dilakukan. Yang pertama adalah pertukaran job (swapping). Mutasi jenis
RO-13
TIDAK D
IPRESENTASIK
AN
kedua adalah mengubah laju mesin. Contoh dari mutasi diilustrasikan pada Gambar 3.
Gambar 3. Mutasi: (a) job swapping, (b) speed changing
D. Algoritma NSGA-II yang diperbaharui
Adapun prosedur lengkap dari NSGA-II yang telah diperbaharui adalah sebagai berikut. Pada inisiasi (t = 0), populasi P sejumlah popSize dibangkitkan secara acak. Selanjutnya, setiap individu dalam populasi ditentukan ranking dan crowding distance.
Setelah itu, seleksi menggunakan turnamen biner dilakukan untuk memilih individu-individu yang akan melakukan perkawinan. Selanjutnya perkawinan dilakukan menghasilkan keturunan Pc. Proses selanjutnya adalah mutasi yang dilakukan pada individu yang dipilih secara acak. Hasil dari mutasi dinotasikan sebagai Pm.
Setelah proses crossover dan mutasi dilakukan, individu-individu baru yang dihasilkan digabung dengan populasi awal, Pt+1 ← Pt + Pc + Pm. Gabungan populasi baru ini Pt+1 kemudian diurutkan berdasarkan ranking dan crowding distance. Individu-individu sebanyak popSize dari hasil pengurutan Pt+1 disimpan sebagai populasi yang digunakan untuk proses evolusi pada generasi selanjutnya. Proses ini diulang sampai kondisi terminasi algoritma tercapai.
IV. PERCOBAAN NUMERIK
Algoritma diimplementasikan menggunakan program JAVA. Percobaan numerik dilakukan pada laptop prosesor hexa core i7 dengan memori 8 GB RAM.
A. Problem instace
Sebanyak 10 buah problem instance dibangkitkan secara acak. Mesin memiliki 3 mode kecepatan: lambat (mode 1), normal (mode 2), dan cepat (mode 3). Waktu proses setiap job menggunakan mesin dibangkitkan secara acak menggunakan distribusi seragam [1, 15]. Konsumsi energi mesin dibangkitkan dengan bilangan acak [5, 20]. Waktu tenggat suatu job dihitung menggunakan persamaan
MN
p
Hd
M
i
N
j
ij
j
1 1* (2)
di mana H adalah bilangan acak dengan distribusi seragam antara 1,2 dan 1,5, M adalah jumlah mode kecepata mesin, N adalah jumlah job, dan pij adalah waktu proses job j apabila diproses menggunakan mode i.
B. Parameter
Parameter yang digunakan oleh algoritma NSGA-II yang disempurnakan adalah sebagai berikut. Jumlah populasi popSize adalah 200. Probabililitas crossover dan mutasi adalah 0,75 dan 0,01. Algoritma NSGA-II dieksekusi sebanyak 10 kali untuk setiap instance. Satu kali eksekusi adalah 100 detik.
C. Metriks performansi
Untuk mengukur performansi algoritma dalam menyelesaikan masalah penjadwalan, digunakan dua buah metrik. Metrik pertama adalah jumlah solusi tidak didominasi yang ditemukan oleh algoritma dalam satu kali eksekusi. Metrik ini dinotasikan dengan ND. Makin besar nilai ND, semakin baik algoritma. Sedangkan metrik kedua yang digunakan dalam penelitian ini adalah generational distance (GD). GD mengukur jarak Euclidian dari setiap solusi tidak didominasi yang ditemukan oleh suatu algoritma (A) dengan solusi terdekat dari himpunan solusi yang menjadi referensi (B). GD dihitung menggunakan persamaan
SGD
S
s
s
1
(3)
dengan S adalah jumlah solusi tak didominasi, s adalah indeks dari solusi tak didominasi, dan Δ adalah jarak Euclidian terdekat dari solusi ke-k dengan sebuah solusi dari himpunan referensi. Algoritma yang memiliki nilai GD yang kecil lebih baik dibandingkan dengan algoritma yang menghasilkan GD yang besar.
D. Analisa hasil percobaan
TABEL I. HASIL PERCOBAAN NUMERIK
No Jumlah job ND GD
1 5 38 0,13
2 10 43 0,67
3 15 22 2,71
4 20 18 4,79
5 25 46 8,63
6 30 17 18,73
7 35 49 21,43
8 40 15 43,85
RO-14
TIDAK D
IPRESENTASIK
AN
Tabel I menampilkan hasil dari percobaan numerik. Setiap instance dieksekusi 10 kali.
No Jumlah job ND GD
9 45 21 53,01
10 50 30 45,23
Rata-rata 29,9 19,92
Dari hasil pada Tabel I dapat disimpulkan bahwa algoritma NSGA-II yang disempurnakan cukup baik dalam mencari himpunan solusi tidak didominasi dari masalah penjadwalan. Hal ini dapat dilihat dengan cukup kecilnya nilai rata-rata GD, yaitu sebesar 19,92. Sedangkan kemampuan algoritma dalam mencari solusi tidak didominasi ND cukup besar, yaitu sebesar 29,9.
V. KESIMPULAN DAN PENELITIAN LANJUTAN
Penelitian ini membahas masalah penjadwalan multi-obyektif dari mesin tunggal dengan tujuan meminimasi earliness/tardiness dan konsumpsi energi. Masalah penjadwalan diselesaikan dengan metode NSGA-II yang disempurnakan. Berdasarkan hasil percobaan numerik, algoritma NSGA-II yang disempurnakan cukup baik dalam mencari solusi tidak didominasi. Penelitian lanjutan adalah melakukan verifikasi dengan membandingkan hasil dari NSGA-II dengan metode lain, seperti multi-objective evolutionary algorithm with decomposition (MOEA/D) atau strength Pareto evolutionary algorithm (SPEA2). Model penjadwalan dapat dikembangkan dengan mempertimbangkan tarif TOU.
UCAPAN TERIMAKASIH
Penulis mengucapkan terima kasih kepada reviewer yang telah memberikan komentar bagi penelitian ini.
DAFTAR PUSTAKA
[1] Energy Information Administration, “International energy outlook 2019 with projections to 2050,” Technical report, U.S. Energy Information Administration Office of Energy Analysis, 2019.
[2] G. Mouzon, M. B. Yildirim, and J. Twomey, “Operational methods for minimization of energy consumption of manufacturing
equipment,International Journal of Production Research, vol. 45, pp. 4247–4271, 2007.
[3] A. Che, X. Wu, J. Peng, and P. Yan, “Energy-efficient biobjective single-machine scheduling with power-down mechanism,” Computers and Operations Research, vol. 85, pp. 172–183.
[4] F. Shrouf, J. Ordieres-Meré, A. García-Sánchez, and M. Ortega-Mier, “Optimizing the production scheduling of a single machine to minimize total energy consumption costs,” Journal of Cleaner Production, vol. 67, pp. 197–207, 2014.
[5] B. Kurniawan, A. A. Gozali, W. Weng and S. Fujimura, "A genetic algorithm for unrelated parallel machine scheduling minimizing makespan cost and electricity cost under time-of-use (TOU) tariffs with job delay mechanism," in 2017 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), pp. 583–587, 2017.
[6] B. Kurniawan, A. A. Gozali, W. Weng and S. Fujimura, " A mix integer programming model for bi-objective single machine with total weighted tardiness and electricity cost under time-of-use tariffs", IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), pp. 137–141, 2018.
[7] B. Kurniawan, W. Chandramitasari, A. A. Gozali, W. Weng, and S. Fujimura, “Triple-chromosome genetic algorithm for unrelated parallel machine scheduling under time-of-use tariffs,” IEEJ Transactions on Electrical and Electronic Engineering, vol. 15, pp. 208–217, 2020.
[8] J. Y. Moon, K. Shin, and J. Park, “Optimization of production scheduling with time-dependent and machine-dependent electricity cost for industrial energy efficiency,” The International Journal of Advanced Manufacturing Technology, vol. 68, pp. 523–535, 2013.
[9] K. Fang, N. A. Uhan, F. Zhao, and John W. Sutherland, “Scheduling on a single machine under time-of-use electricity tariffs,” Annals of Operations Research, vol. 238, pp. 199–227, 2016.
[10] B. Kurniawan, W. Song, W. Weng, and S. Fujimura, “Distributed-elite
local search based on a genetic algorithm for biobjective job-shop scheduling under time-of-use tariffs,” Evolutionary Intelligence, in press.
[11] D. Tang and M. Dai, “Energy-efficient approach to minimizing the energy consumption in an extended job-shop scheduling problem,” Chinese Journal of Mechanical Engineering, vol. 28, pp. 1048–1055, 2015.
[12] M. A. Salido, J. Escamilla, A. Giret, and F. Barber, “A genetic algorithm for energy-efficiency in job-shop scheduling,” The International Journal of Advanced Manufacturing Technology, vol. 85, pp. 1303–1314, 2016.
[13] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: NSGA-II,” IEEE Transactions on Evolutionary Computation, vol. 6, pp.182–197, 2002.
RO-15
TIDAK D
IPRESENTASIK
AN