请教一难题！感谢指点一二，谢谢！

szm1113 · 发表于 2003-8-9 05:43:41

生产计划安排：

  某重型机械厂产品都是单件性的，其中有一车间共有A，B，C，D四种不同设备，现接受6件产品的加工任务，每件产品接受的程序在指定的设备上加工，其工序与加工周期如下表：（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    C  8 A  2    B  4    C  24 D  6
2    A  4 D  5    B  3    C 4
3    C  3 D  7    A  15 B  20 A  8
4    B  7 C  6    D  21 A 1 D  16 C  3
5    D  10 B  4    C  8    D 4 A  12 C  6 D  1
6    A  1 B  4    A  7    C 3 D 5 A  2 C  5 A  8

条件：1、每件产品必须按规定的工序加工，不得颠倒。
   2、每台设备在同一时间只能担任一项任务。（每件产品的每个工序为一个任务）。
问题：做出生产安排，希望在尽可能短的时间里，完成所接受的全部任务。
要求：给出每台设备承担任务的时间表。

请问用何方法解比较适宜？

此题难度较大，哪位高手可指点一二呢？

谢谢！

wanswolf · 发表于 2003-8-9 05:50:02

我也不会,不好意思。

zyxwq · 发表于 2003-8-9 06:30:10

这个题好象属于线性规划的题了
我也搞不明白
看其他英雄的了
不好意思

懵懂 · 发表于 2003-8-13 04:02:53

这个题目在哪见过，好想属于图论。
回去帮你查查。不好意思，我没仔细看，下次来帮你罗

飞云0616 · 发表于 2003-8-13 04:13:31

不懂

踏雪有痕 · 发表于 2003-8-13 04:56:03

用图论好象简单一点

路过 · 发表于 2003-8-13 05:03:43

遍历试试

wolfgang · 发表于 2003-8-14 01:52:33

拓扑排序吧？找数据结构书看看。上面有现成的算法

happy2003 · 发表于 2003-8-14 02:46:39

是用图论知识解。
不过有些数据看出不懂，楼主能解释一下吗？

懵懂 · 发表于 2003-8-14 04:40:05

的确是用图论解
步过也属于线形规划

		自动登录	找回密码
密码			注-册-帐-号