关键字
:
映射；有限集合；最小工作时间
1 问题的提出
能源问题是当今社会最主要的问题，时间观念强也是现代人的主要特点。有
“
”
一句很流行话已经成为很多人的口头禅了，那就是 时间就是金钱。 。所以在生
产产品时，一般商家都会遵守这个原则。安排生产时，由于设备的数量、产品加
工的次序限制，往往不能简单而有效地安排生产任务，但又要尽可能快和尽可
能少等待时间地安排任务，因为等待的时间越长，机器消耗的能量就越多。
例如，某重型机械厂产品都是单件性的 加工周期如下表：（
S—设备号、T
—周期）
产 工序
品
1
2
3
4
5
6
7
8
S T
S
T
S
T
S
T
S
T
S
T
S
T
S
T
1
3
8
1
2
2
4
3
24 4
6
2
1
4
4
5
2
3
3
4
3
3
3
4
7
1
15 2
20 1
8
4
2
7
3
6
4
21 1
1
4
16 3
3
5
4
10 2
4
3
8
4
4
1
12 3
6
4
1
6
1
1
2
4
1
7
3
3
4
5
1
2
3
5
1
8
要求：
1、每件产品必须按规定的工序加工，不得颠倒。
2、每台设备在同一时间只能担任一项任务。（每件产品的每个工序为一 个
任务）。
问题：做出生产安排，希望在尽可能短的时间里，完成所接受的全部任务。
要求：
1、做出每件产品的每个工序开工、完工时间表。
2、给出每台设备承担任务的时间表。
2 问题的假设和符号说明
2．1 模型的假设
(1)．假设机器不会因出现故障而停工的情况。
(2)．假设每一个设备，上一个工序完工后可以马上进行下一个工序的加工。
2．2 符号说明
i
u ：第
i
台设备
(
4
,
2
,
1
=
i
)
kj
T ：第
k
件产品的第 j 道工序的加工周期
(
8
2
,
1
6
2
,
1
=
=
j
k
)
ik
l ：第i 台设备的第
k
个可行排列
ik
t 对于第i 台设备的每一个可行排序
ik
l ，对应于一个最小工作时间