In this research, the single machine capacitated lot-sizing and scheduling problem with sequence-dependent setup costs and setup times (CLSPSD) is considered. This problem is an extension of capacitated lot-sizing and scheduling problem (CLSP) with an additional assumption of sequence-dependent setup costs and setup times. The objective of the problem is minimizing the sum of production costs, inventory holding costs and setup costs while satisfying the customer demands.
It is known that CLSPSD is NP-hard. In this paper, a MIP formulation is presented. To handle the problem more efficiently, a conceptual model is suggested, and one of the well-known meta-heuristics, simulated annealing approach is applied. To illustrate the performance of this approach, various instances are tested and the results of this algorithm are compared with those of CLPEX. Computational results show that the approach generates optimal or near optimal solutions.
본 논문은 생산 순서에 영향을 받는 준비 시간과 준비 비용을 고려한 용량제약이 있는 로트사이징 문제의 해법을 다루었다. 이 문제는 용량제약이 있는 로트사이징과 스케쥴링 문제에 생산 순서에 영향을 받는 준비시간과 준비 비용의 제약을 추가 한 것이다. 이때 준비 시간과 준비 비용이 생산 순서에 영향을 받는다는 것은 현재 제품을 생산하기에 앞서 어떤 제품이 생산 되었느냐에 따라 현재 제품을 생산하기 위한 준비 시간과 준비 비용이 각각 달라진다는 것을 의미한다. 본 연구의 목적은 고객의 수요를 만족시키면서 비용을 최소로 하는 생산계획을 세우는 것이다.
생산 순서에 영향을 받는 준비 시간과 준비 비용을 고려한 용량제약이 있는 로트사이징 문제는 NP-hard임이 알려져 있다. 본 논문에서는 위 문제를 혼합 정수계획문제로 모형화 하고, 시뮬레이티드 어닐링 알고리즘을 사용하여 문제를 해결하였다. 이때 문제를 생산량 결정과 생산 순서 결정으로 분리하여 다루었다. 또한 생산 순서를 좀더 효율적으로 결정하기 위해 개념적인 네트워크 모형을 제시하였다. 실험 결과 본 논문에서 제시한 알고리즘은 최적해 또는 최적에 가까운 해를 빠른 시간 안에 구해주었다. 또한 앞선 연구에서 제시된 휴리스틱 알고리즘을 통한 해와 비교해 봤을 때 해의 개선이 있음을 알 수 있었다.
