An efficient heuristic technique for job shop scheduling with due dates

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, the paper developes move methods by exploiting the properties of active chains. The present tecchnique is compared with the two heuristic techniques, that is, MEHA (Modified Exchange Heuristic Algorighm) 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 outperfroms the two existing techniques in terms of solution quality and computation time. [In Korean.]