2、0-1规划作业.docx
0”规划问题一条装配线由一系列工作站组成，被装配或制造的产品在装配线上流淌的过程中，每站都要完成一道或几道工序，假定一共有六道工序，这些工序按先后次序在各工作站上完成，关于这些工序有如下的数据：工序所需时间（分）前驱工序13无25无322461,3582634另外工艺流程特殊要求，在任一给定的工作站上，不管完成哪些工序，可用的总时间不能超过10分钟，如何将这些工序安排给各工作站，以使所需的工作站数为最少？1）模型分析与变量的假设下面，我们先探讨工序与工作站的关系，并试图建立起该问题的01型整数规划模型。对任一工序而言，它要么属于工作站人要么不属于工作站J,故决策变量可定义为：Fl若工序i在工作站jJ行厂。若工序i不在工作峋上运行这种定义，使我们能依据最优解中勺的值来很快确定工序i与工作站）之间的隶属关系O又因工序1,2,3所需的工作时间不超过10分钟，故工序1,2,3的工作可以在一个工作站上完成，此时，工序4,5,6只能分别在各自的工作站上工作,该可行解对应的工作站数为4个。也就是说，对最优解而言，该装配线上所需的工作站个数不会多于4个。因此，我们再定义变量如下：=P若在最优解中需要工作站j吗=j若在最优解中不需要工作站j至此，我们得到所需的目标函数为：maxz=wi+w2+w3+w42）再考虑该模型的约束条件：（1）每道工序均隶属于一个工作站，且每一工序都必需完成，故有以下六个约束：Xn+X12+xi3÷xi4=1=1，2,3,4,5,6）（2）在任一工作站上完成隶属工序所用的时间不能超过10分钟，故有以下四个约束：3xlj+5x2j+2x3j÷6x4j+Sx5j+3xj10(j=1,2,3,4)（3）最终，我们再考虑各道工序所受的先后次序约束的条件。先考察工序2与工序3的关系，因工序2在工序3之前运行，故若工序3隶属于工作站4,则工序2无论属于那个工作站均可；若工序3隶属于工作站3,则工序2可属于工作站1或2或3；此时，变量"2/"=1.23）应满意的约束条件为：X2+x22+X23133.同理，若工序3隶属于工作站2或1,则变量"=1.2,3）应满意的约束条件为：X2+2-%32如卬同理，依据其它工序的优先关系，可仿此法给出其相应的约束条件，由上图知，六个工序之间有五个优先关系，故这类约束条件共有15个。另外，在最优解中，若有一个工作站啊（P=1.2,3,4）不用（即二0）,则隶属于该工作站的全部与"=1'Z3,4,5,6）必需为0,于是，有以下四个约束条件：Xj÷X2j+X3÷x4j÷x5j÷x6j6wjG=1，2,3,4）3）模型的建立与求解至此，我们得到了该问题的01型整数规划模型，它共包含28个变量，29个约束条件，这样的模型用枚举法求解，人工计算是很难胜任的，这时，只能求助于计算机求解了。我们给出该问题的模型如下。该问题的目标函数为：maxz=wl+w2+w3+w4约束条件为：XiI+Xl2+f3+x,4=1(i=1，2,3,4,5,6)3阳j+5x2j+2x3.+6x4j+8-57+3%10X21+X22+X23X33x2+X22+X23X53X2I+X22X32.,X2l+X22X52.(j=1,2,3,4)21Wix11+x12X42；*31+132”42.,X4+x42x62.JUNJ41.9X3i41.,1.Xl1+X2+1】3X43%31+工32+%33%43X4+x42+x43X63XIj+x2j+x3j÷x4j÷x5j÷xjW6Wj(z=1,2,3,4)一条装配线含有一系列的工作站,在最终产品的加工过程中每个工作站执行一种或几种特定的任务.装配线周期是指全部工作站完成安排给它们各自的任务所花费时间中的最大值.平衡装配线的目标是为每个工作站安排加工任务,尽可能使每个工作站执行相同数量的任务,其最终标准是装配线周期最短.不适当的平衡装配线将会产生瓶颈一一一有较少任务的工作站将被迫等待其前面安排了较多任务的工作站.问题会因为众多任务间存在优先关系而变的更困难,任务的安排必需听从这种优先关系.这个模型的目标是最小扮装配线周期.有2类约束：1要保证每件任务只能也必需安排到一个工作站来加工；2要保证满意任务间的全部优先关系.装配线平衡模型有11件任务(A-K)安排到4个工作站(1-4),任务的优先次序如下图。每件任务所花费的时间如下表。任务ABCDEFGHIJK时间4511950151212121289如何将这些工序安排给各工作站，以使装配线周期最短，最短周期为多少？1)变量的假设设：1,表示第i个任务指派给躲个工作站完成T为完成第i个任务所需时间。CycleTime为装配线周期。2)问题分析(1)目标函数装配线周期最短：min=CycleTime(2)再考虑该模型的约束条件：每道工序均隶属于一个工作站，且每一工序都必需完成，故有以下几个约束：x(i,1)+x(i,2)+x(i,3)+x(i,4)=l,(i=1,211)各道工序所受的先后次序约束的条件：对于每一个存在优先关系的作业对来说，前者对应的工作站i必需小于后者对应的工作站j,即满意约束Jk*x(j,k)-k*x(i,k)0,(i为j的前驱任务)k=l对于每一个工作站来说，其花费时间必需不大于装配线周期：XT(i)*x(i,k)CycleTimek=l3)模型的建立与求解至此，我们得到了该问题的OT型整数规划模型，我们给出该问题的模型如下。该问题的目标函数为：min=CycleTime约束条件为：x(i,1)+x(i,2)+x(i,3)+x(i,4)=l,(i=1,211)k*x(j,k)-k*x(i,k)0,(i为j的前驱任务)A=I-1ZT(i)*x(i,k)CycleTimek=lMODE1.:!装配线平衡模型；SETS:!任务集合，有一个完成时间属性T；TASK/ABCDEFGHIJK:T;!任务之间的优先关系集合(A必需完成才能起先B,等等)；PRED(TASK,TASK)/A,BB,CC,FC,GF,JG,JJ,KD,EE,HE,IH,JI,J/;!工作站集合；STATION/1.4/;TXS(TASK,STATION):X;!X是派生集合TXS的一个属性。假如X(1.K)=1,则表示第I个任务指派给第K个工作站完成；ENDSETSDATA:!任务ABcdefghijK的完成时间估计如下；T=4511950151212121289;ENDDATA!当任务超过15个时，模型的求解将变得很慢；!每一个作业必需指派到一个工作站，即满意约束；FoR(TSK(I):SUM(STATION(K):X(I,K)=1);!对于每一个存在优先关系的作业对来说，前者对应的工作站I必需小于后者对应的工作站J,即满意约束；l'0R(PRED(I,J):SUM(STATION(K):K*X(J,K)-K*X(I,K)>=0);!对于每一个工作站来说，其花费时间必需不大于装配线周期；FOR(STATION(K):SUI(TXS(I,K):T(I)*X(I,K)<=CYCTIME);!目标函数是最小化转配线周期；MIN=CYCTIME;!指定X(1.J)为0/1变量；FOR(TXS:BIN(X);END计算的部分结果为Globaloptimalsolutionfound.Objectivevalue:50.00000Extendedsolversteps:2Totalsolveriterations:388VariableValueReducedCostCYCTIME50.000000.000000T（八）45.000000.000000T(B)11.000000.000000T(C)9.0000000.000000T(D)50.000000.000000T(E)15.000000.000000T(F)12.000000.000000T(G)12.000000.000000T（三）12.000000.000000T(I)12.000000.000000T(J)8.0000000.000000T(K)9.0000000.000000X(A,1)1.0000000.000000X(Az2)0.00000045.00000X(A,3)0.0000000.000000X(Az4)0.0000000.000000X(Bz1)0.0000000.000000X(Bz2)0.00000011.00000X(B,3)1.0000000.000000X(Bz4)0.0000000.000000X(C,1)0.0000000.000000X(C,2)0.0000009.000000X(C,3)0.0000000.000000X(C,4)1.0000000.000000X(Dz1)0.0000000.000000X(D,2)1.00000050.00000X(D,3)0.0000000.000000X(D,4)0.0000000.000000X(Ez1)0.0000000.000000X(E,2)0.00000015.00000X(E,3)1.0000000.000000X(E,4)0.0000000.000000X(F/D0.0000000.000000X(F,2)0.00000012.00000X(F,3)0.0000000.000000X(F,4)1.0000000.000000X(G,1)0.0000000.000000X(G,2)0.00000012.00000X(G,3)0.0000000.000000X(G,4)1.0000000.000000X(H,D0.0000000.000000X(H,2)0.00000012.00000X(H,3)1.0000000.000000X(H,4)0.0000000.000000X(工，D0.0000000.000000X(I,2)0.00000012.00000X(I,3)1.0000000.000000X(I,4)0.0000000.000000X(JfD0.0000000.000000X(J,2)0.0000008.000000X(J,3)0.0000000.000000X(Jf4)1.0000000.000000X(K,D0.0000000.000000X(K,2)0.0000009.000000X(K,3)0.0000000.000000X(K,4)1.0000000.000000（A,1）即A任务支配到1号工作站，并用时45分钟（B,3）即B任务支配到3号工作站，用时11分钟（D,2）即D任务支配到2号工作站，用时9分钟（E,3）即E任务支配到3号工作站,但E任务需在B任务完成后运行，从而，E任务完成后时间为15+11=26分钟（K,4）即K任务支配到4号工作站，并在C,F,G,J,完成后再运行，即最终完成时间为9+12+12+9=42分钟最终比较四个工作站完成任务所用时间总和，分别为：1号：45min,2号：50min,3号：50min,4号：42mino故装配线最短周期为50min.
