基于C++的四象限法设备平面布局的优化

基于C++的四象限法设备平面布局的优化小组成员及分工情况：注：编程部分由全体成员共同完成钟俊辉（20091008）：除编程外负责统稿全文，画程序框图、算法流程，完成计算实例5、6何俊（20091027）：除编程外负责收集相关资料，并完成计算实例4、7马玉梅（20091028）：除编程外负责整理相关资料，并完成计算实例3、8金步岸（20091032）：除编程外负责写从至表，并完成计算实例2、9潘阳（20091002）：除编程外负责写四象限法，并完成计算实例1、101自动化制造系统的组成设备较多，总体平面布局可对零件生产、产品成本等产生很大的影响，应该予以充分的重视。产品的生产是通过加工来实现的，而加工又是通过设备和工人的工作来完成的，因此设备的布局应该能实现和满足特定的生产过程的要求。同时，设备的布置应该使在其间进行的生产有较高的效率，且各设备能力负荷合理，以使生产高效、稳定的进行。因此，为了得到较高的效率与合理的成本，就要对设备的平面布局进行优化，从而得到设备布局的最优解。一、从至表法从至表法是一种试验性的设计方法，适用于加工设备布置在运输线路一侧成直线排列的一维布局设计。这根据零件在各设备间移动次数建立的从至表，经有限次实验和改进，求得近似最优的布置方案。所谓从至表就是零件“从”一个设备“至”另一个设备移动（搬运）次数的汇总表，它是一个按设备数（n）确定的nn矩阵，表中的行为零件移动的起始设备，列为终至设备，行和列交叉中的数据为零件在这两台设备间的移动次数即从至数。从至法的基本步骤为：（1）、根据每一种零件的工艺方案，绘制综合工艺路线图。（2）、根据零件的综合工艺路线图编制零件从至表。（3）、计算在本排列方式下零件移动的总距离。（4）、分析和改进从至表，从而求得较优的设备方案。最佳的设备排列应该是使从至表中越大的从至数越靠近对角线。二、四象限法对于n个设备的系统，设备可能的排列组合多达!n个，当n较大时，全部试排一遍是不可能的。用“四象限法”可以比较方便、迅速地通过有限次试排而得出较优的排列顺序。其基本步骤如下：（1）、随意选择二个相邻的设备，将两设备所在的列和行抽出来，并以其相邻的连线作为坐标轴，将图划分为Ⅰ、Ⅱ、Ⅲ、Ⅳ四个象限。（2）、分别求Ⅰ、Ⅲ象限从至数的累加和1S，Ⅱ、Ⅳ象限从至数的累加和2S和这两个设备之间零件移动从至数的和3S。（3）求123SSSS，如果0S则这两个设备原有的排列顺序是合适的，否则是不合适的，应予以对调。当这两个设备原有排列顺序对调后，其运输距离相应就会减少S，对调后可得到新的从至表。因此，经过有限次调整后，即可获得较优的结果。三、C++编程原理若要获得最优结果，就不能像上面所说的随意调两相邻设备出来，而应该从第一和第二台设备开始逐一调出。但会遇到一个问题，当调到最后的1n台和n台时所输出的从至表也未必是最优化的结果，因为两相邻设备对调后，往前调的设备与对调后在其前一台的设备的排列并不一定是最优的。因此，为了得到最优化的结果，首先，从第一台和第二台设备开始调，当调到第i台和第1i台时，第一次出现0S，即第i台和第1i台需要对调，则下一步计算应该从第1i台和第i台中计算，若0S，则再下一步从第i台和第1i台中计算，如此反复，直到最后的第1n台和第n台。这样就可以保证无论任意地调出哪两台相邻的设备计算都能绝对保证0S，即为最优的结果。2四、程序框图根据编程原理可得到程序框图如图4-1所示开始输入从至表矩阵输入设备个数调两相邻设备的行与列出来，划分四个象限计算Ⅰ、Ⅲ象限和S1，Ⅱ、Ⅳ象限和S2，这两设备移动从至数和S3计算SS≤0将这两设备矩阵对调这两设备矩阵不用对调任意两相邻设备中，S≤0结束NYYN图4-1程序框图3五、算法流程根据程序框图，可以得到算法流程图，如图5-1所示。开始输入设备数length从data.txt中导入数据到Table中在堆中创建一个From_Table的对象对象初始化结束YNi++从From_Table中调用第i和i+1矩阵调用子程序计算resultresult0交换表的两行和表的两列i=0ilengthNY输出数据（i--）--图5-1算法流图4六、算法验证要验证算法的准确性，只需要根据给出的例子，将数据输入到程序中运行后，将运行结果与例子给出的结果进行对比，若运行结果与给出的例子结果一致，则可初步确定算法正确。由于可能存在偶然性，故只需与多个例子进行对比，若结果完全一致，则可说明算法的准确性。七、C++源程序该程序能满足1010以上矩阵规模的从至表分析及布局优化。（1）首先应该在该C++根目录内建立一个data.txt的文本，用于输入从至表矩阵。（2）其源程序如下。#includeiostream#includefstreamusingnamespacestd;classFrom_Table{private:int*table_p;int*order;inttable_length;public:From_Table(int*table_p,int*order,inttable_length);~From_Table();voidprintTable(void)const;voidcomputeAndChange(intleft,intright);voidswapTwoLine(intleft,intright);voidswapTwoRow(intleft,intright);voidmySwap(int*p,int*q);voidgetLowest_trans();};From_Table::From_Table(int*table_p,int*order,inttable_length):table_p(table_p),order(order),table_length(table_length){coutFrom_tableendl;}From_Table::~From_Table(){cout~From_tableendl;delete[]table_p;delete[]order;5}voidFrom_Table::mySwap(int*p,int*q){inttemp;temp=*p;*p=*q;*q=temp;}voidFrom_Table::swapTwoLine(intleft,intright){for(inti=0;itable_length;++i)mySwap(table_p+left*table_length+i,table_p+right*table_length+i);}voidFrom_Table::swapTwoRow(intleft,intright){for(inti=0;itable_length;++i)mySwap(table_p+i*table_length+left,table_p+i*table_length+right);}voidFrom_Table::printTable()const{inti,j;coutendl;for(i=0;itable_length;++i)cout(char)order[i]\t;coutendlendl;for(i=0;itable_length;++i){for(j=0;jtable_length;++j){couttable_p[i*table_length+j]\t;}coutendl;}coutendl;}voidFrom_Table::computeAndChange(intleft,intright){intone_area=0,two_area=0,three_area=0,four_area=0;intresult=0;6inti,j;if(left0)return;//计算第一象限for(i=0;ileft;++i)one_area+=table_p[i*table_length+right];for(j=right;jtable_length;++j)one_area+=table_p[left*table_length+j];//计算第二象限for(i=0;ileft;++i)two_area+=table_p[i*table_length+left];for(j=left;j=0;--j)two_area+=table_p[left*table_length+j];//计算第三象限for(i=right+1;itable_length;++i)three_area+=table_p[i*table_length+left];for(j=right;j=0;--j)three_area+=table_p[right*table_length+j];//计算第四象限for(i=right;itable_length;++i)four_area+=table_p[i*table_length+right];for(j=right+1;jtable_length;++j)four_area+=table_p[right*table_length+j];result=one_area+three_area-(two_area+four_area+table_p[left*table_length+right]+table_p[right*table_length+left]);//true表示需要对调，false表示不需要对调if(result0){swapTwoLine(left,right);swapTwoRow(left,right);mySwap(order+left,order+right);computeAndChange(left-1,right-1);}}voidFrom_Table::getLowest_trans(){for(inti=0;itable_length-1;++i)computeAndChange(i,i+1);}7intmain(){inti;int*table;intlength;cout输入您要优化的设备的个数：\n;cinlength;if(length=0)return-1;table=newint[length*length];int*order=newint[length];ifstreamicin;inttemp;icin.open(data.txt,ios::in);for(i=0;ilength*length;++i){icintemp;*(table+i)=temp;}icin.close();for(i=0;ilength;++i)order[i]='A'+i;From_Table*from_Table=newFrom_Table(table,order,length);from_Table-printTable();from_Table-getLowest_trans();from_Table-printTable();coutendl;coutendl;delete[]order;delete[]table;return0;}八、计算实例8.1设自动化制造系统有5台加工设备成直线排列，每台设备之间的距离大致相等，并8假设为一个单位的距离，共有7种不同零件在系统内加工，其初始从至表如表8-1-1所示。表8-1-1初始零件从至表从至1M2M3M4M5M1M892M443M854M10115M54则设备在该种排列下，零件总的移动距离为122L。优化后的从至表如表8-1-2所示。表8-1-2优化后的从至表从至3M1M2M4M5M3M851M892M444M10115M54验算：优化后，零件总的移动距离为1100L，1LL。8.2设自动化制造系统有6台加工设备成直线排列，每台设备之间的距离大致相等，并假设为一个单位的距离。共