リエントラントフローショップスケジューリング問題に関する研究（第2報）: 発見的なスケジューリング手法の提案

摘要

Two new heuristic procedures for re-entrant flow shop scheduling problem are proposed to plan a feasible production schedule in industrial manufacturing factories. Each job is assigned to one of idle periods within a limited time on a cyclic Gantt chart. One heuristic procedure is for an assignment of a target job on the machine while an adequate the idle time is remained for undecided jobs. Another heuristic procedure is based on solutions for two classical optimization problems, or a job assignment problem and a knapsack problem. The starting time of the target job is optimally determined at each step in the scheduling. The results indicate that the proposed procedures give a good schedule in comparison with the optimal schedule derived theoretically. The Calculation times are also evaluated and verified a validity of the use in actual manufacturing factories.%リエントラントフローショップスケジューリングは，1rnつの製品の生産過程において，同一の生産装置を繰り返し使用rnする処理工程が必要になる生産計画に対して重要な役割を果たrnす．この生産スケジューリングが望まれる代表的な製品としrnて半導体があげられる．半導体の製造過程では，回路形成に対rnして同一の処理が繰り返し行われ。また装置が高額であることrnが，リエントラントな処理工程を避けることができない理由のrnひとつに考えられる．