201规划作业0001

1、0-1 规划问题一条装配线由一系列工作站组成，被装配或制造的产品在装配线上流动的过程 中，每站都要完成一道或几道工序， 假定一共有六道工序， 这些工序按先后次序 在各工作站上完成，关于这些工序有如下的数据：工序所需时间（分）前驱工序13无25无322461，3582634另外工艺流程特别要求， 在任一给定的工作站上， 不管完成哪些工序， 可用的总 时间不能超过 10 分钟，如何将这些工序分配给各工作站，以使所需的工作站数 为最少？1）模型分析与变量的假设下面，我们先讨论工序与工作站的关系，并试图建立起该问题的01 型整数规划模型。对任一工序而言，它要么属于工作站 j ，要么不属于工作站 j ，

2、故决策变量 可定义为：1 若工序 i 在工作站 j 上运 行xij 0 若工序 i不在工作站 j 上运行这种定义，使我们能根据最优解中 xij 的值来很快确定工序 i 与工作站 j 之间 的隶属关系。又因工序 1，2，3 所需的工作时间不超过 10 分钟，故工序 1，2，3 的工作 可以在一个工作站上完成， 此时，工序 4，5，6 只能分别在各自的工作站上工作， 该可行解对应的工作站数为 4个。也就是说，对最优解而言， 该装配线上所需的 工作站个数不会多于 4 个。因此，我们再定义变量如下：1 若在最 优解中需要工作站 jwjj 0 若在最 优解 中不需要 工作站 j 至此，我们得到所需的目标

3、函数为：max z w1 w2 w3 w42）再考虑该模型的约束条件：（1）每道工序均隶属于一个工作站， 且每一工序都必须完成， 故有以下六 个约束：xi1 xi2 xi3 xi4 1 （i 1, 2, 3, 4, 5, 6）（2）在任一工作站上完成隶属工序所用的时间不能超过 10 分钟，故有以下 四个约束：3x1j 5x2 j 2x3j 6x4 j 8x5j 3x6 j 10 (j 1, 2, 3, 4)(3) 最后，我们再考虑各道工序所受的先后次序约束的条件。先考察工序 2 与工序 3 的关系，因工序 2 在工序 3 之前运行，故若工序 3隶属于工作站 4，则工序 2无论属于那个工作站均可

4、； 若工序 3 隶属于工作站 3， 则工序 2可属于工作站 1或2或 3；此时，变量 x2j (j 1, 2, 3) 应满足的约束条 件为：x 21 x22 x23 x33 ；同理，若工序 3隶属于工作站 2或1，则变量x2j (j 1, 2,3)应 满足的约束条件为：x 21 x22 x32x 21 x31同理，根据其它工序的优先关系， 可仿此法给出其相应的约束条件， 由上图 知，六个工序之间有五个优先关系，故这类约束条件共有 15 个。另外，在最优解中，若有一个工作站 wp(p 1, 2, 3, 4)不用(即 wp =0)，则 隶属于该工作站的全部 xip(i 1, 2,3, 4, 5,

5、6)必须为 0，于是，有以下四个约束 条件：x1j x2j x3j x4 j x5 j x6j 6wj (i 1, 2, 3, 4)3) 模型的建立与求解至此，我们得到了该问题的 01 型整数规划模型， 它共包含 28 个变量， 29 个约束条件，这样的模型用枚举法求解，人工计算是很难胜任的，这时，只能求 助于计算机求解了。我们给出该问题的模型如下。该问题的目标函数为：max z w1 w2 w 3 w4约束条件为：xi1 xi2 xi 3 xi4 1 (i 1, 2, 3, 4, 5, 6) 3x1j 5x2 j 2x3j 6x4 j 8x5j 3x6 j 10 (j 1, 2, 3, 4)

6、x22x32x 21 x31x22x52x21 x51 ；x12x42x11 x 41 ；x32x42x31 x41 ；x42x62x41 x61 ；x6 j6wj(i1, 2, 3, 4)x 21 x22 x 23 x33 ； x21 x 21 x22 x 23 x53 ； x21 x11 x12 x13 x43 ； x11 x31 x32 x33 x43 ； x31x 41 x42 x 43 x63 ； x41x1 j x2 j x3j x4j x5j一条装配线含有一系列的工作站 ,在最终产品的加工过程中每个工作站执行 一种或几种特定的任务 .装配线周期是指所有工作站完成分配给它们各自的任

7、务 所花费时间中的最大值 .平衡装配线的目标是为每个工作站分配加工任务 ,尽可能 使每个工作站执行相同数量的任务 ,其最终标准是装配线周期最短 .不适当的平衡 装配线将会产生瓶颈 有较少任务的工作站将被迫等待其前面分配了较多任务的工作站 .问题会因为众多任务间存在优先关系而变的更复杂,任务的分配必须服从这种优先关系 .这个模型的目标是最小化装配线周期 .有 2 类约束 :1 要保证每件任务只能也必须分配到一个工作站来加工 ;2 要保证满足任务间的所有优先关系 .装配线平衡模型 有 11件任务( AK)分配到 4个工作站( 14)，任务的优先 次序如下图。(A)(B)(D)(I)(K)每件任务所

8、花费的时间如下表。任务ABCDEFGHIJK时间4511950151212121289如何将这些工序分配给各工作站，以使装配线周期最短，最短周期为多少？1) 变量的假设 设：1，表示第 i 个任务指派给第 k个工作站完成x(i ，k)0，反之T(i) 为完成第 i 个任务所需时间。CycleTime 为装配线周期。2) 问题分析(1)目标函数装配线周期最短： min= CycleTime(2)再考虑该模型的约束条件： 每道工序均隶属于一个工作站，且每一工序都必须完成，故有以下几个约 束：x(i,1) x(i,2) x(i,3) x(i,4) 1,(i 1,2 11) 各道工序所受的先后次序约束

9、的条件： 对于每一个存在优先关系的作业对来说，前者对应的工作站 i 必须小于后 者对应的工作站 j，即满足约束4 k * x( j, k) - k * x( i, k)0，( i 为j 的前驱任务) k1对于每一个工作站来说，其花费时间必须不大于装配线周期：4T(i) * x( i, k) CycleTime k13) 模型的建立与求解至此，我们得到了该问题的 01 型整数规划模型，我们给出该问题的模型 如下。该问题的目标函数为：min= CycleTime约束条件为：x(i,1) x(i,2) x(i,3) x(i,4) 1,(i 1,2 11)4k * x( j, k) - k * x(

10、i, k)0，(i 为j 的前驱任务)k14T(i) * x( i, k) CycleTimek1MODE:L! 装配线平衡模型 ;SETS:! 任务集合，有一个完成时间属性T;TASK/ A B C D E F G H I J K/: T;! 任务之间的优先关系集合( A 必须完成才能开始 B，等等) ;PRED( TASK, TASK)/ A,B B,C C,F C,G F,J G,JJ,K D,E E,H E,I H,J I,J /;! 工作站集合 ;STATION/1.4/;TXS( TASK, STATION): X;! X 是派生集合 TXS的一个属性。如果 X( I ， K) 1

11、，则表示第 I 个任务指派给第 K 个工作站完成 ;ENDSETSDATA:! 任务 A B C D E F G H I J K 的完成时间估计如下 ;T = 45 11 9 50 15 12 12 12 12 8 9;ENDDATA! 当任务超过 15 个时，模型的求解将变得很慢 ;! 每一个作业必须指派到一个工作站，即满足约束;FO(R TASK( I): SU(M STATION( K): X( I, K) = 1);! 对于每一个存在优先关系的作业对来说，前者对应的工作站I 必须小于后者对应的工作站 J ，即满足约束 ;FO(R PRED( I, J):SU(M STATION( K)

12、: K * X( J, K) - K * X( I, K) = 0);! 对于每一个工作站来说，其花费时间必须不大于装配线周期;FO(R STATION( K):SU(M TXS( I, K): T( I) * X( I, K) = CYCTIME);! 目标函数是最小化转配线周期 ;MIN = CYCTIME;! 指定 X(I,J) 为 0/1 变量 ;FO(R TXS: BIN( X);END计算的部分结果为Global optimal solution found.Objective value:50.00000Extended solver steps:2Total solver it

13、erations:388CYCTIME50.000000.000000T( A)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( H)12.000000.000000T( I)12.000000.000000T( J)8.0000000.000000T( K)9.0000000.000000X( A, 1)1.0000000.000000X( A, 2)0.

14、00000045.00000X( A, 3)0.0000000.000000X( A, 4)0.0000000.000000X( B, 1)0.0000000.000000X( B, 2)0.00000011.00000X( B, 3)1.0000000.000000X( B, 4)0.0000000.000000X( C, 1)0.0000000.000000X( C, 2)0.0000009.000000X( C, 3)0.0000000.000000X( C, 4)1.0000000.000000X( D, 1)0.0000000.000000X( D, 2)1.00000050.000

15、00X( D, 3)0.0000000.000000X( D, 4)0.0000000.000000X( E, 1)0.0000000.000000X( E, 2)0.00000015.00000X( E, 3)1.0000000.000000X( E, 4)0.0000000.000000X( F, 1)0.0000000.000000X( F, 2)0.00000012.00000X( F, 3)0.0000000.000000X( F, 4)1.0000000.000000X( G, 1)0.0000000.000000VariableValue Reduced CostX( G, 2)

16、0.00000012.00000X( G, 3)0.0000000.000000X( G, 4)1.0000000.000000X( H, 1)0.0000000.000000X( H, 2)0.00000012.00000X( H, 3)1.0000000.000000X( H, 4)0.0000000.000000X( I, 1)0.0000000.000000X( I, 2)0.00000012.00000X( I, 3)1.0000000.000000X( I, 4)0.0000000.000000X( J, 1)0.0000000.000000X( J, 2)0.0000008.000000X( J, 3)0.0000000.000000X( J, 4)1.0000000.000000X( K, 1)0.0000000.000000X( K, 2)0.0000009.000000X( K, 3)0.0000000.000000X( K, 4)1.0000000.000000（A，1）即A任务安排到 1号工作站，并用时 45分钟（