筆記 - 智慧型製造系統

發表於 更新於 分類於 Disqus：

  此為「智慧型製造系統」學習筆記，內容取自上課講義。

Capacity management

  一個製造系統除了製造系統本身，還需要自動化與控制系統、物料管控系統、品管系統等等的支援與協助。製造系統由以下組成：

  • Production machines
  • Material handling system
  • Computer system (e.g. coordination)
  • Human workers

  雖然說人類工人的消失是指日可待。製造系統最重要的目的就是生產，因此需要了解產能(capacity)的概念。


Capacity -> maximum rate of output per unit time or units of resource availability


  避免需求量突增、原料短缺、設備故障，需要safety capacity。


Safety capacity (%) = 100% - average resource utilization (%)


  當工廠收到工單(work order)，便需要計算必須的產能。對於某個工單 $i$，需要的產能如下：

$$
C_i = S_i + P_i \times Q_i
$$

  其中 $S_i$ 為setup time，是一個固定的overhead(與需求量無關)。$P_i$ 為工單 $i$ 裡每個unit需要的processing time，$Q_i$ 為工單 $i$ 裡的number of units。$C_i$ 在這裡是以時間為單位，指的是完成工單 $i$ 需求所需時間。產能也可以用產率表示，如下式：

$$
\text{Resource used }(C) = \text{Utilization }(U)\times[\text{service rate}\times\text{number of servers}]
$$

  式子裡的utilization就是目前產率(實際產率)和最大可能產率的比值，或者

$$
U = \text{resource used}/\text{resource available}
$$

  這裡的 $C$ 就不是最大產能，而是實際產能或者是需求產能。那麼短期內如何調整capacity呢？可以增加或是共用生產設備、售出給其他公司、從工人技能著手、調整排班等等。或者反其道而行，用促銷或是預訂(reservation)的方式，改變需求量，來調節需求與產能的關係。


  Some other things：revenue management system (RMS)、theory of constraints(關注影響整體產能的bottleneck)等。

Inventory management

  Inventory有以下類別：

  • Raw materials, component parts
  • Work-In-Progress (WIP) inventory
  • Finished-goods inventory
  • Safety stock inventory

  需要考慮以下的成本：

  • Ordering cost：訂單成本，包括發貨、運輸、收貨過程的成本。
  • Holding cost：持有成本，又稱作carriying cost。
  • Stockout cost：缺貨造成的損失。
  • Unit cost：生產一單位商品或服務的成本。

  一些有關inventory的概念：

  • Lead time

    下訂單到出貨的時間。

  • Stockouts

    無法滿足某物品的需求，即缺貨。可能導致預訂(backorder)或是失去訂單(lost sale)。

  • Total dollar usage

    Total dollar usage = item usage (volume) X item’s dollar value (unit cost)。有些品項的dollar value高但是量少，有些品項則是dollar value低但是量多。


  討論inventory模型，Fixed-Quantity System (FQS) 及 Economic Order Quantity (EOQ) model。


  FQS：每隔一段時間就會訂固定的量。用inventory position (IP)來分析，如下：

$$
\text{IP = OH + SR - BO}
$$

  其中OH為On-Hand Quantity，目前存量；SR為scheduled receipts，預計要送來倉儲的量(還沒送來)；BO為backorders，客戶預訂的量。當IP低於reorder point，就要叫貨(place a new order)。Time between orders (TBO)的概念，當demand rate是固定的，TBO也會是定值。


  EOQ：可以達到最小cost(holding cost + ordering cost)的存量。EOQ模型不允許發生stockout，且demand rate和lead time為常數。


  計算最佳存量的方法如下。定義annual holding cost per unit為$C_h$，則annual inventory-holding cost為 $\frac{1}{2}QC_h$，這裡用到average inventory為$\frac{1}{2}Q$，即最大存量(= 最佳存量)的1/2。


Cycle inventory的概念。改自講義圖片。

  又annual ordering cost為 $\frac{D}{Q}C_0$，其中 $D$ 為annual demand，$Q$ 為每張訂單的訂貨量，$C_0$ 為每張訂單的成本。Total annual cost可以表示為

$$
TC = \frac{1}{2}QC_h + \frac{D}{Q}C_0
$$

  由此得到最小化 $TC$ 的存量 $Q^{*}$：

$$
Q^{*} = \sqrt{\frac{2DC_0}{C_h}}
$$

  至於reorder point $r$ 則以demand rate和lead time的乘積計算，

$$
r = d \times L
$$

  也可以把 $r$ model為隨機變數，$r = \mu_L + z\sigma_L$。套用統計學的概念，$z\sigma_L$ 就可以作為safety stock，表示「要達到某信心水準的量」。


  上述的inventory模型是隨著存量變化而下訂單，因此是隨時查看存量的。還有另一種模型為fixed-period system (FPS)，固定間隔時間T才查看存量並補貨，那麼這個T的最佳值為何？根據前面EOQ的分析，annual demand為 $D$ 且每次下訂單送來的量為 $Q^{*}$，那當然最好間隔 $T^{*} = Q^{*}/D$ 檢查IP。這個模型固定的就不是 $Q$，而是review period $T$。

Scheduling

  排程的目標：最小化last completion time (makespan)。例：機場的登機口分配。一個排程的program由三個部分組成：machine environments，constraints，以及objectives。


  三種特別重要的machine environments：

  • Job shop，固定工序，每一階段(不同位置)有許多機台，完成某階段再前往下一階段。
  • Flow shop，固定工序，每一站(同位置)有許多機台，完成某一站再前往下一站。
  • Open shop，順序(工序)不重要，把每一關完成就好。

  其他machine environments(job $j$ on machine $i$)：加工時間 $p_{ij}$，到達時間 $r_j$，交期 $d_j$，權重 $w_j$。


  常見的constraints如下：

  • Release dates $r_j$，到達時間。
  • Preemptions，中斷。
  • Precedence，工作優先序。
  • Sequence-dependent setup time (比如說換一號板子機台就要重新設定一遍)
  • Breakdowns，機台當機。
  • Blocking (如buffer有容量限制)
  • No-wait (比如說兩工序之間不得間斷)

  常見的objectives如下：

  • Makespan $C_{max}$，總完工時間。
  • Maximum Lateness $L_{max}$，最大總延遲。
  • Total weighted tardness $\sum{\omega_j T_j}$，加權總延遲時間。
  • Weighted number of tardy jobs $\sum{\omega_j U_j}$，加權總延遲數量。

例1. total weighted completion time

  Environments = $1 \lvert \cdots \rvert \sum{\omega_j C_j}$。最佳解為 Weighted Shortest Processing Time (WSPT) rule。($w_j/p_j$ 愈大愈優先。)


  當存在 chains (比如說 J1、J2、J4 一定要依照1 -> 2 -> 3的先後順序)時，用 $\rho$-fractor 的做法；$\rho$ 愈大愈優先。

$$
\rho = \max_{k}{\frac{\sum{w_j}}{\sum{p_j}}}
$$

例2. maximum lateness

  Environments = $1 \lvert r_j \rvert L_{max}$，給你 $r_j$、$p_j$、$d_j$，排程使得 $L_{max}$ 最小。其最佳解為 branch-and-bound method，使用到 decision tree。假設總共 n 個 jobs，則決策樹會有 n + 1 層，如下圖所示。第零層為 root node，第一層共有 n nodes，表示第一個位置要安排的工作，第二層會有 n(n - 1) nodes，表示前兩個位置要安排的工作，以此類推。


Branch and bound method。改自講義圖片。

  這裡有一個條件，在第 k 層若 $r_{j_k} \geq \min_{j_i \in J}{(\max{(t, r_{j_i})}) + p_{j_i}}$。$J$ 為上一層(第 k - 1 層)節點還沒排程的工作，$t$ 為上一層節點的完工時間，則 $j_k$ 就不在第 k 層的排程考慮中。(因為使右式最小化的 $j_i$ 完成的時候，$j_k$ 甚至還沒 released。)


  可以用 earliest due date (EDD) first rule 來決定 lower bound，再用 branch-and-bound method 來刪掉分支。

Genetic algorithm

  首先介紹基因演算法的使用背景。Dispatching (派工)和 scheduling (排程)的差異：

  • 派工：實時規劃，適用於 processing time 無法確定的情況，通常不可得最佳解。
  • 排程：預先規劃，適用於 processing time 可以精確得知的情況，可得最佳解。

  對排程而言，garbage in，garbage out，加工時間不定的話，用最佳化找到的 solution 也沒用。


  Some common dispatching rules，用來指定工作的優先序：

  • Static
    • FIFO，SPT，WSPT，LPT，EDD。
  • Dynamic
    • Minimum slack $\max{(d_j - p_j - t, 0)}$，slack 為寬裕時間 (float time)。
  • Compound dispatching rule：一次考慮複數個目標。

  Assignment problems 的 formulation：

$$
\text{minimize}\quad Z = \sum_{i = 1}^{n}{\sum_{j = 1}^{n}{c_{ij}x_{ij}}}
$$

  其中 $x_{ij} = 1$ 表示第 i 個工作指派給第 j 個機台來處理，又因為每個工作只能指派給一個機台、每個機台只能處理一個工作，所以有以下的限制：

$$
\begin{align}
&\sum_{j = 1}^{n}{x_{ij}}\quad \text{for } i = 1, 2, \cdots, n\\[10pt]
&\sum_{i = 1}^{n}{x_{ij}}\quad \text{for } j = 1, 2, \cdots, n
\end{align}
$$

  這類問題如果用線性規劃來得到最佳解，需要花費大量運算時間；若是非線性的問題，則無法透過線性規劃求解。這時候基因演算法就可以派上用場。

所以什麼是基因演算法？

  如下圖。

Heuristic algorithms

  前述的基因演算法是一種啟發式演算法，並不保證找到最佳解，但是可以在一定的時間限制下找到best solution。模擬退火(SA)、粒子群演算法(PSO)、蟻群演算法(ACO)等皆為啟發式演算法，請參閱講義，這裡就不介紹。

Game theory

  介紹基本的non-cooperative zero sum game。這部分之後再做詳細的筆記(114-2電通所有開賽局理論的課呢)。

Summary

  當初選這堂課有兩個原因：1. 對啟發式演算法的興趣，以及2. 剛離開伺服器大廠派遣作業員的工作，對於製造系統有一些親身經驗，所以想要從工程的角度來認識這個系統。回顧這學期，確實學到一些製造系統的概念，也在期末專題實作啟發式演算法(GA)在最佳化公車派遣的應用，還是有一些takeaway的。