제품조달시간을 고려한 주문처리 일정계획에 관한 연구

Order Scheduling with Product Available Time Constraint

  본 연구는 주문일정계획문제에서 주문에 포함된 일부제품이 자체 생산되지 않고 외부의 협력업체를 통해 조달되는 경우를 고려하고 있다. 각 주문은 자체생산제품과 외부조달제품으로 구성되고, 자체생산제품에 대해서는 독자적인 생산일정계획이 필요하지만, 외부조달제품의 경우에는 외부에서 생산되며 제품의 도착시점이 바로 조달제품의 생산완료시점이 되는 것이다. 따라서 각 주문이 충족되는 시점은 각 주문에 포함된 모든 제품을 생산 및 조달하여 모두 완비되는 최초시점으로 모델링 된다. 본 연구는 이러한 상황에서 모든 고객주문을 충족시키는데 소요되는 총 가중완료시간(total weighted completion time)을 최소화하기 위한 생산일정계획문제를 다루고 있다. 문제의 분석에서 작업간의 우선순위관계를 규명할 수 있는 우월성질이 제시되고, 이를 바탕으로 분지한계법과 그리디 형태의 휴리스틱을 제안한다. 제안된 우월성질, 휴리스틱, 분지한계법의 성능은 다양한 수치데이터를 활용한 실험을 통해 평가된다.

  This paper considers a scheduling problem to meet some orders from customers. Each order is composed of two types of products. One product is manufactured by a single facility under make-to-order environment, the other product is supplied from the outside facility(or, contractor), so given as an available time data. The completion time of each order is measured by the time when both of the corresponding products are completed(or, available). The problem is to obtain the optimal sequence of orders to minimize the total weighted completion time. In the problem analysis, we first derive a powerful property to determine the sequence of two consecutive orders. And then, two lower bounds of objective are derived and tested along with the derived property within a branch-and-boundscheme. An efficient heuristic algorithm based on a greedy manner is also developed. The overall performance of the proposed property, branchand-bound and heuristic is evaluated through numerical experiments.