다품목 화공처리 라인의 실시간 단일 호이스트 일정계획

Abstract

This thesis deals with a single-hoist scheduling problems for a multistage production line in which a computer-controlled hoist system performs the transportation of parts between stages. The production line consists of a series of tanks filled with a variety of chemical solutions for surface processing of the metal parts, and the processing of parts is compiled by soaking them into tanks for a certain time and in particular order. Because the system produces various items, there are distinct soaking sequences for the diverse items produced on the line. Although some MILP (mixed integer linear programming) models for the single-hoist and multiple-products scheduling problem were developed earlier, the production line that motivated this study has a special feature that was not considered in the earlier studies. The company produces parts for assembling an aircraft and an order from customer consists of a set of parts. In order that the set is transported by the hoist and soaked in a tank all together, a tool for installing parts, that is called a rack, is needed. In order to insert a new job into the tank line, an empty rack is needed. When the process of a job is finished, the parts that were installed on the rack are released, and the empty rack can be used to install a new job. In this thesis a new MILP model that considers this rack condition is proposed. Applying the model to a commercial optimization software, the optimal solutions for relatively small problems can be found in very short times. For the case of realistic industry size problems, however, the MILP model cannot find an optimal solution in a reasonable computation time. To solve such problems this thesis developed a branch and bound based heuristic algorithm, in which the number of branches from a node is variable with the problem size. For a very big problem, for example, the number of branches from a node is restricted to just one, while it can be two or more for the small problems. To evaluate the performance of the heuristic algorithm, the biggest problems that can be solved by the MILP model are generated and used for comparing the results of the heuristic algorithms to optimal solutions. The comparison showed that the heuristic has very good performance and the computation time is sufficiently short to use the algorithm in real situation.

Keyword : Hoist, Scheduling, Heuristic. Branch-and-bound