Application of Tabu Search Algorithm in Job Shop Scheduling

Authors

Betrianis Betrianis, Departemen Teknik Industri, Fakultas Teknik, Universitas Indonesia, Depok 16424, IndonesiaFollow
Putu Teguh Aryawan, Departemen Teknik Industri, Fakultas Teknik, Universitas Indonesia, Depok 16424, Indonesia

Abstract

Application of Tabu Search Algorithm in Job Shop Scheduling. Tabu Search is one of local search methods which is used to solve the combinatorial optimization problem. This method aimed is to make the searching process of the best solution in a complex combinatorial optimization problem(np hard), ex : job shop scheduling problem, became more effective, in a less computational time but with no guarantee to optimum solution.In this paper, tabu search is used to solve the job shop scheduling problem consists of 3 (three) cases, which is ordering package of September, October and November with objective of minimizing makespan (Cmax). For each ordering package, there is a combination for initial solution and tabu list length. These result then compared with 4 (four) other methods using basic dispatching rules such as Shortest Processing Time (SPT), Earliest Due Date (EDD), Most Work Remaining (MWKR) dan First Come First Served (FCFS). Scheduling used Tabu Search Algorithm is sensitive for variables changes and gives makespan shorter than scheduling used by other four methods.

Bahasa Abstract

Tabu Search merupakan salah satu metode pemecahan permasalahan optimasi kombinatorial yang tergabung ke dalam local search methods. Metode ini bertujuan untuk mengefektifkan proses pencarian solusi terbaik dari suatu permasalahan optimasi kombinatorial yang berskala besar (bersifat np-hard), contohnya permasalahan penjadwalan job shop, dengan waktu komputasi yang relatif lebih kecil, namun tanpa ada jaminan akan tercapainya solusi yang optimal. Dalam penelitian ini, Tabu search diterapkan pada sebuah permasalahan penjadwalan job shop dengan tujuan untuk meminimalkan waktu proses total atau makespan (Cmax). Penjadwalan menggunakan algoritma Tabu Search ini dilakukan terhadap tiga kasus, yaitu paket pesanan bulan September, Oktober dan Nopember, dimana untuk setiap paket pesanan dilakukan variasi terhadap initial solution dan panjang tabu list. Hasil penjadwalan ini kemudian dibandingkan dengan hasil penjadwalan lain yang menggunakan 4 macam metode basic dispatching rules , yaitu Shortest Processing Time (SPT), Earliest Due Date (EDD), Most Work Remaining (MWKR) dan First Come First Served (FCFS). Hasil pengolahan data menunjukkan bahwa penjadwalan yang menggunakan algoritma Tabu Search sensitif terhadap perubahan yang diberikan pada variabel yang ada didalamnya dan makespan yang dihasilkan secara keseluruhan lebih kecil apabila dibandingkan dengan hasil penjadwalan menggunakan ke-4 metode lainnya.

References

1. M. Pinedo, X. Chao, Operations Scheduling with Applications in Manufacturing and Services, McGraw-Hill, Singapore, 1999.
2. M. Laguna, J. Barnes, F. Glover, Journal of International Manufacturing 2 (1991) 63.
3. B. Yen, G. Wan, Proceedings of ICOTA (1998) 1191.
4. John B. Chambers, J. Wesley Barnes, ORSA Journal 106 (1998) 254.
5. I. Ahmad, M.K. Dhodhi, F. M. Ali, Computer Journal 43 (2000) 152.
6. Riswan, Skripsi Sarjana, Jurusan Teknik Mesin, Fakultas Teknik, Universitas Indonesia, Indonesia, 1993

Recommended Citation

Betrianis, Betrianis and Aryawan, Putu Teguh (2003) "Application of Tabu Search Algorithm in Job Shop Scheduling," Makara Journal of Technology: Vol. 7: Iss. 3, Article 5.
DOI: 10.7454/mst.v7i3.197
Available at: https://scholarhub.ui.ac.id/mjt/vol7/iss3/5