Contents I. Introduction
Job shop scheduling (JSP) is usually a strongly NP complete problem of combinatorial optimization problems and is the most typical one of the production scheduling problems[1], [2], Unfortunately, most publication in shop scheduling area focuses on the static shop scheduling. Very few of them suggest a comprehensive model and solution to the dynamically job shop problem[3], [4]. To deal with dynamic scheduling, most researches usually partition the scheduling process into two phases. In Phase 1, they consider the optimization of makespan under idealized conditions; then in Phase 2, they simply deal with reactive scheduling based on some scheduling rules, in case of accidental disturbance. Muhleman et al analyzed the periodic scheduling policy in a dynamic and stochastic job shop system. Their experiments indicated that more frequent revision was needed to obtain better scheduling performance[5]. Church and Uzsoy considered periodic and event-driven rescheduling approaches in a single machine production system with dynamic job arrivals. Their result indicated that the performance of periodic scheduling deteriorate as the length of rescheduling period increased and event-driven methods achieved a reasonably good performance[6]. Subramaniam et al demonstrated that significant improvements to the performance of dispatching in a dynamic job shop could be achieved easily through the use of simple machine selection rules[7]. SQ. Liu et al presented a framework to model dynamic shop scheduling problem. Using the proposed framework, a metaheuristic was proposed to solve dynamic shop problem. The result showed that the metaheuristic methodology which had been applied to solve dynamic shop scheduling problem efficiently[8], Borstjan and Peter proposed an alternative way to avoid infeasibility by incorporating a repairing technique into the mechanism for applying moves to a schedule. Whenever an infeasible move was being applied, a repairing mechanism rearranged the underlying schedule in such a way that the feasibility of the move was restored. The possibility of reaching infeasible solutions was, therefore, eliminated on the lowest possible conceptual level[9]. Hiroshi and Toshihiro considered the job shop scheduling problem of minimizing the total holding cost of completed and in-process products subject to no tardy jobs. A heuristic algorithm based on the shifting bottleneck procedure was proposed for solving the minimum total holding cost problem subject to no tardy jobs. Several benchmark problems which were commonly used for job-shop scheduling problems of minimizing the makespan were solved by the proposed method and the results were reported[10]
