3 模型的建立与求解
3.1 目标建立
因为不同产品的不同工序被安排在不同的设备生产,而 每件产品又必须按
规定的工序加工,即同一产品必须加工完前面的工序才能投入下一个工序的加
工,而不得颠倒。为了统计与运算方便,因此我们把安排在同一设备的不同产品
的不
同工序用一个表列出来,如下:
同一设备的不同产品工序
上表中的第一行数字表示每个要在同一台设备生产的任务的个数,第一列
表
示不同的设备号,符号
( )
y
x,
中的 x 表示第几个产品, y 表示第 x 个产品第几个
工序。例如,
( )
2
,
1
表示第
1 个产品的第 2 道工序,而
( )
2
,
1
在整个表的意思就是在
对应行对应第一个设备上加工的第
1 个产品的第 2 道工序。
每台设备的生产安排有
!
n 种
,其中 n 代表每台设备要安排的工序个数,每一种
安排
, 由于每一台设备
i
u 将要加工相应产品的工序
m
i
x
,
是已知的,它是一个有限
集合。对于每一台设备
i
u 将要加工集合元素的每一个排序,只要符合同一产品不
同的工序在这个排序中先后完成时间的顺序不变,称为可行排序。它是该设备可
以对这个排序各工序进行处理的一种排序。同一设备的每一可行排序都可以找出
相应范围的处理时间,我们可以取其最小的一个值(相应范围的下界)作为表
示这个排序
k 的一个特性。不妨令这个时间为相应排列的最小工作时间
ik
t 。所以,
对于第
i 台设备的每一个可行排序
ik
l ,对应于一个最小工作时间
ik
t ,令它们之
间所确立的影射为
i
f 即
ik
f
ik
t
l
i
→
提高生产的运行效率,每一台设备的开始运行时间是相同的。为此,由上述
设
备
号
1
2
3
4
5
6
7
8
9
1 0
1
(1,
2)
(2,
1)
(3,
3)
(3,
5)
(4,
4)
(5,
5)
(6,
1)
(6,
3)
(6,
6)
(6,
8)
2
(1,
3)
(2,
3)
(3,
4)
(4,
1)
(5,
2)
(6,
2)
3
(1,
1)
(1,
4)
(2,
4)
(3,
1)
(4,
2)
(4,
6)
(5,
3)
(5,
6)
(6,
4)
(6,
7)
4
(1,
5)
(2,
2)
(3,
2)
(4,
3)
(4,
5)
(5,
1)
(5,
4)
(5,
7)
(6,
5)