Ekonomiskt mycket schemaläggningsproblem

The Economic Lot Scheduling Problem ( ELSP ) är ett problem inom driftledning och inventeringsteori som har studerats av många forskare i mer än 50 år. Termen användes första gången 1958 av professor Jack D. Rogers från Berkeley, som utvidgade den ekonomiska orderkvantitetsmodellen till fallet där det finns flera produkter som ska produceras på samma maskin , så att man måste bestämma både partistorleken för varje produkt och när varje parti ska produceras. Metoden illustrerad av Jack D. Rogers bygger på ett papper från 1956 från Welch, W. Evert. ELSP är en matematisk modell av ett vanligt problem för nästan alla företag eller branscher: planering av vad som ska tillverkas, när man ska tillverka och hur mycket man ska tillverka.

Modellformulering

Den klassiska ELSP handlar om att schemalägga produktionen av flera produkter på en enda maskin för att minimera de totala kostnaderna (som inkluderar installationskostnader och lagerhållningskostnader).

Vi antar en känd, icke-varierande efterfrågan $d_{j},j=1,\cdots ,m$ för de m produkterna (det kan till exempel finnas m=3 produkter och kunder kräver 7 artiklar per dag av produkt 1, 5 artiklar om dagen av produkt 2 och 2 artiklar per dag av produkt 3). Kundernas efterfrågan tillgodoses från lager och lagret fylls på av vår produktionsanläggning.

En enda maskin finns tillgänglig som kan tillverka alla produkter, men inte på ett perfekt utbytbart sätt. Istället måste maskinen ställas in för att producera en produkt, vilket medför en installationskostnad och/eller installationstid, varefter den kommer att producera denna produkt med en känd hastighet P j {\ ${j}}$ . När det är önskvärt att producera en annan produkt stoppas maskinen och ytterligare en kostsam installation krävs för att börja producera nästa produkt. Låt $S_{ij}$ vara installationskostnaden vid byte från produkt i till produkt j och lagerkostnad $h_{j}$ debiteras baserat på genomsnittlig lagernivå för varje artikel. N är antalet genomförda körningar, U användningsgraden, L partistorleken och T planeringsperioden.

För att ge ett mycket konkret exempel kan maskinen vara en tappningsmaskin och produkterna kan vara flaska äppeljuice , apelsinjuice och mjölk . Inställningen motsvarar processen att stoppa maskinen, rengöra den och ladda maskinens tank med önskad vätska. Detta produktbyte får inte göras för ofta, annars blir installationskostnaderna stora, men en lika lång produktionsserie av äppeljuice skulle vara oönskad eftersom det skulle leda till en stor lagerinvestering och kostnad för osålda lådor med äppeljuice och kanske stock-outs i apelsinjuice och mjölk. ELSP söker den optimala avvägningen mellan dessa två ytterligheter.

Rogers algoritm

1.Definiera:

$\theta =T/N=L/U$ = använd period

c _L = ${\frac {hL (PU)}{2PU}}+{\frac {S}{L}}$ , enhetskostnaden för många storlekar L

$C_{N}=NLc_{L}=UT\left[{\frac {hL\left(PU\right)}{2PU}}+{\frac {S}{L}} \right]$ den totala kostnaden för N partier. För att erhålla optimum lägger vi på:

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

ger $L_{0}={\sqrt {\frac {2USP}{h(PU)}}}$ som den optimala lotstorleken. Låt nu:

${\displaystyle C_{N_{L\pm a}}=UT\vänster[ {\frac {h\left(L\pm a\right)\left(PU\right)}{2PU}}+{\frac {S}{L\pm a}}\right]} vara den totala kostnaden$ för N _L± många storlekar L±a

$+\Delta = C_{N_{L+a}}-C_{N}=UT\vänster[{\frac {ha\left(PU\right)}{2PU}}-{\frac {S}{{\frac {L^ {2}}{a}}+L}}\right]$ är den inkrementella kostnaden för att byta från storlek L till L+a

${\displaystyle -\Delta =C_{N_{La}}-C_{N}=UT\vänster[-{\frac {ha\left(PU\right) }{2PU}}+{\frac {S}{{\frac {L^{2}}{a}}-L}}\right]} är den$ inkrementella kostnaden för att byta från storlek L till La

2.

Total kvantitet av en artikel som krävs = UT

Total produktionstid för en artikel = UT/P

Kontrollera att produktionskapaciteten är uppfylld:

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

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

3. Beräkna:

$\theta _{0}={\frac {L_{0}}{U}}$ som ett heltal

₀ Om θ för ett visst objekt inte är ett jämnt tal, beräkna:

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

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

₀ Och ändra L till L i den riktning som ger minst kostnadsökning mellan +Δ och -Δ

4. Beräkna t _p =L/P för varje objekt och lista objekt i ordning med ökande θ=L/U

5. Kontrollera för varje par artiklar:

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

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

To-formerpar ta i: ^an med i+1:an, i+2:an, etc. Om någon av dessa olikheter överträds , beräkna +Δ och -Δ för partistorlekssteg på 2U och i ordningsföljd efter storleken på kostnadsändringen gör steg-för-steg ändringar av partistorlek. Upprepa detta steg tills båda ojämlikheterna är uppfyllda.

6. $e_{ij}=d-t_{p_{i}}\leq \theta _{i}-t_{ p_{i}}-t_{p_{j}}$

1. Bilda alla möjliga par som i steg 5
2. _i < θ _j för varje par
3. Bestäm om t _{p i} > t _{p j} , t _{p i} < t _{p j} eller t _{p i} = t _{p j}
4. Välj ett värde för e _ij (e _ij =0,1,2,3,...,θ _i - t _{p i} - t _{p j} ) och beräkna t _pi +e och t _pj +e
5. Beräkna M _i θ _i -M _j θ _j genom att sätta Mi ₌ k och Mj ₌ 1,2,3,...,T/ _θj ; ∀k∈(1,2,...,T/θi ₎ . Kontrollera sedan om något av följande gränsvillkor är uppfyllt:

för $t_{p_{i}}>t_{p_{j}}$ eller $t_{p_{i}}<t_{p_{ j}}$${\begin{cases}t_{ p_{i}}+e\geq M_{i}\theta _{i}-M_{j}\theta _{j}>e\\t_{p_{i}}+e>M_{i}\theta _{i}-M_{j}\theta _{j}\geq t_{p_{i}}+e\\t_{p_{j}}+e\geq M_{i}\theta _{i}- M_{j}\theta _{j}>t_{p_{i}}+e\\t_{p_{i}}+t_{p_{j}}+e>M_{i}\theta _{i} -M_{j}\theta _{j}\geq t_{p_{j}}+e\end{cases}}$

för $t_{p_{i}}=t_{ p_{j}}$${\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}>t_{p_{j}}+e\\t_{p_{i}}+e=M_{i}\theta _{i}-M_{j}\theta _{j}=t_{p_ {j}}+e\end{fall}}$

Om inget av gränsvillkoren är uppfyllt är e _ij icke-störande: om i=1 i e _ij , välj nästa större e i delsteg 4, om i ≠1 gå tillbaka till delsteg 2. Om något gränsvillkor är uppfyllt, gå till delsteg 4. Om, för något par, inget icke-störande e visas, gå tillbaka till steg 5.

7. Ange objekt i schemat och kontrollera att det är genomförbart

Stokastisk ELSP

Av stor betydelse i praktiken är att designa, planera och driva delad kapacitet över flera produkter med omställningstider och kostnader i en osäker efterfrågemiljö. Utöver valet av (förväntade) cykeltider, med viss mängd slack designad i ("säkerhetstid"), måste man också ta hänsyn till mängden säkerhetslager (buffertlager) som behövs för att uppfylla önskad servicenivå.

Problemstatus

Problemet är välkänt inom verksamhetsforskaren och ett stort akademiskt forskningsarbete har skapats för att förbättra modellen och skapa nya varianter som löser specifika frågeställningar.

Modellen är känd som ett NP-hårt problem eftersom det för närvarande inte är möjligt att hitta den optimala lösningen utan att kontrollera nästan alla möjligheter. Det som har gjorts följer två tillvägagångssätt: att begränsa lösningen till att vara av en specifik typ (vilket gör det möjligt att hitta den optimala lösningen för det smalare problemet), eller ungefärlig lösning av hela problemet med hjälp av heuristik eller genetiska algoritmer .

Se även

• Oändlig fyllnadsgrad för den del som produceras: Ekonomisk orderkvantitet
• Konstant fyllnadsgrad för den del som produceras: Ekonomisk produktionskvantitet
• Efterfrågan är slumpmässig: klassisk Newsvendor-modell
• Efterfrågan varierar över tiden: Dynamisk partistorleksmodell

Vidare läsning

• SE Elmaghraby: The Economic Lot Scheduling Problem (ELSP): Review and Extensions, Management Science, Vol. 24, nr 6, februari 1978, s. 587–598
• MA Lopez, BG Kingsman: The Economic Lot Scheduling Problem: Theory and Practice, International Journal of Production Economics, Vol. 23, oktober 1991, s. 147–164
•   Michael Pinedo, Planning and Scheduling in Manufacturing and Services, Springer, 2005. ISBN 0-387-22198-0

externa länkar

• Gallego: The ELSP, Columbia U., 2004