PaperlayerView exact revision on arXiv

Source-linked AI summary

Supply Chain Analytics: A Data-Driven Approach

Elioth Sanabria

arXiv:2609.10563v1math.OCcs.LGstat.ML

TL;DR

공급망 의사결정은 내재된 상충관계를 조정하는 동시에 수요의 불확실성과 변동성 전파를 고려해야 한다. 이 논문은 이러한 의사결정을 위한 data-driven 전략을 개발하고, Bullwhip effect가 공급망 네트워크의 피할 수 없는 위상적 속성임을 보인다.

  • 문제

    공급망 의사결정에는 내재된 상충관계가 존재하며, 수요는 불확실하고 음이 아닌 것으로 모델링해야 한다.

  • 방법

    이 논문은 공급망의 상충관계를 조정하기 위해 data-driven 전략을 사용하고 수요를 확률변수로 모델링한다.

  • 결과

    완전한 정보와 즉각적인 주문이 있더라도 Bullwhip effect는 공급망 네트워크의 피할 수 없고 내재된 위상적 속성이다.

  • 시사점 및 한계

    공급망 네트워크 의사결정은 변동성 전파를 내재된 네트워크 속성으로 고려해야 한다.

  • 시사점 및 한계

    이 논문은 공급망 의사결정의 내재된 조합적 성격을 궁극적인 병목으로 규정한다.

Abstract

from arXiv · show

Modern supply chain networks increasingly rely on real-time data to navigate structural uncertainties, market volatility, and operational disruptions. This manuscript bridges the gap between statistical data-driven learning and robust decision-making frameworks in logistics and operations management. We present a comprehensive, mathematically rigorous treatment of supply chain analytics, moving from empirical demand forecasting to optimal inventory and network control under uncertainty. Key topics explored include sample minimization, dynamic programming recursions for time-varying inventory replenishment, network fulfillment frameworks, and advanced distributionally robust optimization (DRO) via transport theory to hedge against rare events. By integrating predictive statistical models with prescriptive control algorithms, such as column generation for vehicle routing and non-homogeneous queueing regimes, this text provides the foundational tools necessary for designing resilient, data-driven automated systems. It serves as both a theoretical blueprint and an algorithmic guide for researchers and practitioners operating at the intersection of machine learning, mathematical optimization, and applied probability.

수요 추정 및 예측 … 1.3 시간에 따른 수요 변화

이 절에서는 확률적 기초에서 시간 의존적 확률모형에 이르기까지 수요 예측을 전개하며, 부가 정보, 분포적 상계, 시간 구조가 수요 추정을 어떻게 개선하는지 보인다. 또한 유연한 함수를 사용해 조건부 기댓값을 예측 대상으로 삼을 수 있지만, 유한 표본과 미지의 분포가 추정을 제약한다고 결론짓는다.

  • 1.1 서론: 수요는 알 수 없는 미래의 확률변수로 모형화되며, 실현된 수요는 발생한 뒤에만 관측된다.이 framework는 미래 수요를 나타내기 위해 확률변수를 사용하고, 가능한 결과를 정량화하기 위해 확률모형을 사용한다.
  • 1.2 확률변수로서의 수요: 음이 아닌 계수형 수요에서는 확률질량함수와 누적질량함수가 사건 확률을 뒷받침하며, 평균과 분산은 전형적인 수준과 산포를 요약한다.누적질량함수는 P(D ≤ i)를 제공하며, 구간 확률은 누적값의 차이로 계산할 수 있다.
  • 1.2.1 유용한 확률 계산: 평균 수요가 µD = 1 million units라는 정보만 있을 때, Markov 부등식은 수요가 5 million에 도달할 확률을 20%로 상계하며, 해당 임계값 미만일 확률이 적어도 80%임을 뜻한다.실제 초과 확률이 정확히 0일 수도 있으므로 이 상계는 느슨하다.
  • 1.2.1 유용한 확률 계산: 평균 µD = 1 million과 표준편차 σD = 100,000 units를 알고 있을 때, Chebyshev 부등식은 수요가 800,000–1,200,000 units 범위를 벗어날 확률을 25%, 5 million을 초과할 확률을 0.06%로 상계한다.같은 정보로 수요가 2 million을 초과할 확률도 1% 미만으로 상계할 수 있다.
  • 1.2.2 부가 정보: 경제 상황, 가격, 관련 제품, 날씨와 같은 부가 정보는 관측된 변수 X를 조건으로 수요를 추정함으로써 추정 성능을 높인다.제곱오차 손실하에서 X = x가 주어졌을 때 최적 예측자는 X = x가 주어졌을 때 수요의 조건부 기댓값이다.
  • 1.2.2 부가 정보: 수력발전 예제에서 P(X = 1) = 5%인 드문 더운 날과 조건부 수요 5Mw 및 15Mw는 평균 수요 µD = 5.5Mw를 산출한다.계산에는 E[D] = E[E[D|X]]가 사용된다.
  • 1.3 시간에 따른 수요 변화: 시간 의존적 수요는 Dt로 나타내는데, 시간 정보를 고려하지 않은 평균화가 오해를 낳을 수 있기 때문이다. 기본 모형은 절편, 시차 수요, 무작위 변동을 결합한다.시간 단위는 의사결정 맥락과 일치해야 하며, 과거 관측값은 추정에 사용할 실현 수요 데이터를 제공한다.

1.4 실제 수요 추정

수요 추정은 실제 수요분포와 관련 변수를 알 수 없는 상황에서 제한된 과거 관측값으로 조건부 기댓값을 근사하는 문제로 정식화된다. 이 절에서는 i.i.d. sampling에 대한 신뢰성 보장을 전개하고, nonstationarity가 단순 평균을 무효화할 수 있는 이유를 보이며, 수요모형을 표본 외에서 적합하고 평가하는 방법을 제안한다.

  • 실제 추정의 난점: 가능한 최선의 수요 예측은 관련 변수에서 얻은 정보를 조건으로 한 조건부 기댓값이지만, 실제로는 관측값이 제한적이고 수요를 유발하는 요인을 알 수 없거나 관측할 수 없는 경우가 많다.
  • 통계적 보장: 유한한 평균과 분산을 갖는 i.i.d. sampling에서는 대수의 법칙에 따라 표본평균이 실제 평균 수요로 수렴하며, 중심극한정리는 그 무작위성을 정량화한다.
  • 표본 크기 추정: σD = 30% of µD일 때 표본평균 수요가 95% 신뢰수준에서 실제 평균의 10% 이내가 되려면 34.5 years의 관측값이 필요하다.이 계산은 주어진 수요 변동성 가정하에서 중심극한정리를 사용한다.
  • 비정상 수요: drift가 있는 수요 과정에서는 µD(t) → ∞에 따라 표본평균이 발산하므로, 차분을 취하면 평균이 c이고 분산이 σ2인 stationary normal process가 된다.
  • 수요모형 적합: 실제 모델링 전략은 함수형을 설정하고, 최적화를 통해 그 매개변수를 보정한 뒤, 조건부 기댓값에 대한 근사로서 표본 외에서 이를 평가한다.근사의 품질은 함수형의 적절성과 과거 표본 크기에 모두 좌우된다.

재고 관리 모델 · 2.1 서론 · 2.2 Newsvendor 모델

이 절에서는 재고 관리를 과잉 할당에 따른 비용과 혼잡 및 판매 손실 사이의 균형 문제로 정식화한 뒤, 경험적 수요분포를 위한 Newsvendor 모델과 데이터 기반 보장을 전개한다. 가격, 비용, 수요 불확실성, 표본 크기를 바탕으로 최적 공급량을 도출하고, 재고와 이익에 대한 confidence bound를 포함한다.

  • 2.1 서론: 고정된 capacity, 자재 또는 노동력이 무작위 수요를 충족해야 할 때, 재고 의사결정은 비용이 큰 잉여 자원과 혼잡 및 판매 손실 사이의 균형을 맞춘다.이 절에서는 이 상충관계를 최적화하기 위한 데이터 기반 전략을 제시한다.
  • 2.2 Newsvendor 모델: Newsvendor 모델은 시점 0에 생산량 또는 재고량 q를 선택하여 horizon T에서 무작위 수요 D_T를 충족할 때의 기대이익을 maximize expected profit하도록 한다.매출은 p min(q, D_T)이고, 변동비는 qc이며, 고정비는 수량 결정에 영향을 주지 않는다.
  • 2.2 Newsvendor 모델: 최적 Newsvendor 수량은 critical ratio (p − c)/p에 대응하는 수요 분위수이며, concavity에 의해 critical point가 이익을 유일하게 최대화한다.critical ratio는 모델의 시각적 정식화에서 전체 수요를 충족할 확률을 나타낸다.
  • 2.2 Newsvendor 모델: 수요를 normal로 근사하면 최적 재고는 예측 수요에 inverse normal cdf와 가격–비용 비율로 결정되는 표준편차 buffer를 더한 값이다.p = 3c일 때 buffer는 예측 수요보다 σ의 약 43%만큼 높다.
  • 2.2 Newsvendor 모델: avocado 예제에서 고객당 lifetime profit ℓ을 $2,000으로 높이면 최적 수량은 q∗≈81.72 avocados로 증가한다.확장된 기대이익 정식화에는 구매, 준비, 폐기 및 고객 손실 비용이 포함된다.

2.3 재고 보충 - (s, S) rule

이 절에서는 (s, S) inventory policy를 stochastic process로 정식화하고 장기 비용을 도출하며, dynamic programming을 통해 i.i.d. demand에서 time-varying demand로 최적화를 확장한다.

  • (s, S) rule: 기말 재고가 s보다 낮아지면 (s, S) rule은 재고를 즉시 S까지 보충하며, 그렇지 않으면 demand가 현재 수준에서 재고를 감소시킨다.보충 간격은 random이며 demand에 따라 달라진다. 재고는 0보다 낮아질 수 있지만 S를 초과하지는 않는다.
  • (s, S) rule: i.i.d. demand에서는 inventory process가 Markov Chain이며, transition probabilities가 limiting distribution과 (s, S) rule의 장기 비용을 결정한다.stationary distribution은 πP = π를 풀어 수치적으로 계산하며, state space의 하한은 가능한 최대 demand M을 사용해 설정한다.
  • (s, S) rule: model에는 fixed replenishment cost K, per-unit ordering cost c, holding cost c_h, 그리고 inventory가 음수일 때 순수익 p̃의 lost-sales loss가 포함된다.이 구성요소들은 state-dependent cost function c(i)로 요약된다.
  • 최적 (s, S) policies 찾기: i.i.d. demand에서는 feasible (s, S) pairs를 열거하고 πP(s, S) = π를 풀면 구현이 쉬운 optimization routine을 얻을 수 있지만, 가장 효율적인 algorithm은 아니다.이 절차는 각 candidate pair에 대해 stationary distribution과 cost를 평가한 뒤 minimum cost policy를 반환한다.
  • Time-varying demand: time-varying demand에서는 dynamic programming이 inventory states와 actions에 대한 optimal expected cost를 재귀적으로 정의하며, horizon T 동안 expected cost를 최소화하도록 peak periods에 s_t와 S_t를 조정한다.inventory trajectories가 history-dependent이고 non-time-homogeneous이므로, 이 접근법은 terminal period에서부터 역방향으로 계산한다.

Network Fulfilment Models · 3.1 서론 · 3.2 창고 통합 및 입지

이 절에서는 공급망 분석의 초점을 시간에 따른 수요 대응에서 물리적 공간에 걸친 수요 충족으로 전환하며, 운송 지연과 네트워크 구조를 고려한다. 비용, 용량, 수요 불확실성, 위험의 균형을 유지하면서 계산 가능성을 확보하는 graph 기반 창고 입지 모델을 전개한다.

  • 3.1 서론: Network fulfilment model은 상당한 운송 지연을 고려하면서 생산자와 고객 사이에서 상품을 이동시켜 공간적 수요를 다룬다.이 절에서는 공간상에서 발생하는 일반적인 공급망 문제를 위한 알고리즘과 heuristic도 소개한다.
  • 3.2 창고 통합 및 입지: 창고 입지 문제는 물리적 공간을 graph로 표현하며, vertex는 위치를, edge는 위치 간 연결을 나타낸다.Graph 추상화는 계산 가능한 알고리즘을 가능하게 하지만 일부 정확도와 해상도를 희생한다. 경로는 명시적으로 표현하거나 단일 edge에서 평균화할 수 있다.
  • 3.2 창고 통합 및 입지: 공간 모델은 각 vertex에 random demand D_i를, 각 edge에 random travel time T_ij를 할당하여 정적 i.i.d. 일일 수요 정식을 구성한다.이 random quantity들은 고객 요구와 차량 이동 시간 모두의 불확실성을 포착한다.
  • 3.2.1 단일 위치 창고: 단일 창고 입지는 후보 위치를 열거하고 최소 기대 총비용을 선택하며, 창고 간접비와 수요 노드까지의 운송비를 결합한다.기대비용만으로 충분하지 않을 때는 수요와 이동 시간의 불확실성에서 발생하는 분산을 모델에 포함할 수 있다.
  • 3.2.1 단일 위치 창고: 위험을 고려한 창고 입지는 E(X)+λVar(X)를 최적화하여 위험회피 parameter λ를 비용 변동성에 대한 명시적 제어변수로 만든다.이 정식은 random demand와 random transportation time 모두로 인해 발생하는 분산에 불이익을 부여하며, λ는 실무적으로 calibration해야 한다.
  • 3.2.2 복수 위치 창고: 복수 창고는 배송비를 줄이고 규모의 경제를 활용하거나 물류 부담을 분산할 수 있지만, M개 위치 중 선택하면 2^M possible subsets가 생성된다.따라서 모델은 binary location variable과 선택된 창고를 수요 지점에 연결하는 flow variable을 사용한 Mixed Integer Programming을 적용한다.
  • 3.2.2 복수 위치 창고: 복수 위치 정식은 창고 용량과 수요 서비스 제약을 강제하며, chance constraint와 MIQP 또는 MISOCP 확장을 통해 불확실성과 위험을 반영한다.위험 고려 정식은 travel time과 demand가 서로 독립이라고 가정하고 λ를 통해 목적함수를 변화시킨다.
  • 3.2.2 복수 위치 창고: efficient frontier는 기대 운영비용과 비용 분산 사이의 trade-off를 보여주며, λ = 0은 위험 중립을 나타내고 더 큰 λ는 증가하는 위험회피를 의미한다.도식화된 곡선은 의사결정자가 위험 감소에 더 큰 가중치를 둘수록 입지 결정이 어떻게 변하는지 보여준다.

3.3 Distributionally Robust Warehouse Location Optimization

유한표본 수요 불확실성은 창고 입지 해를 크게 바꾸고, 표본 기반 최적화가 실제 기대 비용을 과소평가하게 만들 수 있다. Distributionally robust optimization은 경험적 분포에서 거리 δ 이내에 있는 분포들을 대상으로 최적화함으로써 이를 해결하며, 관측되지는 않았지만 개연성 있는 수요에 자원을 배분한다.

  • 유한표본 민감도: 수요 관측값, 기대값, 분산의 작은 변화가 입지 전반에 걸쳐 누적되면서 표본 기반 창고 해가 실제 최적해와 substantially different해질 수 있다.이 절은 제한적이거나 시간에 따라 변하는 관측값에 대한 민감도를 부각해 robustness의 필요성을 제시한다.
  • 유한표본 민감도: 95% 확률로 Hoeffding’s inequality는 표본 추정값을 중심으로 실제 기대 비용을 bounded하게 제한하며, 표본 기반 해가 비용을 과소평가할 가능성이 높고 N이 증가할수록 n에서 최소 quadratic growth가 필요함을 보인다.이 bound는 배송 비용을 수요 벡터의 bounded function으로 다루며 지리적 입지 수에 의해 발생하는 불확실성을 드러낸다.
  • Distributionally robust formulation: DRO는 알려지지 않은 실제 분포 P가 경험적 분포 P_n에서 distance-δ neighborhood 안에 있다고 모델링하며, δ는 risk aversion과 데이터에 대한 confidence에 따라 선택된다.더 큰 δ는 유한표본 추정값에 대한 신뢰가 낮음을, 더 작은 δ는 경험적 분포에 대한 신뢰가 높음을 반영한다.
  • 분포 불확실성하의 fulfillment: 경험적 접근과 달리 DRO는 개연성 있는 수요 공백에 probability mass를 분산하고, 관측되지 않았지만 잠재적으로 중요한 지역에 대해 positive allocations q_ij > 0을 강제한다.경험적 모델은 표본에 없는 지역에 q_ij = 0을 할당할 수 있지만, DRO는 더 넓은 distributional neighborhood를 통해 해당 지역을 고려한다.
  • 모델링 가정: 제안하는 DRO 처리는 수요 불확실성을 변화시키면서 duality theory와 optimal transport에 초점을 두고, 배송 비용 c_ij는 알려져 있으며 고정되어 있다고 가정한다.과거 수요는 n개의 관측 수요 벡터로 구성된 표본 행렬 D_n으로 표현된다.

Scheduling Models · 4.1 서론 · 4.2 Set covering 문제

Scheduling framework는 fulfillment를 time-space matching 문제로 모델링하며, deterministic set covering에서 시작해 불확실한 resource coverage로 확장한다. 이는 조합적 할당 문제를 포착하고 probabilistic scheduling 제약을 다루기 쉬운 conic program으로 변환한다.

  • 4.1 서론: Scheduling은 time-space matching problem으로 다루며, 공간 또는 discrete-time coverage에서 시작해 시간과 공간을 공동으로 모델링한다.이 framework는 최적화가 부적절할 경우 congestion, lost sales, resource 낭비를 초래할 수 있는 ordering decision을 다룬다.
  • 4.2 Set covering 문제: Set covering은 가용 resource를 사용해 location 또는 time period 전반의 demand를 나타내지만, 그 combinatorial structure 때문에 일반적으로 optimal solution을 찾기 어렵다.예로는 truck을 delivery에 할당하고 worker를 production task에 할당하는 경우가 있다.
  • 4.2 Set covering 문제: 기본 formulation은 demand vector D, schedule matrix A, feasible assignment vector x를 사용해 structural space-time demand를 cover하는 schedule을 선택한다.A의 dimension은 N ×J이며, schedule j가 task i를 cover할 때 aij = 1이다. x는 X = {0, 1}J와 같은 binary vector일 수 있다.
  • 4.2 Set covering 문제: 동일한 formulation으로 worker 수 또는 schedule cost를 minimize할 수 있으며, 동일한 비용이나 시간에 비례하는 비용을 사용하면 |x|를 minimize할 때와 same optimum을 얻는다.목적함수를 |x|로 대체하면 expected demand를 cover하는 minimum workforce를 찾을 수 있다.
  • 4.2.1 Data Uncertainty: Data uncertainty는 각 coverage row ai를 multivariate normal variable로 취급해 모델링하며, probabilistic constraint에 resource-allocation risk와 demand risk를 모두 반영한다.이 framework는 shift hour에 따른 productivity variation과 low-probability machine failure를 포괄한다.
  • 4.2.1 Data Uncertainty: 결과적으로 variance term xΣ_ix⊺가 nonlinear이므로, 불확실한 scheduling model은 Second-order Cone Program으로 재정식화하며 f(x)가 affine일 때 MISOCP solver로 푼다.Cholesky decomposition은 conic reformulation을 뒷받침하며, 그 feasible set은 Lorentz cone으로 나타낸다.

4.3 생산 스케줄링 · 4.4 배낭 문제

수요가 알려진 생산 스케줄링은 최적 경로가 생산 기간을 식별하는 최단 경로 문제로 환원되며, 배낭 문제는 탐욕적 선택이나 직접적인 mixed-integer optimization이 적절하지 않을 때 순방향 재귀 dynamic programming으로 해결된다. 배낭 재귀는 비감소 capacity consumption하에서 일반적인 편익을 처리하며 O(CN|X|) 연산을 수행한다.

  • 4.3 생산 스케줄링: 알려진 수요를 대상으로 한 생산 스케줄링은 수요를 정확히 충족하면서 생산 및 재고 보유 비용을 포함하는 결정론적 구간 비용 c(s, t)를 정의한다.모든 비용이 결정론적이고 계산 가능하다면 비용 명세는 달라질 수 있다.
  • 4.3 생산 스케줄링: 생산 재귀는 c(T + 1) = 0에서 시작해 미래의 최소 비용을 역방향으로 계산하며, 기간을 나타내는 노드와 c(s, t)를 가중치로 갖는 간선으로 구성된 그래프를 만든다.이 정식화는 한 구간을 담당하는 생산 의사결정이 완료된 뒤의 renewal structure에 의존한다.
  • 4.3 생산 스케줄링: 최적 생산 계획은 노드 0에서 T로 이어지는 최단 경로이며, 방문한 노드는 생산이 실행되는 기간을 식별한다.간선 가중치는 해당 기간의 setup, variable production, holding 비용을 나타낸다.
  • 4.4 배낭 문제: 배낭 문제는 capacity 제약하에서 객체의 편익을 최대화하며, 제한된 시간 내 작업을 선택하거나 예산 내 투자를 선택하는 응용을 포괄한다.각 객체는 편익 f_i(x_i)을 가지며, 음이 아닌 capacity c_i(x_i)를 소비하고, 수량 또는 indicator x_i ∈ X를 사용한다.
  • 4.4 배낭 문제: f_i(x_i)/c_i(x_i)에 따른 탐욕적 정렬은 최적 assortment를 산출하지 않을 수 있으며, f_i(x_i)가 비선형이면 직접적인 mixed-integer optimization을 적용할 수 없다.비선형 편익에는 할당량이 threshold를 넘을 때 총 순이익을 일시적으로 감소시키는 threshold penalty가 포함될 수 있다.
  • 4.4 배낭 문제: 순방향 재귀 dynamic programming은 처음 j개 객체와 capacity k를 사용했을 때의 최적 편익을 F_j(k)로 정의하고, 이를 predecessor state와 연결한다.재귀식은 객체 j의 편익과 잔여 capacity k − c_j(x_j)에서 처음 j − 1개 객체를 사용했을 때의 최적 편익을 비교한다.
  • 4.4 배낭 문제: 비감소 capacity c_i하에서 배낭 재귀는 O(CN|X|) 연산으로 F_j(k)를 순방향으로 채운다.결과 state space는 순차적 의사결정을 위한 stage와 남은 subproblem capacity를 위한 row로 구성되며, 각 cell은 직전 stage에서 가능한 최선의 전이를 평가한다.

차량 경로 문제 · 5.1 서론 · 5.2 Traveling Salesman Problem

이 장은 차량 경로 설정을 시간–공간 공급-수요 동시 매칭으로 정식화하며, 계산적 난이도와 해결 가능한 휴리스틱을 강조한다. TSP 정식화를 전개하고 subtour를 반복적으로 해소하며, 경로 설정을 확률적·위험 인지형 이동 비용으로 확장한다.

  • 5.1 서론: 차량 경로 설정은 공급과 수요를 맞추기 위해 시간과 공간을 할당하지만, 이러한 조합적 문제는 최적으로 풀기 어렵다.따라서 이 장은 이동 시간을 최소화하고 수요를 충족하면서 계산적으로 다루기 쉬운 시간 안에 실행 가능한 해를 산출하는 휴리스틱을 연구한다.
  • 5.2 Traveling Salesman Problem: TSP는 edge-selection 변수와 각 노드에 하나의 유입 edge와 유출 edge를 강제하는 제약을 사용해 모든 위치를 지나는 minimum-cost tour를 찾는다.정식화에서는 위치를 graph vertex로 나타내고 이동 비용 c_i,j를 할당하며, 전체 tour 비용을 최소화한다.
  • 5.2 Traveling Salesman Problem: 기본 할당 제약은 연결되지 않은 disconnected subtour를 만들 수 있으므로, 유효한 TSP 해에는 각 subtour를 외부 노드와 연결하는 추가 제약이 필요하다.Figure 5.2는 행·열 합 제약을 만족하는 두 개의 연결되지 않은 subtour를 묘사한다.
  • 5.2 Traveling Salesman Problem: 모든 subtour 제약은 지수적으로 많기 때문에, 실용적인 solver는 최적화 중 위반된 제약을 지연 방식으로 추가하며, 순차적 재해결은 비교적 빠르게 수렴한다.Dantzig-Fulkerson-Johnson 정식화는 가능한 모든 subtour에 대한 제약을 추가하지만, 현대 solver는 subtour가 나타날 때 이를 추가한다.
  • 5.2 Traveling Salesman Problem: subtour-connectivity 제약을 추가하면 연결되지 않은 할당이 모든 노드를 방문하는 최적 tour로 변환되며, 그 결과인 단일 연결 cycle로 이를 확인할 수 있다.필요한 제약은 v_sX(1 − v_s)^⊺ ≥ 1이다. Figure 5.3은 연결된 cycle 해를 보여준다.
  • 5.2.1 무작위성과 위험 인식 반영: 확률적 경로 모델은 운송 시간을 random cost로 취급하고, 이례적으로 긴 이동 시간에 대비하기 위해 분산을 반영한다.이는 엄격한 배송 시간 창과 위험 민감형 응용에서 비롯된다. 기대 시간이 더 짧더라도 분산이 클 수 있기 때문이다.
  • 5.2.1 무작위성과 위험 인식 반영: mean-variance 확장은 covariance 항을 통해 경로 비용의 분산에 페널티를 부여하면서, 동적으로 추가할 수 있는 subtour 제약은 유지한다.분산 항은 평탄화된 경로 벡터 x에 대해 xCov(c)x^⊺로 표현된다.

5.3 차량 라우팅 문제

차량 라우팅 정식화는 단일 외판원 문제를 K개 디포 기반 경로로 확장하고, subtour elimination을 통해 단절된 고객 섬을 처리한다. 차량 용량과 배송 시간창 같은 운영 제약은 하나의 비대한 정식화보다 반복적인 feasibility enforcement를 요구한다.

  • 다중 차량 정식화: VRP는 디포 노드 0과 정확히 K회의 출발 및 복귀를 추가하고 각 고객을 한 번씩 방문하도록 하여, 단일 자원 라우팅 정식화를 확장한다.결과 네트워크는 N + 1개 노드로 구성되며, 디포는 모든 차량의 공통 출발지이자 목적지 역할을 한다.
  • 운영 제약 모델링: 용량, 시간창 및 기타 제약을 결합한 단일 정식화는 선형계획 완화가 약한 경우가 많고 소규모 인스턴스를 넘어서는 순간 실패하는 경향이 있다.대안은 간결한 정식화에서 시작해 feasibility와 optimality에 도달할 때까지 제약을 추가하지만, 필요한 반복 횟수는 불확실하며 조합적 복잡성이 여전히 병목으로 남는다.
  • 용량 제약: 차량에 할당된 수요가 용량을 초과하면 용량 위반이 발생한다. subset cut은 누적 수요를 충족할 수 있도록 충분한 수의 출차 차량을 강제하며, lazy feasibility constraint를 사용한다.노드 부분집합 s_k에 대해 필요한 최소 차량 수는 m(s_k)=⌈Σ_i∈s_k E[D_i]/C⌉이며, CapacityUnfeasibility는 위반하는 고객 부분집합을 확인한다.
  • 시간창 제약: 시간창 제약은 경로 변수가 도착 시간을 추상화하기 때문에 어렵고, 단순한 위반 처리는 주로 투어의 순서만 바꾸는 느리고 약한 cut을 생성한다.신선식품과 같은 배송은 지정된 시간대를 요구할 수 있으며, 인용된 절차는 최종적으로 optimal solution을 보장한다.

연쇄 효과 · 6.1 서론 · 6.2 기본 모형

이 장에서는 수요 위험, 변동성, 리드타임이 공급망 네트워크를 통해 어떻게 전파되는지 정량화한다. 기본 모형은 Newsvendor 헤징과 네트워크 흐름 제약을 결합해, 용량 한계와 토폴로지가 품절 및 Bullwhip 위험을 증폭함을 보인다.

  • 6.1 서론: 이 장에서는 수요의 무작위성과 리드타임의 영향을 포함해 위험이 공급망 네트워크를 통해 어떻게 전파되고 상위 단계로 전달되는지 정량적으로 분석한다.이러한 효과를 확률적 네트워크 이론으로 형식화한다.
  • 6.2 기본 모형: 기본 모형은 노드 용량, 외부 수요, 라우팅 비율, Newsvendor 위험 버퍼를 사용해 최대 제품 흐름을 선형계획법으로 정식화한다.수요가 정규분포를 따를 때 각 노드의 버퍼는 수요의 표준편차와 critical-ratio factor z_i = Φ^-1(ρ_i)에 의존한다.
  • 6.2 기본 모형: 일부 노드는 용량이 제한되어 Newsvendor 위험을 최적으로 헤지하는 데 필요한 수량보다 적게 생산하므로, 무시할 수 없는 품절 가능성이 발생한다.나머지 노드는 외부 수요와 네트워크 구조가 허용하는 최대 수량을 생산한다.
  • 6.2.1 Bullwhip 효과와 기타 민감도: 수요 증가와 네트워크 구조는 함께 Bullwhip 효과를 유발하며, 외부 수요의 분산을 더 많은 내부 공급망 노드로 전파한다.민감도 분석은 네트워크 multiplier를 통해 수요와 변동성의 변화를 포착한다.
  • 6.2.1 Bullwhip 효과와 기타 민감도: 네트워크 multiplier matrix (I_H − P_H)^−1는 노드 간 생산 요구량과 위험 피드백이 어떻게 전달되는지를 나타내며, 각 원소는 노드 간 multiplier를 제공한다.substochastic matrix에서는 반복 피드백 항이 수렴하므로, 충격이 네트워크를 통해 전파될수록 더 깊은 노드에서 효과가 증폭될 수 있다.
  • 6.2.2 변동성 전파: 분산 전파에는 M_σ = (I − (P ⊙ P))^-1라는 두 번째 multiplier가 존재하며, 이는 외부 수요 표준편차에 대한 충격을 추가로 증폭한다.그 결과 발생하는 충격은 현재 표준편차에도 비례하므로 변동성 효과가 더욱 커진다.
  • 6.2.2 변동성 전파: 완전한 정보와 즉각적인 이행이 있더라도, 위험 헤징으로 인해 Bullwhip 효과는 공급망 네트워크의 본질적인 토폴로지 특성으로서 불가피하다.모형은 증폭의 원인을 정보, 조정, 예측 또는 리드타임의 부족만이 아니라 네트워크 구조에 귀속한다.
  • 6.2.2 변동성 전파: 두 노드 희토류 사례에서 수요 변동성이 1톤 증가하면 안전 수준 z_1 = z_2 = 1.645에서 생산자 산출량이 1.645톤 증가한다.생산자는 수요 변동에 대해 최적으로 헤지된 상태를 유지하려면 판매자의 수량보다 상당히 많이 생산해야 한다.

6.3 동적 모델

동적 모델은 Skorokhod 정식화를 통해 Bullwhip 및 기타 충격의 발생 시점과 크기를 포착하고, 장기적으로 정적 균형을 회복한다. 용량 제약으로 인해 hedged 및 un-hedged 노드 집합이 변화하며, 그 진화를 구간별 선형 방식으로 시뮬레이션한다.

  • 동적 모델: 이 모델은 Bullwhip effect와 기타 충격의 발생 시점과 크기를 분석하기 위해 네트워크를 동적 환경으로 확장한다.
  • 동적 모델: Skorokhod 구성은 경계 조절을 추가하여 음이 아닌 재고를 보장하며, 항 Yj(t)pji는 노드 간 부족분 전파를 추적한다.이 과정은 Z(t) = X(t) + Y(t)(I − P)를 만족하며, 재고가 0일 때 조절이 활성화되고 재고가 양수이면 비활성화된다.
  • 동적 모델: 장기적으로 동적 모델은 정적 생산량으로 수렴하며, 용량이 충분하면 limt→∞ λ(t) = q∗ 및 λ = α(I − P)^−1이 성립한다.균형 조건은 0 = θ = C(I − P) − α이며, 이에 따라 C = λ와 유효 생산률이 도출된다.
  • 동적 모델: 노드가 용량 한계에 도달하면 네트워크는 수요 증가에 따라 변화할 수 있는 서로소 hedged 및 un-hedged 집합으로 분할된다.시스템은 집합이 변경될 때까지 선형적으로 진화하며, 노드가 생산 한계에 도달하거나 의무를 더 이상 충족할 수 없게 되면 시뮬레이션을 재시작한다.

Queueing Models · 7.1 서론 · 7.2 큐잉 시스템의 네트워크 관점

이 장은 큐잉 시스템을 시간 의존적 운영의 확률 모형으로 소개하고, 평형 분석을 위한 연속시간 Markov chain 도구를 전개한다. 이어 이 도구를 처리량, 수익, 대기시간, 상호 연결된 큐에 적용한다.

  • 7.1 서론: 큐잉 모형은 작업 순서, 스테이션 구성, 가용 작업자가 생산 및 창고 운영의 처리량과 회복탄력성에 미치는 영향을 포착한다.이 장은 네트워크와 확률 이론을 사용해 일반적인 큐잉 문제를 기술한다.
  • 7.2 큐잉 시스템의 네트워크 관점: 큐잉 시스템은 유한 시스템 내 작업 수를 추적하며, 이는 각 상태에서 머무는 시간의 비율을 나타내는 시간 동질적 분포를 갖는 확률 과정으로 표현된다.상태 변수는 N = 0, 1, 2, . . . 이며 시간 동질적 시스템은 정상분포 분석을 지원한다.
  • 7.2 큐잉 시스템의 네트워크 관점: Continuous Time Markov Chains는 상태 간 전이확률과 시간 동질적인 평균 체류시간을 사용해 제조 공정을 모형화한다.전이행렬 P는 상태 i에서 상태 j로 이동할 확률 pij를 포함한다.
  • 7.2 큐잉 시스템의 네트워크 관점: 시간 동질성은 무기억 관계 R(t)R(s) = R(t + s)를 부과하며, 이로부터 이산시간에서는 기하학적 대기시간이, 연속시간에서는 지수 꼬리 R(t) = e^−µt가 도출된다.동일한 성질에 따라 짧은 구간에서 상태 i를 떠날 확률은 대략 µi∆t가 된다.
  • 7.2 큐잉 시스템의 네트워크 관점: qii = −µi 및 qij = pijµi를 갖는 생성행렬 Q는 전이행렬 P(t) = eQt를 제공하며 평형분포 계산을 가능하게 한다.평형 시스템을 풀면 pij를 따르고 상태 i에 지수시간 Ti 동안 머무는 체인에 대한 분포를 얻는다.
  • 7.2 큐잉 시스템의 네트워크 관점: 5개 스테이션의 선박 검사 예에서 birth-death 모형은 도착률 e−5p와 서비스율 min(i, 5)/2를 사용하며, 평형분포에서 수익은 pE(N)이다.이 모형은 선박 수로 상태를 정의하고 πQ = 0을 풀어 장기 수익을 구한다.
  • 7.2 큐잉 시스템의 네트워크 관점: Little’s law는 E(N) = E(a)E(W)를 명시하며, 도착률과 시스템 내 평균 개수로부터 기대 대기시간을 추론할 수 있게 한다.유도 과정은 시간 가중 점유율로 본 시스템 수익과 도착 선박의 처리시간으로 본 수익을 같게 둔다.

7.3 시간에 따라 변하는 도착

이 절에서는 도착률을 구간별 상수로 근사하고 시스템 내 예상 재고에 대한 과도상태 재귀식을 도출하여 대기열 분석을 시간에 따라 변하는 도착으로 확장한다. 도착 강도 대비 용량에 따라 대기열이 소진되거나 안정화되거나 지속 불가능하게 증가하는지가 결정됨을 보인다.

  • 구간별 상수 근사: 구간별 상수 도착률 r0과 r1은 시간에 따라 변하는 수요를 근사하며, 오차는 도착률 변화 지점 부근에 집중되고 처리 속도가 빠를수록 정확도가 높아진다.이 근사는 각 구간을 거의 동질적인 구간으로 취급하며, 느린 처리가 이전 작업을 시스템에 남겨 두는 경우에는 신뢰도가 낮아진다.
  • 용량 체계: 도착률 r1이 용량 kµ를 초과하면 대기열은 (r1 − kµ)t의 속도로 증가하며, r1 ≤ kµ이면 증가는 지속되지 않는다.r1 > kµ인 경우 서버가 작업을 충분히 빠르게 처리할 수 없지만, r1 ≤ kµ이면 용량이 누적의 지속을 막을 수 있다.
  • 용량 체계: k = 3000일 때 시스템은 선형 소진에서 833-customer equilibrium으로 전환한 뒤, 10am 급증 이후 지속 불가능한 선형 증가에 진입한다.이러한 교대 체계는 급증이 용량 경계를 넘을 때 발생한다.

대기행렬 시스템 최적화 · 8.1 서론 · 8.2 선형 할당

이 절은 대기행렬 최적화를 수요, 서비스 용량, 비즈니스 목표에 의해 좌우되는 자원 할당 문제로 설정한다. 다루기 쉬운 선형 할당 정식화를 전개하고, 이를 세차장 스케줄링으로 예시한 뒤, risk-aware mean-variance optimization으로 확장한다.

  • 8.1 서론: 대기행렬 최적화는 경제적 타당성을 유지하면서 수요와 서비스 수준 목표를 충족하도록 직원, 서버, 작업장 등의 자원을 할당한다.응용 사례로는 소매점 인력 배치, 온라인 서버 용량, 제조 작업장이 있다.
  • 8.2 선형 할당: 단일 서버 근사는 Little’s law를 사용해 도착률과 서비스율로 기대 대기시간을 표현하며, 안정성을 위해 E(a) < µ가 필요하다고 가정한다.이 근사는 µ에 대해 거의 선형이므로 서버율을 할당 자원 x와 연결할 수 있다.
  • 8.2 선형 할당: 선형 할당 모형은 서비스 기간 전반에서 수요가 처리 용량을 밑돌도록 하고 평균 대기시간을 사전 지정된 최대값으로 제한한다.목적함수 f(x)는 인건비 또는 더 정교한 운영 측정치를 나타낼 수 있다.
  • 8.2 선형 할당: 세차장 예제는 µAx⊺ ≥ E(A)를 대기행렬 안정성 제약으로 사용하면서 수요 충족을 조건으로 인건비와 운영비를 최소화한다.변동비는 각 인력 배치 구성에서 시스템 내 평균 고객 수에 따라 달라진다.
  • 8.2 선형 할당: 실현 가능한 값들에서 대기행렬 점유율을 추정하고 보조변수로 이를 선택하면, 조합적 인력 배치 공간에서 반복 시뮬레이션을 피하는 다루기 쉬운 MIP를 얻을 수 있다.이 정식화는 여전히 근사이며 변동비 구성요소를 선형화해야 한다.
  • 8.2 선형 할당: kµ의 속도를 갖는 하나의 mega-server는 k개의 개별 서버와 다르므로, 근사는 유휴 서버를 반영하기 위해 집계 속도를 kµη_k로 낮추며 η_k < 1이다.가능한 η_k는 원래 M/M/k 대기행렬에서 모든 서버가 가동 중일 확률에 기반해 설정할 수 있다.
  • 8.2.1 평균-분산 최적화: Risk-aware 할당은 M/M/1 사례와 같은 closed-form 분산식을 사용해 근사된 대기행렬 목적함수에 λVark(N(t))를 추가한다.승수 λ는 변동성에 부여하는 중요도를 조절한다.

8.3 정확도와 비지수 서비스 시간

이 절에서는 queueing 기반 dynamic programming을 지수 서비스 시간에서 비지수 서비스 시간으로 확장한다. 비기억성이 성립하지 않아 제어가 어려워지는 상황에서, QPLEX 는 전체 simulation이나 폭발적인 상태 추적 없이 전이 동학을 추정해 dynamic program을 다시 적용할 수 있게 한다.

  • 적용 범위: 이 framework는 대규모 computer service를 대상으로 하며, 수십만 건의 동시 요청이 합리적인 system time 안에 처리되도록 server를 할당하는 LLM providers를 포함한다.최적화는 평균 운영 비용과 낮은 확률의 service-time threshold 사이의 균형을 맞춘다.
  • 지수 서비스 시간 model: 지수 서비스 시간의 경우, model은 server 수와 이산화된 time에 대한 dynamic program을 사용하며, 전이는 기대 arrival rate와 queueing 동학에 의해 결정된다.loss function은 server cost c(k)와 congestion cost γ(N)을 결합하며, recursion은 k = 0, 1, …, K에 대해 반복된다.
  • 서비스 제약: service constraint P(W > s) ≤ α는 queueing delay가 threshold를 위반하는 dynamic-programming path를 pruning하여 강제한다.N > k이면, waiting time은 service rate kµ로 service에 진입하는 N − k명의 queued customer에서 유도한 뒤, 새로운 customer의 service를 rate µ로 처리하는 시간까지 반영한다.
  • 비지수 서비스 시간: 비지수 서비스 시간에서는 service가 더 이상 memoryless하지 않으므로 경과 또는 잔여 service time을 추적해야 하며, 이 때문에 control problem은 intractable해진다.reliability function은 일반적으로 time-homogeneity를 갖지 않으며, R(s)R(t) ≠ R(s + t)이다.
  • 비지수 서비스 시간: QPLEX 는 잔여 service와 system-size distribution을 추정하여, 전체 simulation이나 폭발적인 state space 없이 비지수 서비스 시간에 대한 dynamic programming을 가능하게 한다.conditioning을 통해 무작위로 선택된 job의 잔여 service time 분포 ν_t와 다음 단계 system distribution p_t를 추정한다.
Loading 2609.10563v1…