Multiple Exchanges of Job Orders for No-Buffer Job Shop Scheduling Problem

Abstract

This paper describes a procedure for local modifications of a job shop schedule planned under a no-buffer constraint. The modifications are to correct the infeasibility caused by exchanging two consecutive operations on the same machine. An extended disjunctive graph, which has reverse conjunctive arcs connecting two consecutive processes, is introduced to identify the operations preventing the feasibility of such a schedule. By exchanging the operating order of these operations, the obtained infeasible schedule can be corrected to a feasible schedule. An example of the modifications for a given job shop schedule is shown to discuss the advantages of the proposed procedure.

Keywords

• job shop schedule
• no-buffer
• local search
• disjunctive graph