生产线平衡问题的+Leapms线性规划方法

admin/2020-06-25

  第一类生产线平衡问题,第二类生产线平衡问题

  整数线性规划模型,+Leapms模型,直接求解,CPLEX求解

  装配生产线又叫做组装生产线, 是把产品的工艺做串行生产安排的流水生产线。一个产品的组装需要不同的工序来完成,且工序之间有先后次序要求。

  下表是Jackson, J. R. . (1956)给出一个产品工序的装配次序要求:

  工序

  执行时长

  紧前工序

  1

  6

  --

  2

  2

  1

  3

  5

  1

  4

  7

  1

  5

  1

  1

  6

  2

  2

  7

  3

  3,4,5

  8

  6

  6

  9

  5

  7

  10

  5

  8

  11

  4

  10,9

  上表也可以用有向图表示:

  

  生产线平衡问题的目的是:把工序划分成工作站,且满足工序紧前要求。优化目标有两种:(1)在生产节拍被指定时使得工作站数量最少;或(2)在工作站数量被限定情况下使得生产节拍最小。

  前一种目标被称为第一类生产线平衡问题,后一种目标被称为第二类生产线平衡问题。

  (1)问题

  已知工作站共有m=5个,工序共有n=11个,极小化生产节拍。

  (2)有向图的表达

  有向图可以表达为节点的点对集合,例如 e={ 1 2, 1 3, 1 4,...,10 11}

  第k条边的前后两个顶点一般被写成 a[k], 和 b[k]。第k条边被记为 (a[k], b[k])

  边的数目 ne 是 e 中元素数除以2,即:ne=_$(e)/2

  (3)决策变量

  设 x[i][j] 为0-1变量,表示工序j是否被分配给工作站i。其中i=1,...,m; j=1,...,n。

  (4)依赖变量

  设变量c为生产线的节拍

  (5)目标是极小化生产节拍,即:

  minimize c

  (6)约束1: 每个工序被分配给且仅被分配给一个工作站:

  sum{i=1,...,m} x[i][j]=1 | j=1,...,n

  (7)约束2:节拍大于等于任何一个工作站的执行时长:

  c >=sum{j=1,...,n}x[i][j]t[j] | i=1,...,m

  (8)约束3:对任何边k,如果其后节点b[k]被分配到工作站i,则其前节点 a[k] 必须被分配到 j=1,...,i 中的某个节点,即:

  x[i][b[k]] <=sum{j=1,...,i}x[j][a[k]] | i=1,...,m;k=1,...,ne



上一篇:武汉开车到乐山要多少公里,时间,过路费,油
下一篇:没有了