線平衡切分問題(以C++實作)

前言：

本次文章算是難得有點學術外加有實務價值的。本次的內文的案例，出自於即將出版的論文蘇宗偉(2018)內的一個方案，名為線平衡，實際關於線平衡的計算方式我想大家Google的到，在本篇文章內的說明是:”在生產線當中，若有更好的線平衡率，則會有較少的等待時間，並且會因為生產時間的不平衡所造成的在製品降低”。而為了達成更好的線平衡率，則需要將生產線進行切分，找出可能的切分方式中最佳者。

而在這樣的背景動機下，我們可能遇到的問題是，工作站與工作站間的可能切分組合非常多，是否需要程式計算。而如何從切分結果中，快速的找到使線平衡率最高者。因此，正文將簡化實際案例，成為一個簡單的數學模型，在想辦法用程式計算。

正文：

在前言已經將問題的背景作了大致上的描述。因此以下就用幾張圖片快速讓大家了解我們要處理的問題與目前掌握的資訊，可以參考圖一至圖三。

圖一是蘇宗偉(2018)針對案例公司的一個製程區段的流程描述，可以看到左邊有三種零件，圖右邊則描述該零件對應必經的前加工區的製程，當前加工區完成加工，才能進入焊接區，將三種零件透過焊接組成一個前三角。

圖一 製程區段的流程描述

圖二則是將圖一的工作站進行編碼，分別編為S1~S8。

圖二 工作站編碼

經過簡化，可以看到最終流程如圖三所示。而目的就是測試所有可能的組合，(以立管為例)就是考量S1到S7之間，共計6個切點，是否需要進行切分，因此可能的解有2的6次方(因為每個切點都可以決定切或不切)。

圖三 線平衡方案示意圖

因此，目前的一個問題是，如何找出所有組合。因此，研讀了演算法筆記中的一篇講述排列組合文章，找到比較合適的方法為出自於Applied-math期刊Loughry, J., van Hemert, J., & Schoofs(2000)的Efficiently enumerating the subsetsof a set一文，所提出的Banker’s Sequence。該方法，可以從組合中(集合)擁有的元素數量由少至多，找出可能的組合，該方法的好處是，可以由擁有較少元素的組合開始找起；因此，假設本例子有切分的上限(可能是考量超級市場設立的成本，而有切點的上限的話)，那麼就可以設定組合中擁有元素的上限。當然，本例子是沒有這樣的考量，因此用此方法舉出所有可能的組合後，即可將下圖四的資料，放入程式中進行計算。

圖四 各零件加工工時

由於，一次的切點會產生一段的加工時間總和，因此，以此例我的向量(Vector)大小就預設為7。(六個切點最多把生產線上的所有工作站切成7個小段 (Segment) )。此處會選擇用向量還有一個好處，因為我們需要找出各個零件，最大分段的加工時間加總，因此用向量可以直接使用max_element直接找出向量中最大者，便於我們比較大小。

最後補充說明一下，本程式會輸出一個AllPossibleSubset的txt檔案，就代表在我們設定的切點個數下，可能的組合數。其中1就代表該切點會進行切分，而0則對應不會進行切分。而讀入這個檔案後，在根據切分/不切分，計算分段的加工時數，並輸出各零件的最大工時分段，將結果放到ConstraintResult.txt中。

引用：蘇宗偉 (2018)，「以精實生產原則改善高階自行車管件加工之問題」。成功大學製造資訊與系統研究所學位論文。

Loughry, J., van Hemert, J., & Schoofs, L. (2000). Efficiently enumerating the subsets of a set. Applied-math