주문형 생산 스케줄링을 위한 혼합 알고리즘

Abstract

주문자의 요구 사항을 기반으로 한 다품종 소량 생산 시장에서, 기계적인 사양의 만족과 주문한 제품의 납기 준수 여부는 매우 중요한 요소이다. 하지만 생산 품목의 종류와 수량이 매우 다양하고 제품의 종류에 따라 소요 시간이 달라지는 주문형 생산 시스템에서는, 주문의 완료 시간 및 납기일을 예측하기가 쉽지 않다. 또한 하나의 일정계획을 수립하기 위해서는 수많은 제약 조건들을 고려해야 한다. 현실의 제약 조건들은 작업 내 각 공정의 선행 및 후행 조건과 특정 작업에 대한 기계의 처리 가능 여부, 작업반 배치에 따른 소요 시간 변화 등이 존재한다. 이러한 제약 조건들은 문제를 복잡하게 만들어 빠른 시간 안에 최적의 스케줄을 찾기 어렵게 만든다. 실제 생산 현장에서는 새로운 주문의 추가와 같은 다양한 상황 변화에 따라 빠른 시간 안에 새로운 일정계획을 구해야 한다. 따라서 적당한 시간 내에 좋은 해를 찾는 효과적인 일정계획 알고리즘이 필요하다. 본 연구에서는 변압기 생산 사례를 통해 주문형 생산 문제를 정의하고, 효율적인 일정 계획을 수립하기 위한 유전알고리즘과 지역 탐색을 기반으로 한 알고리즘을 제안할 것이다. 또한 시뮬레이션 실험을 통해 다양한 상황 하에서 기존 일정계획 알고리즘들과 새로운 일정계획 알고리즘의 성능을 평가할 것이다.

The industrial transformer market has a characteristic of flow shop production system by specific requirements such as due date, voltage, and capacity. In this Make-to-Order production environment, on-time delivery has a major influence on the competitiveness of company. From the manufacturing factorys standpoint, it is also important to minimize the production cost like work-in-process inventory holding cost and transporting cost between stages by the due date that a company promised their clients. Therefore deriving a schedule to minimize both tardiness and production cost is essential for improving business competition. However the complexity of flow shop problem and a lot of constraints in the real world make it harder to solve these

problems within a reasonable time.

This paper presents a hybrid flow shop scheduling problem with real-world constraints, and develops a hybrid genetic algorithm for its solution. We first discuss the characteristics of the hybrid flow shop problem under the constraints of nighttime and simultaneous work. A hybrid genetic algorithm is then formulated to minimize the total tardiness. This algorithm incorporates both Nawaz– Enscore–Ham (NEH) and local search algorithms. The performance of our proposed approach with those of heuristic algorithms is compared. The results show that the proposed algorithm outperforms the NEH algorithm, a simple genetic algorithm, and five existing dispatching rules in terms of a total tardiness performance measures.