Two production scheduling models with concave costs are considered; backlogging case and lost-sales case.
There are constraints on production and inventory level in each period. The structure of the optimal schedule for backlogging case has been studied, while we extend it to lost-sales case. Efficient Backward dynamic programming algorithms are developed for both cases.
Both algorithms are also tested and appeared more favorable in comparison with others developed based on the so-called shortest-route network method.
본 논문에서는 주어진 기간에서의 생산계획을 정하는 문제를 다룬다. 각 기간에서의 수요는 알고 있으며 생산능력에는 매 기간마다 다른 최소한계와 최대한계가 주어져 있다. 본 논문에서는 첫째, 주문의 지연조달이 가능하지만 판매 손실을 허락하지 않는 경우를 다룬다. 첫째 경우에 있어서, 만일 지연조달이 일어나면 재고 수준은 음의 값을 갖는다. 어떤 기간에서의 재고수준은 양의 값을 갖는 최대한계와 o혹은 음의 값을 갖는 최저한계 사이에 있어야 한다. 생산비용함수는 양의 범위에서 오목함수의 형태를 취하며 재고-지연 조달비용함수는 양의 범위와 음의 범위 각각에서는 오목하지만 전 범위에서는 오목하지 않을 수도 있다. 둘째 경우에 있어서, 초기재고와 어떤 기간까지의 총 생산량의 합이 그 기간까지 필요한 주문량에 못 미치면 판매 손실이 일어난다. 첫째 경우에서와 마찬가지로 재고수준에는 최대한계가 있다. 생산함수비용과 재고비용함수는 양의 범위에서 오목하다. 첫번째 경우에 관하여 S.F.Love는 최적해가 갖는 성격에 관하여 분석하였다. 본 논문에서는 그 성격을 두번째 경우에 적용할 수 있게 연장한다. 또한 K.R.Baker등의 논문에서 말한 최적해의 지배성 (Dominance Property)을 일반화하여 두 경우 각각에 대해 효율적인 동적 계획 기법을 개발한다.