SMS

인트로

• 계층적 플래닝의 원칙 5개
  deecompoisiton and hierarchical structure
  coordination : communication between planning units
  aggregation : 집계
  modell building, anticipation and disagrregation
  model solving

• 스케줄링의 정의와 스케줄링 문제예시
  allocation of linited recourses to activities
  optimize its objectives and consider relevant limitations and constraints

• 엑티비티와 리소스

lateness 는 마이너스 가능
tardiness는 최소 0

2. Job Shop Scheduling

Job Shop Scheduling

다양한 작업(Job)들이 있고, 각 작업은 여러 공정(Operation)으로 구성되어 있으며, 각각의 공정은 특정한 기계(Machine)에서 정해진 순서로 수행되어야 하는 스케줄링 문제

• 뒤 알파벳이 잡. 앞에가 머신
• 1~5까지 제약조건 별로 몇개 조건이 필요한지 세기 -> 변수 보고 생각하기.
  disjunction constraint의 수는 "자원(머신)을 공유하는 작업들 사이에 설정해야 하는 쌍(pair) 수"를 의미

• 3) Disjunctive constraints : 이 부분이 비결합(disjunctive) 조건이며, 보통 MILP에서는 이 OR을 이진 변수 x를 도입해서 linearize:
  
  x : if job j is done before job k on machine i -- 1 or 0
  x가 1이면 엄청 큰 수 빼기 -> j가 먼저

Simplified shifting bottleneck heuristic (SSBH)

Job Shop Scheduling 문제에서 널리 쓰이는 휴리스틱(heuristic) 알고리즘
잡샵 문제는 NP-hard 라서 이걸로 풀기.
⚙️ "가장 혼잡한 자원(= bottleneck machine)을 하나씩 해결해가며 전체 스케줄을 구성"하는 방식입니다.
왜 "Shifting Bottleneck"인가?
Bottleneck: 현재 makespan에 가장 큰 영향을 주는 머신 (가장 많이 쓰이거나, 지연이 큰 자원)
Shifting: 한 머신의 스케줄을 고정하면 병목이 다른 머신으로 옮겨가기 때문
→ 그래서 병목을 "shifting"해가며 해결함

• 절차

초기화:
각 job의 작업 순서는 주어졌지만, 각 머신의 순서는 아직 미정
각 머신에 대해 단일 머신 문제를 풀어: 그 머신만 고려했을 때의 최적 makespan을 계산

가장 병목이 심한 머신을 선택: 예: 가장 높은 makespan을 유발하는 머신 Lmax

해당 머신의 작업 순서를 고정 -- freeze the seq

전체 스케줄을 다시 평가

아직 순서가 정해지지 않은 머신에 대해 다시 2~5 반복

• 예시문제 풀기 --> 그래프 그릴 수 있어야 해.

---

3-a. Sequenceing in paced assembly lines

Paced Assembly Line Scheduling

• paced assembly line:
  제품은 라인의 각 스테이션(작업장)을 일정한 시간 간격(pacing)으로 통과합니다.
  각 스테이션은 그 시간 안에 맡은 작업을 끝내야 합니다.
  작업 순서를 어떻게 정하느냐에 따라 효율성과 비용이 크게 달라짐.
  

• involves organizing the order of production tasks to optimize efficiency and productivity

Base Model

Extensions

• workload oriented appr.
  • 믹스드 모델 시퀀싱 : 서로다른 제품 모델 같은 조립라인에서 번갈아 생산시 생산순서 최적화. 명시적 워크로드 줄이기. 에포트 크지만 정확성도 큼.
  • 카 시퀀싱 : 자동차 제조에서 특정 옵션의 설치 능력이 제한된 작업 관련.. 암묵적 워크로드 줄이기. Surrogate (대리, 대행)

• JIT-oriented appr. -- just in time

  	- 레벨 스케줄링 : 일정기간동안 제품수요 평균화. 매일 비슷한 비율로 모델 생산.  제고 최소화
  	

Mixed-model sequencing

deals with the sequencing of different product models on the same assembly line.
It aims to minimize setup times and balance workloads across the line, allowing for efficient production of various models without significant downtime.

Car Sequencing

Car sequencing is a specialized type of sequencing used in automotive manufacturing. It focuses on organizing the production of different car models in a way that meets specific constraints, such as color and feature options, while optimizing the flow of production.

• 12번 제약식 왜 필요하냐?? 윈도우에서 중복으로 세어지니까. 제일 앞에꺼만 세자!

Level Scheduling

Level scheduling involves maintaining a consistent production rate across the assembly line, regardless of variations in demand or product complexity. This extension is crucial for managing inventory levels and ensuring that production remains stable and predictable.

3b Robust Car Sequencing

위의 Car Sequencing 문제에 ‘불확실성(uncertainty)’을 도입한 확장 모델: Robust Car Sequencing은 전통적인 Paced Assembly Line의 Car Sequencing 문제를 기반으로 하되, 불확실성(예: 차량 순서 변경, 수요 변화 등)이 존재하는 상황에서도 성능 저하가 최소화되도록 설계된 시퀀스를 찾는 것이 목표

Exact branch-and-bound algorithm

조합 최적화 문제(예: scheduling, TSP, MILP 등)에서 전역 최적해를 보장하면서도, 불필요한 해 탐색을 피하는 스마트한 방식
"전체 해 공간을 분할하고 잘라내면서 (branch-and-bound) 최적해를 정확히 찾는 알고리즘"

• Root 노드: 원래 문제 전체
• 분기(branching): 결정을 하나씩 고정하면서 하위 문제를 생성
• 경계(bounding): 그 하위 문제의 낙관적 해(lower bound) 계산
• 가지치기(pruning):
• 최적해보다 더 나쁜 bound → 해당 분기 탐색 안 함
• 해가 정수 조건 만족 안 하면 계속 분기
  최적해가 보장될 때까지 반복

• challenges for large sequences -> 1. Sampling approach 2. Adaptive large neighborhood search:

• Robust Car Sequencing Heuristic

  전통적인 car sequencing 문제에 불확실성(robustness) 요소를 반영해서, 실용적으로(빠르게) 좋은 시퀀스를 찾기 위한 근사 알고리즘(heuristic)
  

• Adaptive Large Neighborhood Search (ALNS)

  복잡한 최적화 문제를 빠르게 그리고 유연하게 푸는 메타휴리스틱 알고리즘입니다.
  "해를 크게 바꾸는 neighborhood 연산자들을 여러 개 조합해 사용하면서, 성능 좋은 연산자에 더 집중하도록 학습해나가는 방법"

• 이론적인 내용
• 바운드 고려해서 B&B tree search 트리써치 하기 --> Best-first search strategy:
  • We choose the node with the lowest lower bound for further extension. If there is a tie, we choose the node with the greater depth in the tree.
• 휴리스틱들 내용, 장점, 특징 등

---

4a - Lot Sizing 1 - Lot-sizing & scheduling (Single stage systems)

• lot sizing 배경

구분	로트사이징 (Lot Sizing)	스케줄링 (Scheduling)
목적	얼마나 생산할지 결정	언제, 어떤 순서로 생산할지 결정
질문	"생산량은?"	"생산 순서와 시점은?"
단위	수량, 배치(Lot), 기간별 생산량	시간, 작업 순서
주요 고려사항	수요, 생산비, 재고비, 셋업비용	자원 가용성, 우선순위, 납기, 가동시간
모델 유형	EOQ, Wagner-Whitin, Capacitated Lot Sizing	Job Shop, Flow Shop, Gantt Chart
예시	"이 주에 제품 A를 500개 생산하자"	"제품 A는 월요일 오전에 생산하자"

• continuous manufacturing 에서 중요 -- 비용과 시간 셋업, 변화하는 수요

big buckets & small buckets

Big Bucket 모델과 Small Bucket 모델은 생산 계획 및 일정 관리 (Planning & Scheduling)에서 사용되는 시간 구간(time bucket) 기반 모델링 방식
| 구분 | Big Bucket 모델 | Small Bucket 모델 |
| ------ | ---------------------------- | -------------------------- |
| 초점 | 계획(Planning) 중심 | 스케줄링(Scheduling) 중심 |
| 시간 단위 | 긴 시간 간격 (예: 1주, 1일) | 짧은 시간 간격 (예: 1시간, 10분) |
| 유연성 | 낮음 (세부 순서 미포함) | 높음 (정확한 시작/종료 시각 포함) |
| 계산 복잡도 | 낮음 (빠름) | 높음 (느림) |
| 사용 목적 | 생산량 결정 (얼마나?) | 작업 순서/시간 결정 (언제?) |
| 모델 예시 | Lot Sizing (Wagner-Whitin 등) | Job Shop Scheduling 등 |

w/ Changeover

종류	설명
Sequence-dependent	제품 A → B 전환과 B → A 전환의 세팅 시간이 다름 예: 색이 진한 제품에서 밝은 색으로 전환할 때 청소시간 더 김
Time-dependent	일정 시간마다 강제로 체인지오버 필요 예: 8시간마다 청소 필요
Volume-dependent	일정 생산량 후 체인지오버 필요 예: 1000병 생산하면 필수 청소

• 연습문제 : 수식 바꾸기 -> The changeover has to be performed at a fixed time.
  

• 연습문제 -- add Big-M formulation
  

Economic Lot Sizing (ELS)

ELS는 일정 기간 동안 수요를 충족시키기 위해 언제, 얼마나 생산할 것인가를 결정하는 문제입니다.
목표는 총비용(생산 + 재고 + 셋업 비용)을 최소화하는 것

Economic Lot Sizing (ELS): One type Item

"단일 품목"은 오직 하나의 제품만 고려한다는 뜻입니다.

• inventory
• cost
• lot size
• setup time

Economic Lot Sizing (ELS): Several types of Item

• interactive에 있는 연습문제 중요!!

---

4b - Lot Sizing 2 - industry application ||| Block planning (Multi-stage systems)

Block planning

Block Planning은 생산 자원을 일정 시간 동안 특정 제품군(product family)에 "블록(block)" 단위로 할당하는 계획 방식입
| 요소 | 설명 |
| -------------------------- | ------------------------------------ |
| 🔲 Block | 일정한 기간 동안 자원을 특정 제품군에 전담 배정하는 시간 슬롯 |
| 🧱 제품군(Product Family) | 유사한 자재, 설비, 공정을 공유하는 제품들의 집합 |
| 🕒 Time Horizon | 예: 한 달, 한 주 등 블록을 배치하는 전체 기간 |
| ⛓️ 제약조건 | 수요, 설비 용량, setup/changeover 시간, 재고 등 |

modeling

Two-stage flow line in food production -- cheese

Structure
First Stage: The initial stage involves the pretreatment and standardization of the basic product, which is milk in the cheese production example. The milk is standardized to a specific fat content before being processed further.

Implications: This stage ensures uniform quality and consistency of the input material, which is crucial for the subsequent production processes.
Second Stage: The second stage involves filling the standardized milk into tubs and preparing the curd, which is then processed into cheese.

Implications: The second stage focuses on transforming the standardized input into the final product through various processing steps.

---

---

---

5 a ) Online scheduling & Markov Decision Processes

online scheduling

미래 정보 알수 없는 상황에서 실시간으로 스케줄링 결정. uncertainty handling

Markov Decision Process (MDP)

MDP는 어떤 에이전트(agent)가 확률적으로 변화하는 환경에서 최적의 의사결정을 내리는 문제를 수학적으로 표현한 모델
| 기호 | 설명 |
| ------------- | --------------------------------------------------------------------- |
| S | 상태 집합 (State space): 에이전트가 있을 수 있는 모든 상태들 |
| A | 행동 집합 (Action space): 각 상태에서 취할 수 있는 행동들 |
| P | 상태 전이 확률 함수 (Transition probability): 특정 상태에서 어떤 행동을 했을 때 다음 상태로 갈 확률 |
| R | 보상 함수 (Reward function): 특정 상태에서 특정 행동을 했을 때 얻는 보상 |
| γ (gamma) | 할인율 (Discount factor): 미래 보상을 현재 가치로 환산하는 비율, $0 \leq \gamma < 1$ |

• Markov Property

  미래는 오직 현재 상태에만 의존하고 과거는 필요 없다
  P(St+1​∣St​,At​,St−1​,At−1​,...,S0​,A0​)=P(St+1​∣St​,At​) -> 다음상태의 확분은 현재상태와 행동에만 달렸다!

• 정책 (Policy) 𝜋 ( 𝑠 ) π(s): 각 상태에서 어떤 행동을 선택할지를 정해주는 함수
• 가치 함수 (Value function): 특정 상태에서 시작했을 때 받을 것으로 기대되는 총 보상

• bellman equation

Bellman Equation(벨만 방정식)은 MDP의 핵심을 수학적으로 표현한 식이에요. MDP가 "의사결정 문제를 정의"하는 틀이라면, Bellman Equation은 그 틀 안에서 최적의 정책(Policy)이나 가치 함수(Value Function)를 계산하는 원리를 설명
"최적성 원리"에 따라 최적화 문제를 일련의 더 단순한 하위 문제로 나누는 동적 프로그래밍 기법

plolicy iternation / value iteration

dynamic programming

---

---

5 b Online Scheduling with GP & RL

Genetic programmming:

Genetic Programming은 유전 알고리즘(Genetic Algorithm)의 확장 형태로, 프로그램 자체를 진화시키는 최적화 기법

• infix notation -> binary tree 변환

• prioritz matrix