Vol 7, No 3 (2003) > Articles >

Application of Tabu Search Algorithm in Job Shop Scheduling

Betrianis Betrianis 1 , Putu Teguh Aryawan 1

Affiliations:

  1. Departemen Teknik Industri, Fakultas Teknik, Universitas Indonesia, Depok 16424, Indonesia

 

Abstract: 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.
Keywords: scheduling, tabu search, job shop, makespan
Published at: Vol 7, No 3 (2003) pages: 107-112
DOI:

Access Counter: 2681 views, 3249 PDF downloads, .

Full PDF Download

References:

M. Pinedo, X. Chao, Operations Scheduling with Applications in Manufacturing and Services, McGraw-Hill, Singapore, 1999.

M. Laguna, J. Barnes, F. Glover, Journal of International Manufacturing 2 (1991) 63.

B. Yen, G. Wan, Proceedings of ICOTA (1998) 1191.

John B. Chambers, J. Wesley Barnes, ORSA Journal 106 (1998) 254.

I. Ahmad, M.K. Dhodhi, F. M. Ali, Computer Journal 43 (2000) 152.

Riswan, Skripsi Sarjana, Jurusan Teknik Mesin, Fakultas Teknik, Universitas Indonesia, Indonesia, 1993