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 ０

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）