경제 로트 스케줄링 문제

ELSP(Economic Lot Scheduling Problem)는 50년 이상 많은 연구자들에 의해 연구되어 온 운영 관리 및 재고 이론의 문제이다.이 용어는 1958년 잭 D 교수에 의해 처음 사용되었다. 버클리 ^[1]대학의 로저스는 경제 주문 수량 모델을 동일한 기계에서 여러 개의 제품이 생산되는 경우까지 확장하여 각 제품의 로트 크기와 로트 생산 시기를 모두 결정해야 했다.Jack D가 설명한 방법.로저스는 1956년 Welch, W. Evert의 ^[2]논문을 인용한다.ELSP는 제조 대상, 제조 시기, 제조 수량 계획 등 거의 모든 기업 또는 업계에서 공통적인 문제의 수학적 모델입니다.

모형 제작

기존 ELSP에서는 발생하는 총 비용(셋업 비용 및 인벤토리 보유 비용 포함)을 최소화하기 위해 단일 머신에서 여러 제품을 생산하도록 스케줄링하는 것이 중요합니다.

우리는 m 제품에 대해 알려진 비표준 $수요{\displaystyle {}_{}}$ d ${\displaystyle j_{}}$ ${\displaystyle j}$ $=$ , j 、$$ , $m$ { \ $displaystyle d_{j$ ,$j$ = $1,$ \$cdots$ , m$$}을$$ 가정합니다(예를 들어, m= 3개의 제품이 있을 수 있으며 고객은 제품 1의 하루에 7개, 제품 2개의 아이템을 필요로 합니다).고객의 요구는 재고에서 충족되고 재고는 생산 시설에서 보충됩니다.

모든 제품을 만들 수 있는 단일 기계를 사용할 수 있지만 완벽하게 교환할 수 있는 방법은 아닙니다.그 대신에, 1개의 제품을 생산하도록 기계를 셋업 할 필요가 있어 셋업 코스트나 셋업 시간이 소요됩니다.그 후, 이 제품을 기존의 레이트 $(\$로 생산합니다.다른 제품을 생산하려면 기계를 정지하고 다음 제품 생산을 시작하기 위해 또 다른 고가의 셋업이 필요합니다.제품 i에서 제품 j로 전환 시 설정 ${\displaystyle {\mathrm{비용}}_{}}$은$Sij$ {$displaystyle S_{$ij$$}로 $하고{\displaystyle {}_{}}$ $재고{\displaystyle {}_{}}$ 비용 ${\displaystyle h_{}}${\$displaystyle h_{j}}$는 품목별 평균 재고 수준을 기준으로 청구합니다.N은 실행 횟수, U는 사용률, L은 로트 크기, T는 계획 기간입니다.

아주 구체적인 예를 들면, 그 기계는 병입기일 수도 있고, 그 제품들은 병에 든 사과 주스, 오렌지 주스, 그리고 우유일 수도 있다.이 설정은 기계를 정지하고 기계를 청소하고 기계의 탱크에 원하는 오일을 적재하는 과정에 해당합니다.이 제품을 너무 자주 바꾸거나 셋업 비용이 커서는 안 되지만, 마찬가지로 애플 주스의 생산 기간이 너무 길면 사과 주스의 미판매 케이스에 대한 재고 투자와 운반 비용이 크고 오렌지 주스와 우유의 재고가 소진될 수 있기 때문에 바람직하지 않습니다.ELSP는 이 두 극단 사이에서 최적의 균형을 추구합니다.

로저스 알고리즘

1. 정의:

${\displaystyle \bullet }$ =${\displaystyle T}$ / N${\displaystyle }$=${\displaystyle L}$ /$U$ {$displaystyle$ \theta $= T$ / $N =$ L /$$U } $$= ${\displaystyle \mathrm{사용기간}}$

c_L= ${\displaystyle \frac{h}{}}$L (${\displaystyle \frac{P}{}}$ -${\displaystyle \frac{U}{}}$ ) ${\displaystyle \frac{\mathrm{}}{}}$ ${\displaystyle \frac{P}{}}$ ${\displaystyle \frac{U}{}}$+ ${\displaystyle \frac{S}{}}$ L$$( \ $displaystyle$\ $frac${ $hL$($$P - U ) } { $2$$PU}}+{\frac {S}{L$ L 사이즈의 단가

$=$$표시 C_{N$$UT\left[{\frac {hL\left(P-U\right)}{2$PU$}}+{\frac {S}{L}}\right}N$ 로트의 총비용입니다.최적화를 실현하기 위해, 델은 다음을 실시합니다.

$(\displaystyle\frac{d(C_{N}){dL}} = flac {hT\left(P-U\right)}{2P}}-{\frac {SUT}{L^{2}}=0}$

${\displaystyle {즉\mathrm{}}_{}}$, L 0 ${\displaystyle {}_{}}$ ${\displaystyle 2\sqrt{\frac{\mathrm{}}{}}}$ ${\displaystyle \sqrt{\frac{U}{}}}$ ${\displaystyle \sqrt{\frac{}{}}}$h (${\displaystyle \sqrt{\frac{P}{}}}$ -${\displaystyle \sqrt{\frac{U}{}}}$ )$${ $displaystyle L_{0$ } =$sqrt${$frac${ $2$ }$USP}{h$$(P-U)}}}}}:$ 최적 로트 사이즈.이제 다음을 수행합니다.

$]$$UT\left[{\frac {h\left(L\pm a\right)\left(P-U\right)}{2$$PU}}+{\frac {S}{L\pm$ a$}}\right}$는 L±a 크기의 Nlot의_L±a 총 비용입니다.

$=$$PU}-{\frac {S}{\frac {L^{2}}{a}}+$$L}}\right]}$는 L사이즈에서 L+a로 변경하는 증분비용입니다.

$displaystyle$$PU}}+{\frac {S}{\frac {L^{2}}{a}}-L}}\right}$는 크기 L에서 L-a로 변경하는 증분 비용입니다.

2.

필요한 아이템의 총수량 = UT

품목의 총생산시간 = UT/P

생산 용량이 충족되는지 확인합니다.

$\displaystyle \sum _{i=1}^{m}{\frac {U_{i}T}{P_{i}}\leq T}$

$\displaystyle \sum _{i=1}^{m}{\frac {U_{i}}{P_{i}}\leq 1}$

3. 계산:

$U$$$$U}}$의 정수

특정 항목에 대해 θ가₀ 짝수가 아닌 경우 다음을 계산합니다.

${\displaystyle L=U\left(\theta _{0}+1\오른쪽)}$

${\displaystyle L=U\left(\theta _{0}-1\right)}$

그리고 +δ에서 -δ 사이에서 비용이 가장 적게 증가하는 방향으로 L을 L로 변경한다₀.

4. 항목별로 t=L/P를 계산하여_p ==L/U의 순서로 나열한다.

5. 각 항목 쌍에 대해 ij 체크:

$\displaystyle \theta _{i}-t_{p_{i}}\geq t_{p_{j}}$

$\displaystyle \theta _{j}-t_{p_{j}}\geq t_{p_{i}}$

쌍을 이루려면 i를^th i+1번째, i+2번째 등으로 취한다.이 중 하나라도 위반될 경우 로트 크기 2U의 증가분에 대해 + and과 - for를 계산하고 비용 변경 크기에 따라 단계적으로 로트 크기를 변경한다.두 부등식이 모두 충족될 때까지 이 단계를 반복합니다.

6. ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle j_{}}$ ${\displaystyle {}_{}d}$ - ${\displaystyle {}_{}}$ ${\displaystyle {p{}_{}}_{}}$ ${\displaystyle {i_{}}_{}}$ ${\displaystyle {{}_{}}_{}}$ ${\displaystyle {i\theta }_{}}$ i${\displaystyle {}_{}}$i - ${\displaystyle {t{}_{}}_{}}$ p${\displaystyle {{}_{}}_{}{i_{}}_{}}$ - ${\displaystyle {t{}_{}}_{}}$ p ${\displaystyle {j_{}}_{}}${ $display e$_ { $ij$ } =$$d - t _ { $p$_ { $i$} \$leq \theta$_ { $i$} - t$_$ { p$_$ { i$$} } - $t$_ { p _ { $j$} }

1. 순서 5와 같이 가능한 모든 쌍을 형성합니다.
2. 각 쌍에 대해 [ ]를_i 선택합니다_j.
3. t > t_pj, t_pi < t_pj 또는_pi t = t_pj 중 어느_pi 쪽인지 확인합니다.
4. e(e_ij=0,1,2,3,...)의_ipi 값을_ij 선택하고 t+e와_pj t+e를_pj 계산한다_pi.
5. M = k_j, M = 1, 2, 3, ...T/lamb_j; kk(1, 2, ...T/lamb_i; t∈)로 설정하여_i Mµ-Mµ를_iijj 구한다.그런 다음 다음 다음 경계 조건 중 하나가 충족되는지 확인합니다.

tp 위해 나는;t_{p_{j}}}또는 tp나는 &lt는 pj{\displaystyle t_{p_{나는}}<>는 과목은 pj{\displaystyle t_{p_{나는}}을입니다. t_{p_{j}}}{tp나는 + e≥ Miθ 나는 − Mjθ j>e tp나는 + e>Miθ 나는 − Mjθ j≥ tp나는 + etpj+e≥ M나 나는 Mj− θ$j$$M_{i}\theta _{i}-M_{j}\theta _{j}+e\t_{p_{j}+e\geq M_{i}\theta _{i}\theta _{j}\theta _{j}-M_{p_i}\theta _{p_i}\t}\ta_{j}$$_{j}}+e>$$M_{i}\theta_{i}-M_{j}\theta_{j}\geq t_{p_{j}}+e\end{case}}$

tp 위해 나는}}{tp나는 e을 +, Miθ 나는 − Mjθ j>e tp나는 tpj+e을 +, Miθ 나는 − Mjθ j>는 과목은 pj+e 있어 p나는 + e=Miθ 나는 − Mjθ j)tpj+e{\displayst tpj{\displaystyle t_{p_{나는}}=t_{p_{j}정도씩 생겨나고 있다.yle{\begin{$cases}t_{p_{i}}+e>$$M_{i}\theta_{i}-M_{j}\theta_{j}>e\t_{p_{i}}+t_{p$$}$$_{j}}+e>$$M_{i}\theta _{i}-M_{j}\theta _{j}}+e\t_{p_{i}+e=M_{i}-M_{j}\theta _{j}\ta _{p_{j}+{case}{case}}}$

어떤 경계 조건도 충족되지 않으면_ij e는 비중계적입니다. i=1 in_ij e이면 하위 단계 4에서 다음으로 큰 e를 선택하고, i11이 하위 단계 2로 돌아갑니다.일부 경계 조건이 충족되면 하위 단계 4로 이동합니다.어떤 쌍에서도 비간섭 e가 표시되지 않으면 스텝5로 돌아갑니다

7. 스케줄에 항목을 입력하고 실행 가능성을 확인합니다.

확률 ELSP

실제로 중요한 것은 수요 환경이 불확실한 상황에서 전환 시간과 비용으로 여러 제품에 걸쳐 공유 용량을 설계, 계획 및 운영하는 것입니다.(예상) 사이클 타임의 선택 이외에, 어느 정도의 여유 시간이 「안전 시간」으로 설계되어 있어, 희망하는 서비스 ^[3]레벨을 만족시키기 위해서 필요한 안전 재고(버퍼 재고)의 양도 고려해야 한다.

문제 상태

이 문제는 운영 연구 커뮤니티에서 잘 알려져 있으며, 모델을 개선하고 특정 문제를 해결하기 위한 새로운 변형을 만들기 위해 많은 학술 연구 작업이 생성되었습니다.

이 모형은 현재 거의 모든 가능성을 확인하지 않고 최적의 솔루션을 찾을 수 없기 때문에 NP-난이도 문제로 알려져 있습니다.지금까지 행해진 것은, 2개의 어프로치, 즉 솔루션을 특정의 타입으로 한정하는 것(좁은 문제에 대한 최적의 솔루션을 찾아낼 수 있는 것) 또는 휴리스틱스나 유전 ^[4]알고리즘을 사용해 대략적인 문제의 해결 방법.

「 」를 참조해 주세요.

• 생산 중인 부품의 무한 충전 속도:경제발주수량
• 생산 중인 부품의 고정 채우기 속도:경제생산수량
• 수요는 랜덤: 기존 뉴스벤더 모델
• 수요는 시간에 따라 달라집니다.동적 로트 크기 모델

레퍼런스

추가 정보

• SE Elmaghraby:ELSP: 경영과학, 제24권, 제6호, 1978년 2월, 587-598페이지
• M A Lopez, B G Kingsman:경제적 로트 스케줄링 문제:이론과 실천, 국제생산경제학회지, 제23권, 1991년 10월, 페이지 147~164
• Michael Pinedo, Springer, 제조 및 서비스 기획 및 스케줄링 담당, 2005.ISBN 0-387-22198-0

외부 링크

• 갈레고:ELSP, 콜롬비아, 2004