- Job Shop 일정계획을 위한 Tabu Search
- ㆍ 저자명
- 김여근,배상윤,이덕성,Kim. Yeo-Keun,Bae. Sang-Yun,Lee. Deog-Seong
- ㆍ 간행물명
- 대한산업공학회지
- ㆍ 권/호정보
- 1995년|21권 3호|pp.409-428 (20 pages)
- ㆍ 발행정보
- 대한산업공학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
Job shop scheduling with m different machines and n different jobs is a NP-hard problem of combinatorial optimization. The purpose of the paper is to develop the heuristic method using tabu search for job shop scheduling to minimize makespan or mean flowtime. To apply tabu search to job shop scheduling problem, in this paper we propose the several move methods that employ insert moves in order to generate the neighbor solutions, and present the efficient rescheduling procedure that yields active schedule for a changed operation sequence by a move of operations. We also discuss the tabu search techniques of diversifying the search of solution space as well as the simple tabu search. By experiments, we find the appropriate tabu list size and tabu attributes, and analyze the proposed tabu search techniques with respect to the quality of solutions and the efforts of computation. The experimental results show that the proposed tabu search techniques using long-term memory function have the ability to search a good solution, and are more efficient in the mean flowtime minimization problem than in the makespan minimization.