Penjadwalan Flow Shop untuk Meminimasi Total Tardiness Menggunakan Algoritma Cross Entropy–Algoritma Genetika

Dana Marsetiya Utama; Leo Rizki Ardiansyah; Annisa Kesy Garside

doi:10.25077/josi.v18.n2.p133-141.2019

Dana Marsetiya Utama

Universitas Muhammadiyah Malang

Leo Rizki Ardiansyah

Universitas Muhammadiyah Malang

Annisa Kesy Garside

Universitas Muhammadiyah Malang

Keywords

scheduling, total tardiness, flow shop, cross entropy, genetic algorithm

Abstract

Flow shop scheduling problems much studied by several researchers. One problem with scheduling is the tardiness. Total tardiness is the performance to minimize tardiness jobs. it is the right performance if there is a due date. This study proposes the Cross-Entropy Genetic Algorithm (CEGA) method to minimize the mean tardiness in the flow shop problem. In some literature, the CEGA algorithm is used in the case of minimizing the makespan. However, CEGA not used in the case of minimizing total tardiness. CEGA algorithm is a combination of the Cross-Entropy Algorithm which has a function to provide optimal sampling distribution and Genetic Algorithms that have functions to get new solutions. In some numeric experiments, the proposed algorithm provides better performance than some algorithms. For computing time, it is affected by the number of iterations. The higher the iteration, computing requires high time.

Downloads

Download data is not yet available.

References

[1] D. M. Utama, "Analisa Perbandingan Penggunaan Aturan Prioritas Penjadwalan Pada Penjadwalan Non Delay N Job 5 Machine," Prosiding SENTRA (Seminar Teknologi dan Rekayasa), vol. 2, pp. 19-23, 2017.

[2] S. Harto, A. K. Garside, and D. M. Utama, "Penjadwalan Produksi Menggunakan Algoritma Jadwal Non Delay Untuk Meminimalkan Makespan (studi kasus di CV. Bima Mebel)," Spektrum Industri, vol. 14, pp. 79-88, 2015. https://doi.org/10.12928/si.v14i1.3706.

[3] K. R. Baker and D. Trietsch, Principles of sequencing and scheduling: John Wiley & Sons, 2013.

[4] M. L. Pinedo, Scheduling: theory, algorithms, and systems: Springer, 2016.

[5] R. Ginting, "Penjadwalan Mesin," Yogyakarta: Graha Ilmu, 2009.

[6] D. M. Utama, "Algoritma LPT-Branch and Bound Pada Penjadwalan Flexible Flowshop untuk Meminimasi Makespan," PROZIMA (Productivity, Optimization and Manufacturing System Engineering), vol. 2, pp. 20-26, 2018.

[7] D. M. Utama, T. Baroto, D. Maharani, F. R. Jannah, and R. A. Octaria, "Algoritma ant-lion optimizer untuk meminimasi emisi karbon pada penjadwalan flow shop dependent sequence set-up," 2019, vol. 9, pp. 69-78, 2019-06-28 2019.

[8] D. M. Utama, A. K. Garside, and W. Wicaksono, "Pengembangan algoritma Hybrid Flow shop Three-Stage Dengan Mempertimbangkan Waktu Setup," Jurnal Ilmiah Teknik Industri, vol. 18, pp. 72-78, 2019. https://doi.org/10.23917/jiti.v18i1.7683.

[9] D. S. Widodo, "Pengembangan Cross Entropy-Genetic Algorithm (CEGA) Pada Penjadwalan Model Flow Shop Untuk Meminimalkan Makespan," TEKNOTERAP, vol. 1, pp. 1–11, 2017.

[10] D. M. Utama, "An Effective Hybrid Sine Cosine Algorithm to Minimize Carbon Emission on Flow-shop Scheduling Sequence Dependent Setup," 2019, vol. 20, pp. 62-72, 2019-02-26 2019. https://doi.org/10.22219/JTIUMM.Vol20.No1.62-72.

[11] D. M. Utama, D. S. Widodo, W. Wicaksono, and L. R. Ardiansyah, "A New Hybrid Metaheuristics Algorithm for Minimizing Energy Consumption in the Flow Shop Scheduling Problem," International Journal of Technology, vol. 10, pp. 320-331, 2019. https://doi.org/10.14716/ijtech.v10i2.2194.

[12] A. Firmansyah, D. Utomo, and M. Irawan, "Algoritma Genetika Ddengan Modifikasi Kromosom Untuk Penyelesaian Masalah Penjadwalan Flowshop," J. Sain dan Seni, vol. 1, 2016.

[13] A. K. Garside, D. M. Utama, and M. R. Arifin, "Penjadwalan produksi flowshop menggunakan algoritma branch and bound untuk meminimasi mean tardiness," 2018, vol. 3, pp. 1-6, 2018-08-11 2018.

[14] I. Masudin, D. M. Utama, and F. Susastro, "Penjadwalan Flowshop Menggunakan Algoritma Nawaz Enscore HAM," Jurnal Ilmiah Teknik Industri, 2014.

[15] D. M. Utama, "Pengembangan Algoritma NEH Dan CDS Untuk Meminimasi Consumption Energy Pada Penjadwalan Flow Shop," 2018, p. 8, 2019-01-10 2019.

[16] M. Husen, I. Masudin, and D. M. Utama, "Penjadwalan Job Shop Statik Dengan Metode Simulated Annealing Untuk Meminimasi Waktu Makespan," Spektrum Industri, vol. 13, 2015. https://doi.org/10.12928/si.v13i2.2689.

[17] M. Firdaus, I. Masudin, and D. M. Utama, "Penjadwalan Flowshop Dengan Menggunakan Simulated Annealing," Spektrum Industri, vol. 13, 2015. https://doi.org/10.12928/si.v13i1.1836.

[18] R. Nasution, A. K. Garside, and D. M. Utama, "Penjadwalan Job Shop Dengan Pendekatan Algoritma Artificial Immune System," Jurnal Teknik Industri, vol. 18, pp. 29-42, 2017. https://doi.org/10.22219/JTIUMM.Vol18.No1.29-42.

[19] Y. Li, W. Ip, and D. Wang, "Genetic algorithm approach to earliness and tardiness production scheduling and planning problem," International Journal of Production Economics, vol. 54, pp. 65-76, 1998. https://doi.org/10.1016/S0925-5273(97)00124-2.

[20] G. C. Onwubolu and M. Mutingi, "Genetic algorithm for minimizing tardiness in flow-shop scheduling," Production planning & control, vol. 10, pp. 462-471, 1999. https://doi.org/10.1080/095372899232993.

[21] L. Min and W. Cheng, "Genetic algorithms for the optimal common due date assignment and the optimal scheduling policy in parallel machine earliness/tardiness scheduling problems," Robotics and computer-integrated manufacturing, vol. 22, pp. 279-287, 2006. https://doi.org/10.1016/j.rcim.2004.12.005.

[22] A. Hamidinia, S. Khakabimamaghani, M. M. Mazdeh, and M. Jafari, "A genetic algorithm for minimizing total tardiness/earliness of weighted jobs in a batched delivery system," Computers & Industrial Engineering, vol. 62, pp. 29-38, 2012. https://doi.org/10.1016/j.cie.2011.08.014.

[23] O. Etiler, B. Toklu, M. Atak, and J. Wilson, "A genetic algorithm for flow shop scheduling problems," Journal of the Operational Research Society, vol. 55, pp. 830-835, 2004. https://doi.org/10.1057/palgrave.jors.2601766.

[24] R. Le Riche and R. T. Haftka, "Optimization of laminate stacking sequence for buckling load maximization by genetic algorithm," AIAA journal, vol. 31, pp. 951-956, 1993. https://doi.org/10.2514/3.11710.

[25] H. Gunawan, "Aplikasi Algoritma Genetik untuk Optimasi Masalah Penjadwalan Flow-Shop," IPB (Bogor Agricultural University), 2003.

[26] N. Saputro and Y. Yento, "Pemakaian Algoritma Genetik Untuk Penjadwalan Job Shop Dinamis Non Deterministik," Jurnal Teknik Industri, vol. 6, pp. 61-70, 2005.

[27] C. Yu, Q. Semeraro, and A. Matta, "A genetic algorithm for the hybrid flow shop scheduling with unrelated machines and machine eligibility," Computers & Operations Research, vol. 100, pp. 211-229, 2018. https://doi.org/10.1016/j.cor.2018.07.025.

[28] J. F. Gonçalves, J. J. de Magalhães Mendes, and M. G. Resende, "A hybrid genetic algorithm for the job shop scheduling problem," European journal of operational research, vol. 167, pp. 77-95, 2005. https://doi.org/10.1016/j.ejor.2004.03.012.

[29] P. K. Muhuri, A. Rauniyar, and R. Nath, "On arrival scheduling of real-time precedence constrained tasks on multi-processor systems using genetic algorithm," Future Generation Computer Systems, 2018. https://doi.org/10.1016/j.future.2018.10.013.

[30] P.-T. De Boer, D. P. Kroese, S. Mannor, and R. Y. Rubinstein, "A tutorial on the cross-entropy method," Annals of operations research, vol. 134, pp. 19-67, 2005. https://doi.org/10.1007/s10479-005-5724-z.

[31] M. Krisnawati, "Penyelesaian Permasalahan Penjadwalan Aktivitas Proyek dengan Batasan Sumber Daya Menggunakan Metode Cross Entropy," Dinamika Rekayasa, vol. 10, pp. 1-5, 2014.

[32] M. Caserta, E. Q. Rico, and A. M. Uribe, "A cross entropy algorithm for the Knapsack problem with setups," Computers & Operations Research, vol. 35, pp. 241-252, 2008. https://doi.org/10.1016/j.cor.2006.02.028.

[33] M. Caserta and E. Q. Rico, "A cross entropy-Lagrangean hybrid algorithm for the multi-item capacitated lot-sizing problem with setup times," Computers & Operations Research, vol. 36, pp. 530-548, 2009. https://doi.org/10.1016/j.cor.2007.10.014.

[34] J. L. Buliali, D. Herumurti, and G. Wiriapradja, "Penjadwalan Matakuliah dengan Menggunakan Algoritma Genetika dan Metode Constraint Satisfaction," JUTI: Jurnal Ilmiah Teknologi Informasi, vol. 7, pp. 29-38, 2008. https://doi.org/10.12962/j24068535.v7i1.a59.

[35] H. Bashori, "Upaya Meminimasi Makespan dengan Penerapan Algoritma Cross Entropy pada Penjadwalan Flow Shop," Widya Teknika, vol. 23, 2015.

[36] H. Bashori, P. Pratikto, and S. Sugiono, "Penjadwalan Flow Shop Dengan Penerapan Cross Entropy-Genetic Algorithm (Cega) Untuk Meminimasi Makespan," Journal of Engineering and Management in Industrial System, vol. 3, 2015. https://doi.org/10.21776/ub.jemis.2015.003.01.6.

[37] M. Budiman, "Pendekatan Cross Entropy-Genetic Algorithm Untuk Permasalahan Penjadwalan Job Shop Tanpa Waktu Tunggu Pada Banyak Mesin," Surabaya: Institut Teknologi Sepuluh Nopember, 2010.

[38] B. Santosa, M. A. Budiman, and S. E. Wiratno, "A Cross Entropy-Genetic Algorithm for m-Machines No-Wait Job-ShopScheduling Problem," Journal of Intelligent Learning Systems and Applications, vol. 3, p. 171, 2011. https://doi.org/10.4236/jilsa.2011.33018.

[39] L. Nurkhalida and B. Santosa, "Pendekatan Cross Entropy-Genetic Algorithm Pada Permasalahan Multi Objective Job Shop Scheduling," ed: UPT. Perpustakaan Institut Teknologi Sepuluh Nopember Surabaya, 2012.

[40] M. Hanka and B. Santosa, "Pengembangan Algoritma Hybrid Cross Entropy-Genetic Algorithm Pada Permasalahan Multiobjective Job Shop Scheduling Untuk Minimasi Makespan Dan Mean Flow Time," Tugas Akhir: Institut Teknologi Sepuluh Nopember, 2013.

[41] I. G. A. Widyadana and A. Pamungkas, "Perbandingan Kinerja Algoritma Genetika Dan Simulated Annealing Untuk Masalah Multiple Objective Pada Penjadwalan Flowshop," Jurnal Teknik Industri, vol. 4, pp. 26-35, 2004.

[42] N. Rahmawati and B. Santosa, "Penerapan Algoritma Hybrid Cross Entropy-Genetic Algorithm Dalam Penyelesaian Resource-Constrained Project Scheduling Problem," Prosiding SENIATI, vol. 3, pp. 37-1-5, 2017.

[43] D. S. Widodo, P. B. Santoso, and E. Siswanto, "Pendekatan Algoritma Cross Entropy-Genetic Algorithm Untuk Menurunkan Makespan Pada Penjadwalan Flow Shop," Journal of Engineering and Management in Industrial System, vol. .https://doi.org/10.21776/ub.jemis.2014.002.01.6

[44] S. S. Rao, T.-S. Pan, and V. B. Venkayya, "Optimal placement of actuators in actively controlled structures using genetic algorithms," AIAA journal, vol. 29, pp. 942-943, 1991. https://doi.org/10.2514/3.10683.

[45] P. D. Puspitasari and B. Santosa, "Penjadwalan Truk pada Sistem Cross Docking dengan Penyimpanan Sementara dengan Algoritma Hybrid Cross Entropy-Genetic Algorithm," Surabaya: Teknik Industri, Institut Teknologi Sepuluh Nopember, 2011.

PDF

Published

Oct 30, 2019

https://doi.org/10.25077/josi.v18.n2.p133-141.2019

How to Cite

[1]

D. M. Utama, L. R. Ardiansyah, and A. K. Garside, “Penjadwalan Flow Shop untuk Meminimasi Total Tardiness Menggunakan Algoritma Cross Entropy–Algoritma Genetika”, J. Optimasi Sist. Ind., vol. 18, no. 2, pp. 133–141, Oct. 2019.

Issue

Vol. 18 No. 2 (2019): Published in October 2019

Section

Articles

Authors' Retention of Copyright

Authors retain the copyright of their original work published in Jurnal Optimasi Sistem Industri (JOSI). By submitting their manuscript to the journal, authors grant Jurnal Optimasi Sistem Industri (JOSI) a non-exclusive license to publish the work under the CC BY-NC-SA 4.0 International License. This means that others are permitted to:

Share and adapt the work for non-commercial purposes, provided proper attribution is given to the original authors and source.
Create derivative works based on the original article, as long as the new work is non-commercial and under the same CC BY-NC-SA 4.0 International License.

Non-Commercial Usage

The CC BY-NC-SA 4.0 International License restricts commercial use of the published work and its derivatives. Commercial use includes generating revenue, financial gain, or any form of commercial exploitation. This limitation aims to preserve the scholarly and educational nature of the content.

ShareAlike Requirement

If you remix, adapt, or build upon the work, you must distribute your contributions under the same CC BY-NC-SA 4.0 International License as the original work. This "ShareAlike" requirement ensures that any new works based on the original content adhere to the same non-commercial, share-alike principles.

Usage, Attribution, and Citations

Authors and readers are allowed to:

Share and distribute the published article in any medium or format.
Adapt, remix, transform, and build upon the article for non-commercial purposes.
Provide appropriate attribution to the original authors and the journal.

When using content from Jurnal Optimasi Sistem Industri (JOSI), proper attribution must be provided through citation of the original source and authors.

Copyright Infringement and Ethical Considerations

If you believe that any material published in Jurnal Optimasi Sistem Industri (JOSI) infringes upon your copyright or the copyright of someone you represent, please contact the editorial team promptly. The journal is committed to addressing copyright concerns in accordance with established ethical guidelines set forth by the Committee on Publication Ethics (COPE).

For any questions or inquiries related to copyright and licensing, please contact the editorial team at editor_josi[at]eng.unand.ac.id.

Author Biographies