Optimization problem for feasibility evaluation of schedules considering blocking

Abstract

In the present paper, the job shop scheduling problem with no intermediate buffers, i.e. the blocking job shop scheduling problem, is investigated. Since there are no buffers between operating machines, the machines are blocked by the products that the machines operated until those products are passed to the products’ downstream machines. Under the condition where blocking is considered, complicated calculations must be performed to evaluate semi-active schedules when a partial change of a schedule, or exchange of an operation order of jobs on a specific machine, is planned. Furthermore, because some or most of the partial changes result in infeasible schedules, it will be an advantage to know the feasibility of the changes before the time adjustments for the semiactive schedule. To deal with the feasibility problem, a new optimization problem using an artificial variable is proposed for the feasibility evaluation of a partial change of a schedule. The proposed method utilizes the mixed integer programming problem of the blocking job shop scheduling problem, with the integer variables given so that the problem becomes a simple linear programming problem solved by the simplex method. By using the information before the change of the schedule, namely the basic variables and the deformed constraints, the optimization is performed efficiently beginning at a close solution of the present evaluation. Moreover, the semi-active schedules are determined within a few steps after the evaluation, which eliminates the calculation of determining the schedule separately. To demonstrate the behavior of the proposed method, examples of calculation procedures are described in a precise manner. In addition, numerical examples are shown to verify the advantages of the proposed evaluation method.

Keywords

• buffer
• blocking
• scheduling problem
• semi-active schedule
• feasibility
• two-phase method
• artificial variable
• simplex method