용량 제약 다항목 배치 문제를 위한 라그랑주 이완

용량 제약 다항목 배치 문제(CLS)은 주어진 유한 기간의 계획 수립에서 각 기간의 제품 수요와 자원 한계를 충족하는 제품의 배치 크기를 결정하고, 생산, 재고 보유 및 설정 비용으로 구성된 총 비용을 최소화하는 문제입니다. CLS는 산업 생산 환경에서 종종 발생하며 NP-하드로 간주됩니다. 본 논문에서는 이러한 문제를 해결하기 위한 라그랑주 이완(LR) 접근법을 제안합니다. 이 접근법은 용량 제약을 목적 함수로 이완하여 CLS를 여러 개의 비용량 단일 항목 문제로 분해하고, 각 문제는 동적 프로그래밍으로 쉽게 해결할 수 있습니다. 유효한 솔루션은 결과적으로 나타나는 수송 문제와 수정 휴리스틱을 해결하여 얻어집니다. 이완된 문제의 라그랑주 승수는 부분 기울기 최적화를 사용하여 업데이트됩니다. 실험 결과는 LR 접근법이 고품질 솔루션을 탐색하고 문헌에서 일반적으로 사용되는 다른 솔루션 접근법에 비해 더 나은 적용 가능성을 가지고 있음을 보여줍니다.