線平衡切分問題(以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/06/17
//說明:LBC為Line Balance Calculation的縮寫，目的在於計算生產線中，分段後的可能線平衡綠。
//首先要根據可能的切點，找出所有可能組合，放到第一個可產出文件:AllPossibleSubset.txt。此處找出集合的方法，請參考http://www.applied-math.org/subset.pdf
//再設定第二個檔案串流，讀取AllPossibleSubset，然後計算可能解的數量(由於一個可能解，後面都會有一個\n，所以看有幾個\n就有幾組解)
//再逐一計算每個可能解於三種零件的分段工時加總，分別放到topSeg,botSeg,stdSeg(也就是生產上/下/立 管的生產線的分段加工時間加總)
//最終將檔案輸出到ConstraintResult.txt
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <fstream>
#include <iterator>
using namespace std;
void output(int string[], int position);
void generate(int string[], int position, int positions);
int length;
//輸出可能組合檔案串流
fstream myfile;
//輸入可能組合檔案串流
fstream infile;
// This function takes "string", which contains a description
// of what bits should be set in the output, and writes the
// corresponding binary representation to the terminal.
// The variable "position" is the effective last position.
void output(int string[], int position)
{
int * temp_string = new int[length];
int index = 0;
int i;
for (i = 0; i < length; i++)
{
if ((index < position) && (string[index] == i))
{
temp_string[i] = 1;
index++;
}
else
temp_string[i] = 0;
}//end for
for (i = 0; i < length; i++)
myfile<<temp_string[i];
//cout << temp_string[i];
delete [] temp_string;
//cout << endl;
myfile << endl;
}
// Recursively generate the banker’s sequence.
void generate(int string[], int position, int positions)
{
if (position < positions)
{
if (position == 0)
{
for (int i = 0; i < length; i++)
{
string[position] = i;
generate(string, position + 1, positions);
}
}
else
{
for (int i = string[position - 1] + 1; i < length; i++)
{
string[position] = i;
generate(string, position + 1, positions);
}//end for
}//end if-else
}//end if
else
output(string, positions);
}
// Main program accepts one parameter: the number of elements
// in the set. It loops over the allowed number of ones, from
// zero to n.
//argv don't work in code block
//reference in https://stackoverflow.com/questions/11888528/how-to-take-command-line-argument-in-codeblock-10-05
//int main (int argc, char ** argv)
int main()
{
//argv[1]=(char*) 6;
/*if (argc != 2)
{
cout << "Usage: " << argv[0] << " n" << endl;
exit(1);
}
*/
//construct the file
myfile.open ("AllPossibleSubset.txt");
//設定位元數(也就是長度
length = 6;
//Top,down,stand tube process time
float topPT[]={ 75.36 , 0.8 , 67.28 , 0.72 , 0 , 0 , 0.55};
float botPT[]={ 101.36 , 1.06 , 66.28 , 1.06 , 0 , 0 , 1.11};
float stdPT[]={ 76.32, 0.19 , 72.16 , 1.51 , 17.20 , 2.16 , 2.11};
//上,下,立管的分段時間
vector<float> topSeg { 0.0, 0.0 , 0.0 , 0.0 , 0.0 , 0.0 ,0.0 };
vector<float> botSeg { 0.0, 0.0 , 0.0 , 0.0 , 0.0 , 0.0 ,0.0 };
vector<float> stdSeg { 0.0, 0.0 , 0.0 , 0.0 , 0.0 , 0.0 ,0.0 };
for (int i = 0; i <= length; i++)
{
int * string = new int[length];
//cout<<"======The "<<i<<" cut Result======"<<endl;
//myfile<<"======The "<<i<<" cut Result======"<<endl;
generate(string, 0, i);
delete [] string;
}
//宣告一個buffer放讀取的資料
char buffer[200];
FILE *fp=fopen("AllPossibleSubset.txt", "r");
char ch;//char buffer
int line_cnt=0;//line counter
while( ( ch = fgetc(fp)) != EOF)
if(ch=='\n')
++line_cnt;
//以本例而言，是64(2的6次方，因為六個切點，每個切點都有要切或不切兩個選項)
//cout<<line_cnt<<endl;
ofstream ResultFileStream;
ResultFileStream.open ("ConstraintResult.txt");
infile.open ("AllPossibleSubset.txt",ios::in);
//針對每個結果，開始計算各種切法的瓶頸時間
for(int i=0 ; i<line_cnt ; i++){
//重設所有切點的結果，每個結果都是0
topSeg={0,0,0,0,0,0,0};
botSeg={0,0,0,0,0,0,0};
stdSeg={0,0,0,0,0,0,0};
int cutter=0;
//讀取一個可能的切法
infile.getline(buffer,sizeof(buffer));
ResultFileStream<<"第"<<i<<"組的組合:"<<buffer<<endl;
//針對每個可能的切點(本例子有6點)，看是否有切
//由於array的index是從0開始，所以j要小於length(從0到5)
for(int j=0; j<length ; j++)
{
if(j==0){
if( buffer[j]=='0' )
{
//如果第一個點，不是切點，則要把第一站與第二站的加工時間加總
topSeg[cutter]=topPT[j]+topPT[j+1];
botSeg[cutter]=botPT[j]+botPT[j+1];
stdSeg[cutter]=stdPT[j]+stdPT[j+1];
}else{
topSeg[0]=topPT[j];
botSeg[0]=botPT[j];
stdSeg[0]=stdPT[j];
topSeg[1]=topPT[j+1];
botSeg[1]=botPT[j+1];
stdSeg[1]=stdPT[j+1];
cutter++;
}
}else{
if( buffer[j]=='0' )
{
topSeg[cutter]=topSeg[cutter]+topPT[j];
botSeg[cutter]=botSeg[cutter]+botPT[j];
stdSeg[cutter]=stdSeg[cutter]+stdPT[j];
}
else{
cutter++;
topSeg[cutter]=topPT[j];
botSeg[cutter]=botPT[j];
stdSeg[cutter]=stdPT[j];
}
}//end else
}
float top_result= *std::max_element(topSeg.begin(), topSeg.end());
float bot_result= *std::max_element(botSeg.begin(), botSeg.end());
float std_result= *std::max_element(stdSeg.begin(), stdSeg.end());
ResultFileStream<<"max topSeg:"<<top_result<<endl;
ResultFileStream<<"max topSeg:"<<bot_result<<endl;
ResultFileStream<<"max topSeg:"<<std_result<<endl;
}
//Close the output filestream
myfile.close();
return 0;
}
view raw LBC.cpp hosted with ❤ by GitHub
引用：蘇宗偉 (2018)，「以精實生產原則改善高階自行車管件加工之問題」。成功大學製造資訊與系統研究所學位論文。
Loughry, J., van Hemert, J., & Schoofs, L. (2000). Efficiently enumerating the subsets of a set. Applied-math

留言

張貼留言