Solving Dynamic Lot Sizing with Python’s PuLP
ในปัญหา dynamic lot sizing, demand ไม่เท่ากันในแต่ละ time period. (แตกต่างกับใน Economic Order Quantity (EOQ) model ซึ่งมี assumption ว่า demand คงที่). ในการสั่งซื้อแต่ละครั้ง, มี setup cost แทนด้วย K. ในการถือครองสินค้า, มี unit holding cost = h; นั่นคือ หากสมมติให้ time period คือสัปดาห์ จะได้ว่าต้นทุนในการถือครองสินค้าหนึ่งหน่วยต่อหนึ่งสัปดาห์เท่ากับ h บาท.
Input parameters
สมมติให้ setup cost K = 300 บาท และ unit holding cost h = 1 บาท/หน่วย/period. (ไม่ว่าจะสั่งกี่ชิ้นก็ตามจะเสีย setup cost K = 300 บาทต่อครั้ง.) สมมติว่าเราต้องการวางแผนล่วงหน้า 10 period นั่นคือ planning horizon n = 10. เราต้องรู้ demand ทั้งหมด n periods แทนด้วย D1, D2,…,Dn; เราอาจะใช้ time series forecasting method เพื่อดู trend และ season ในอดีตเพื่อ forecast demand ทั้งหมด 10 ตัวนี้. จาก Table 1, สังเกตว่า demand สูงสุดคือ 100 ใน period 6 แและต่ำสุดคือ 20 ใน period 10. ตอนเริ่มต้นของ period แรก, สมมติเราไม่มีสินค้าคงคลังเหลืออยู่เลย (initial inventory = 0). ในการวางแผนนี้, ไม่ต้องการให้สินค้าขาดมือ.
Sequence of events
ในแต่ละ period, เหตุการณ์ที่เกิดขึ้นเป็นดังนี้
- ในตอนต้น period, เราทราบ inventory level ของ period ที่ผ่านมา.
- เราตัดสินใจว่าจะสั่งซื้อเป็นจำนวนเท่าใด?
- สินค้าที่สั่งมาถึง
- มี demand เกิดขึ้น
- ตอนปลาย period, เราทราบ inventory level
เช่น สมมติว่าหากตอนสิ้น period 3 เรามีของเหลือ Inv3 = 0. ใน period 4, เราตัดสินใจสั่งซื้อเป็นจำนวน Q4 = 200. จาก Table 1, D4 = 70. เมื่อสิ้น period 4, จำนวนสินค้าคงคลังจะเป็น Inv4 = Inv3 + Q4 -D4 = 0 + 200–70 = 130.
หากมี scheduled receipt ที่จะรับสินค้าไว้แล้วในบาง period, ควรใช้ net requirement ซึ่งหักด้วย schedule receipt ออกจาก demand ไปแล้ว. นอกจากนี้หาก lead time > 0, ให้ใช้ time-phased net requirement เพื่อให้ได้ของทันใน period ที่ต้องการจะใช้. ตัวอย่างเช่น predicted demand ที่ได้ในสัปดาห์ 4 คือ 90, มีของที่กำลังจะมาส่ง (scheduled receipt) ในสัปดาห์ 4 คือ 10 (จากการสั่งครั้งก่อนๆที่ยังทยอยมาส่งไม่ครบ), และคาดว่า ending inventory สัปดาห์ 3 คือ 30. จะคำนวณ net requirement ในสัปดาห์ 4 ได้จาก 90–10–30 =50. หากมี lead time = 3 สัปดาห์, จะได้ time-phased net requirement ของสัปดาห์ที่ 1 คือ 50.
Lot sizing algorithm ที่จะอธิบายต่อไป จะใช้เพื่อคำนวณหา planned order release ที่เหมาะสมที่สุด. หากสั่งทุก period (หรือที่บางครั้งเรียก “lot for lot”) จะเสีย setup cost สูงมากแต่ไม่มี holding cost เลย. ในทางตรงกันข้าม หากสั่งทั้งหมดเพียงครั้งเดียวใน period แรกสุด, จะเสีย holding cost สูงมาก. Lot sizing algorithm จะพยายาม balance ค่าใช้จ่ายทั้งสองนี้.
Simple 3-period policy
พิจารณานโยบายแบบง่าย คือ สั่งทุก 3 periods. จะได้ว่า ปริมาณสั่งซื้อ (order quantity) ใน period แรก Q1 = D1 + D2 + D3 = 50 + 60 + 90 = 200, และ Q4 = D4 + D5 + D6 = 70 + 30 + 100 = 200 เป็นต้น. จะได้จำนวนสินค้าคงคลังและค่าใช้จ่ายตาม Table 3.
เรานิยาม indicator = 1 เมื่อมีการสั่งซื้อ และเป็นศูนย์เมื่อไม่มีการสั่งซื้อ. จะได้
Total setup cost = K*(Indicator1 + Indicator2 +…).
Total holding cost = h*(Inv1 + Inv2 +…).
Total cost = (Total setup cost) + (Total holding cost)
นโยบายข้างต้นมีการสั่งที่เดือน 1, 4, 7, 10 เป็นจำนวน 200, 200, 180, 20 ตามลำดับ. ได้ค่าใช้จ่ายรวมคือ 1870.
Code for lot sizing problem (LP formulation)
เราต้องการหานโยบายการสั่งซื้อที่ทำให้ได้ค่าใช้จ่ายรวมต่ำสุด. ปัญหานี้ สามารถเขียนเป็น linear program ได้ ตาม code ด้านล่าง. คำอธิบายอยู่ต่อจาก Figure 1.
เมื่อ solve แล้วจะได้
ต้นทุนรวมต่ำสุดคือ 1550 และ optimal order quantity ดังแสดงใน Table 4. หากต้องการแสดงเฉพาะ order quantity ใน period ที่มีการสั่งซื้อ สามารถทำได้โดยใช้ code ตามใน [12]. เนื่องจาก index แรกของ list ใน Python คือ 0, ตัวแปร Qty_0 = Q1 จำนวนสั่งซื้อใน period ที่ 1, ตัวแปร Qty_2 = Q3 จำนวนสั่งซื้อใน period ที่ 3 เป็นต้น.
รายละเอียดของแต่ละบรรทัดเป็นดังนี้
Line 1: import pulp เข้ามาใช้
Line 8: กำหนด planning horizon และ timeIndex=range(0,nTime) เช่นในตัวอย่าง nTime=10 จะได้ timeIndex เป็น 0,1,2,…,8,9 ซึ่งตรงกับ periods 1,2,3,…,9,10 ใน Tables 1–3.
Line 10: กำหนดจำนวนสินค้าคงคลังเริ่มต้น invInitial=0 ซึ่งสามารถจากเลขศูนย์เป็นเลขอื่นๆได้ตามข้อมูลปัจจุบัน.
Line 11: demand ได้มาจาก forecasting พร้อมทั้งเอา lead time และ scheduled receipts มาคิดด้วยเพื่อให้ได้เป็น time-phased net requirement.
Line 13: cap เป็นจำนวนสูงสุดที่สั่งได้. หากเป็นไปได้, ควรกำหนดให้สูงกว่าปริมาณความต้องการรวม, เพื่อให้ LP สามารถพิจารณาได้ทุก solution รวมทั้งแบบที่สั่งครั้งเดียวใน period แรกด้วย (นั่นคือ ใน period 1, สั่งให้เท่ากับปริมาณความต้องการรวม จะเสีย setup cost แค่ครั้งเดียว แต่จะมี total holding cost สูงมาก).
Line 14–15: กำหนด setup cost และ unit holding cost
Line 18: สร้าง LP ชื่อว่า Lotsizing เป็นปัญหาการหาค่าต่ำสุด LpMinimize เอา LP model ที่ได้เก็บไว้ในตัวแปรชื่อ mod
Line 25: ระบุ decision variable จำนวนที่สั่งซื้อ Q ซึ่งมี index อยู่ใน timeIndex นั่นคือ Q[0], Q[1],Q[2],… กำหนดให้ Q ≥ 0 เนื่องจากเป็นปริมาณที่สั่งซื้อ. หากต้องการกำหนดให้เป็นจำนวนเต็ม สามารถใส่เพิ่มเข้าไปได้ เป็น
Q = LpVariable.dicts("Qty", timeIndex, lowBound=0, cat=LpInteger)
Line 28: ระบุ decision variable จำนวนสินค้าคงคลังปลาย period IL[0], IL[1],... หาก demand ที่ forecast ได้มี error, อาจต้องกำหนด safety stock > 0 ให้เป็น lower bound.
Line 31: ระบุ decision variable Uที่เป็น binary {0,1}.
Line 37: เพิ่มเข้าไปในตัวแปรที่สร้างขึ้น mod += , ระบุ objective function ซึ่งเป็นผลรวมของ setup cost และ holding cost ของทุก periods ใน timeIndex และตั้งชื่อ objective function นี้ว่า "TotalCost" เพื่อดูหาก print model ออกมา
Line 45–53: ระบุ constraints ทั้งหมดของ LP นี้โดยใช้ mod += .
Line 45–43: สำหรับแต่ละ t=0,1,2,…, Q[t] ≤ (cap)*U[t] นั่นคือ
Q[0] ≤ (cap)*U[0],
Q[1] ≤ (cap)*U[1],
…
Constraint บังคับให้ binary variable U[t] มีค่าเป็น 1 เมื่อมีการสั่งซื้อ: ถ้า Q[t] > 0 แล้ว U[t] =1 เท่านั้น, จะเป็น 0 ไม่ได้, เพราะจะขัดกับ constraint.
Line 49–50: สำหรับแต่ละ t=1,2,3,…, IL[t] = IL[t-1] + Q[t] — D[t] นั่นคือ IL[1]=IL[0]+Q[1]-D[1],
IL[2]=IL[1]+Q[2]-D[2],
…
Constraint นี้ให้นิยามของ ending inventory ตอนสิ้น period. สังเกตว่า หาก t=0 จะไม่สามารถหาค่า IL[-1] ได้, จึงแยกออกมาเป็นอีก constraint ใน Line 53 สำหรับที่ period แรก. เรามักเรียก constraints กลุ่มนี้ว่า inventory balance constraints เนื่องจากบอกถึงความสัมพันธ์ระหว่าง inventory ในแต่ละ period.
Larger model
ตัวแบบข้างต้น สามารถปรับให้ใหญ่ขึ้น เช่น มีสองสินค้า และใช้ budget ในการสั่งซื้อร่วมกัน ใน Line 58–59 ของ code ด้านล่าง
