An Optimization Approach for Job Shop Planning and Scheduling

DOI Web Site 7 References

Bibliographic Information

Other Title
  • ジョブショップの生産計画とスケジューリングに対する最適化アプローチ
  • ジョブショップ ノ セイサン ケイカク ト スケジューリング ニ タイスル サイテキカ アプローチ

Search this article

Abstract

This paper proposes an optimization approach for the production planning and scheduling of a job shop. Production planning must satisfy the forecasted demand with minimum production cost, while scheduling is responsible for generating the detailed allocation of operations among machines based on the given production plan. In general, the planning phase of the job shop cannot utilize the maximum production time because the scheduling phase often requires some unavoidable idle time in order to satisfy the precedence constraint of operations. In addition, the scheduling problem is determined after the production plan is frozen. As it is difficult to formulate and solve an entire planning and scheduling model, our approach solves the planning and scheduling problems iteratively. A Lagrangean relaxation method is adopted to solve the production planning problem formulated as a mixed-integer program. In the scheduling phase, the record of schedules obtained before is first utilized in order to reduce the computational workload, and if no record is available or no feasible solution is obtained, the scheduling problem is solved by a branch and bound method to minimize the makespan. If the makespan of the optimal schedule is greater than the available production time, a new capacity constraint to the planning problem is generated and the enlarged production planning problem is solved again. The generated constraint requests that the sum of processing time of operations belonging to the critical path must be equal to or less than the available production time. When the scheduling phase finds a feasible schedule, a feasible production plan and its detailed production schedule are obtained. Computational experiments have shown that the proposed approach can find feasible solutions with a relatively small number of added constraints, and the degree of minimization of makespan may affect the quality of the proposed approach in terms of both finding feasible solutions and obtaining lower cost solutions.

Journal

References(7)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top