납기를 갖는 Job Shop일정계획의 효율적인 발견적기법 = An Efficient Heuristics Technique for Job Shop Scheduling with Due Dates

다국어 초록 (Multilingual Abstract)

This paper presents an efficient heuristic technique for minimizing the objectives related to tardiness such as total tardiness, maximum tardiness and root mean square of tardiness in the job shop scheduling. The heuristic technique iteratively improves an active schedule through exploring the schedule's neighborhood, using operation move methods. The move operation is defined on an active chain of tardy jobs in the active schedule. To find the move operations which have a high probability of reducing tardiness, we develop move methods by exploiting the properties of active chains. Our technique is compared with the two existing heuristic techniques, that is, MEHA(Modified Exchange Heuristic Algorithm) and GSP(Global Scheduling Procedure) under the various environments with the three levels of due date tightness and several sized problems. The experimental results show that the proposed technique outperforms the two existing techniques in terms of solution quality and computation time.