当前位置：文档之家 › 运筹学 第12章 排序与统筹方法

运筹学 第12章 排序与统筹方法

  • 格式：ppt
  • 大小：1.68 MB
  • 文档页数：54

下载文档原格式

  / 54

合集下载

运筹学答案_第_12_章__排序与统筹方法

运筹学答案_第_12_章__排序与统筹方法

第 12 章 排序与统筹方法
习题 1 解：各零件的平均停留时间为： 6p1+5p2 +4p3 +3p4 +2p5 + p1 6 由此公式可知，要让停留的平均时间最短，应该让加工时间越少的零件 排在越前面，加工时间越多的零件排在后面。 所以，此题的加工顺序为：3，7，6，4，1，2，5
习题 2 解：此题为两台机器，n 个零件模型，这种模型加工思路为：钻床上加工时v 1aFra bibliotekv 2
b
v4
c
d
v 3
设第 V 发生的时间为 x ，(V, V)间的工序提前完工的时间为 y
i
ij
目标函数 min f = 4.5(x4 −x1)+ 4y12 + y24 +4y23 + 2y34
s.t. x2 − x1 ≥3− y12 x3 − x2 ≥ 4− y23 x4 − x2 ≥7− y24 x4 − x3 ≥5− y34 x1 = 0 y12 ≤2 y23 ≤2 y24 ≤4 y34 ≤3 xi ≥ 0, yij ≥0
这个正态分布的均值 E(T) =12.08
2
2
2
其方差为：σ ＝σb ＋σd ＋σg ＝０.70 则σ ＝０.84
当以９８％的概率来保证工作如期完成时，即：φ(u) =0.98，所以 u=2.05
此时提前开始工作的时间Ｔ满足： T −12.08 =2.05 0.84
所以Ｔ＝13.8 ≈14
习题 7 解：最短的施工工时仍为４＋５＋６＝１５ 具体的施工措施如下：
以上 i=1，2，3，4； j=1，2，3，4 用管理运筹学软件中的线性规划部分求解，得到如下结果： minf=46.5 x1=0,x2=1, x3=5,x4=7,
运筹学排队论-文档资料

运筹学排队论-文档资料


系统服务类型 银行储蓄
飞机着陆或起飞 电话通话
卸货或装货 工序安排
计算机系统 机器维护
1
排队论的研究内容： （1）性态问题：研究排 各队 种系统的概率性， 规主 律要研究队长分等 布待 、时间 的分布和忙期分布等； （2）最优化问题：分态 为最 静优和动态最优者 ，指 前最优设计，后现 者有 指排队
Pn (t )表示在时刻 t、系统状态为 n的概率。
含 Pn (t )的关系式一般为微分差 分方程，其解成为瞬态 （ transient state ）解 ;
lim
t
Pn
(t)
P（n 如果存在）称为稳态
（ steady state ）解，或称统计平衡状
3、排队模型的分类 按排队系统中的 影三 响个 最特 大征进1行 95年 分 3 ， 类 D.G（ .Kend） a:ll （1）相继顾客到间 达的 间分 隔布 时； （2）服务时间的分布； （3）（并列）服数 务。 台的个
7
相应的模型用 Kendall 记号表示： X /Y /Z
其中， X , Y , Z分别表述上述三个特征 。 例如： M — 负指数分布（ M 为 Markov 的首字母） D — 确定型（ determinis tic ） E k — k阶爱尔朗（ erlang ）分布 GI — 一般相互独立（ general independen t）的间隔时间的分布 G — 一般（ general ）服务时间的分布 M / M / 1， D / M / c（ c个并列服务平台，但顾 客是一队）
需要知道单位时间内的 顾客到达数或相继到达 的间隔时间分布。
4）顾客的到达可以是相 互独立的，也可以是有 关联的。
5）输入过程可以是平稳 的，或称对时间是齐次 的，是指相继到达的间 隔时间分布和
运筹学12.1统筹图

运筹学12.1统筹图

2011-3-10
4
运筹学
Operations Research
事项：生产过程的始点，终点以及其中的两道或两道以上工 序的交点. 某一工序的开工时刻称为开工事项，完工时刻称为完工事项. 一个生产过程的最初开工时刻称为总开工事项，最终完工时 刻称为总完工事项. 在统筹图中，一般用弧来表示工序，用弧的起点和终点分布 来表示工序的开工事项和完工事项.
2011-3-10
2
运筹学
Operations Research
统筹方法成功应用的范例： （1）都江堰
2011-3-10
3
运筹学
Operations Research
（2）丁谓修皇城 祥符中，禁中火.时丁谓主营复宫室，患取土远，公乃命凿 通衢取土，不日皆成巨堑，乃决汴水入堑中，引诸道竹木牌 筏及船运杂材，尽自堑中入，至公门事毕，却以拆弃瓦砾灰 壤实于堑中，复为街衢，一举而三役济，计省费以亿万计. （3）60年代，修建钱塘江大桥（茅以升），“引滦入津” 工程等. 基本概念： 工序：一项有具体内容，需经过一定时间才能完成的生产 过程. 相邻的两个工序，前者称为后者的紧前工序，后者称为前 者的紧后工序.
A B C D E
2011-3-10
A,B C C
7
运筹学
Operations Research
统筹图的绘制规则： （1）图中不能含有有向圈；否则，会致使工序的先后顺序 混乱，此时，应重新分解工序.
应重新分解工序.
2011-3-10

8
运筹学
Operations Research
（2）图中任意两个顶点之间不能有重弧；否则，会致使工 序的先后顺序混乱，此时，应引入虚工序，并令虚工序的工 序时间为0. 工序 紧前工序
管理运筹学期末复习资料【韩伯棠】

管理运筹学期末复习资料【韩伯棠】

运筹学（Operational Research）复习资料第一章绪论一、名词解释1.运筹学：运筹学是应用分析、试验、量化的方法，对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。

二、选择题1.运筹学的主要分支包括（ABDE ）A图论B线性规划C非线性规划D整数规划E目标规划2. 最早运用运筹学理论的是（ A ）A . 二次世界大战期间，英国军事部门将运筹学运用到军事战略部署B . 美国最早将运筹学运用到农业和人口规划问题上C . 二次世界大战期间，英国政府将运筹学运用到政府制定计划D . 50年代，运筹学运用到研究人口，能源，粮食，第三世界经济发展等问题上第二章线性规划的图解法一、选择题/填空题1.线性规划标准式的特点：（1）目标函数最大化（2）约束条件为等式（3 决策变量为非负（4 ) 右端常数项为非负2. 在一定范围内，约束条件右边常数项增加一个单位：（1）如果对偶价格大于0，则其最优目标函数值得到改进，即求最大值时，最优目标函数值变得更大，求最小值时最优目标函数值变得更小。

（2）如果对偶价格小于0，则其最优目标函数值变坏，即求最大值时，最优目标函数值变小了；求最小值时，最优目标函数值变大了。

（3）如果对偶价格等于0，则其最优目标函数值不变。

3.LP模型（线性规划模型）三要素：（1）决策变量（2）约束条件（3）目标函数4. 数学模型中，“s·t”表示约束条件。

5. 将线性规划模型化成标准形式时，“≤”的约束条件要在不等式左端加上松弛变量。

6. 将线性规划模型化成标准形式时，“≥”的约束条件要在不等式左端减去剩余变量。

7．下列图形中阴影部分构成的集合是凸集的是A【解析】：如何判断是凸集？凸集：两点之间连线在图内凹集：两点之间连线在图外8. 线性规划问题有可行解且凸多边形无界，这时CA没有无界解 B 没有可行解 C 有无界解 D 有有限最优解9. 对于线性规划问题，下列说法正确的是（ D ）A. 线性规划问题可能没有可行解B. 在图解法上，线性规划问题的可行解区域都是“凸”区域C. 线性规划问题如有最优解，则最优解可在可行解区域顶点上到达D. 上述说法都正确第三章线性规划问题的计算机求解一、名词解释1.相差值：相应的决策变量的目标系数需要改进的数量，使得决策变量为正值。

《运筹学》排队论培训课件

《运筹学》排队论培训课件


一般的排队系统，都可由图12-1加以描述。
顾客源 顾客到来
排队结构 排队规则
服
服务规则
务 机
构
离去
排队系统
图12-1
➢排队系统的组成
排队系统都有输入过程、排队规则和 服务台等3个组成部分：
1、输入过程 这是指要求服务的顾客是按怎 样的规律到达排队系统的过程，有时也把 它称为顾客流．一般可以从3个方面来描述 输入过程。
3．忙期和闲期
忙期是指从顾客到达空闲着的服务机 构起，到服务机构再次成为空闲止的这段 时间，即服务机构连续忙的时间。这是个 随机变量，它关系到服务员的服务强度。
与忙期相对的是闲期，即服务机构连 续保持空闲的时间。在排队系统中，忙期 和闲期总是交替出现的。
除了上述几个基本数量指标外，还 会用到其他一些重要的指标：
设随机变量T服从以为参数的负指数分布，它
的分布函数为：
P (T
t
)
1 0,
e
t
,
t 0 t 0
方差：E(t ) 1/ 期望：Var (t ) 1/ 2
负指数分布的性质：
性质1 由条件概率公式容易证明 p{T t s|T s} p{T t }
这性质称为无记忆性。若T表示排队系统中顾客到达的 时间间隔，那么这个性质说明一个顾客到来所需要的 时间与过去一个顾客到来所需要的时间s无关，所以说 在这种情形下的顾客到达是纯随机的。
性质2 当单位时间内的顾客到达数服从以为平均数 的泊松分布时，则顾客相继到达的间隔时间T服从负 指数分布。
由性质2可知： 相继到达的间隔时间是独立且为相同 参数的负指数分布，与输入过程为泊松流（参数为 ） 是等价的。
根据负指数分布与泊松流的关系可以推导出，当服
管理运筹学期末复习资料【韩伯棠】

管理运筹学期末复习资料【韩伯棠】

运筹学（Operational Research）复习资料第一章绪论一、名词解释1.运筹学：运筹学是应用分析、试验、量化的方法，对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。

二、选择题1.运筹学的主要分支包括（ABDE ）A图论B线性规划C非线性规划D整数规划E目标规划2. 最早运用运筹学理论的是（ A ）A . 二次世界大战期间，英国军事部门将运筹学运用到军事战略部署B . 美国最早将运筹学运用到农业和人口规划问题上C . 二次世界大战期间，英国政府将运筹学运用到政府制定计划D . 50年代，运筹学运用到研究人口，能源，粮食，第三世界经济发展等问题上第二章线性规划的图解法一、选择题/填空题1.线性规划标准式的特点：（1）目标函数最大化（2）约束条件为等式（3 决策变量为非负（4 ) 右端常数项为非负2. 在一定范围内，约束条件右边常数项增加一个单位：（1）如果对偶价格大于0，则其最优目标函数值得到改进，即求最大值时，最优目标函数值变得更大，求最小值时最优目标函数值变得更小。

（2）如果对偶价格小于0，则其最优目标函数值变坏，即求最大值时，最优目标函数值变小了；求最小值时，最优目标函数值变大了。

（3）如果对偶价格等于0，则其最优目标函数值不变。

3.LP模型（线性规划模型）三要素：（1）决策变量（2）约束条件（3）目标函数4. 数学模型中，“s·t”表示约束条件。

5. 将线性规划模型化成标准形式时，“≤”的约束条件要在不等式左端加上松弛变量。

6. 将线性规划模型化成标准形式时，“≥”的约束条件要在不等式左端减去剩余变量。

7．下列图形中阴影部分构成的集合是凸集的是A【解析】：如何判断是凸集？凸集：两点之间连线在图内凹集：两点之间连线在图外8. 线性规划问题有可行解且凸多边形无界，这时CA没有无界解 B 没有可行解 C 有无界解 D 有有限最优解9. 对于线性规划问题，下列说法正确的是（ D ）A. 线性规划问题可能没有可行解B. 在图解法上，线性规划问题的可行解区域都是“凸”区域C. 线性规划问题如有最优解，则最优解可在可行解区域顶点上到达D. 上述说法都正确第三章线性规划问题的计算机求解一、名词解释1.相差值：相应的决策变量的目标系数需要改进的数量，使得决策变量为正值。

《统筹方法》ppt课件

《统筹方法》ppt课件


第一段1：
运用下定义的方法介绍了统筹方法;统领 全文
第二段214：
介绍统筹 方法的原 理及应用
第一层28：统筹方法的必要性 第二层911：抓住关键环节 第三层1214：合并次要环节
统筹方法
第三段1516：
总结全文;说明统筹方法的 现实作用
15
洗水壶
图表11 1 烧开水
洗茶壶 1
泡茶
1 洗茶杯
2 拿茶叶
通盘筹划
统筹方法
华罗庚
阅读课文;回答问题：
一 谈谈你对作者的认识 二 什么叫统筹方法 三 对烧水泡茶的事例;为什么先后作了三次分析 四 文中三幅图说明了什么 有何作用 五 文章用了哪些说明方法 语言有何特点
华罗庚
华罗庚1910年11月12日~1985年 6月12日;国际数学大师;中国科 学院院士;是中国解析数论 矩 阵几何学 典型群 自安函数论 等多方面研究的创始人和开拓 者 他为中国数学的发展作出了 无与伦比的贡献 被誉为中国现代数学之父 中国 数学之神;中国现代数学之父; 人民数学家
图表12
洗水壶——1——烧开水——1—5—
泡
洗茶壶茶杯 拿茶叶————4—
茶
1
1
2
15
图表13
4 34
1洗水壶2烧开水3 洗茶壶茶杯 拿茶 叶4泡茶
列图表分析
一 图表分别指向哪次泡茶 图表11：第二次泡茶 图表12和13：第三次泡茶 二 列图表和运用文字说明有什么区别 列
图表说明方法的作用 运用列图表的说明方法;可以起到一目了
然的效果
本文的说明方法简明 易懂
常用词语积累： 统筹 小题大做 卑之无甚高论 错综复杂 万事俱备;只欠东风 不无裨益
统筹方法;是一种安排工作进程的数学方 法 它的实用范围极广泛;在企业管理和基 本建设中;以及关系复杂的科研项目的组 织与管理中;都可以应用
排序与统筹方法

排序与统筹方法


时间——费用优化
• 正常完成：
– 完成工序j的正常所需时间为Tj – 直接费用为cj
• 最快速度完成：
– 完成工序j的最快速度完成所需时间为Tj’ – 直接费用为cj’
• 直接费用变动率kj：缩短工序j的一天工期所 ' 增加的直接费用 c j cj
kj Tj T
' j
时间——费用优化
• 解：设网络图上第i点发生的时间为xi，工序提前完 工的时间为yij min f=120y27+300y23+400y24+500y25+230y37+350y46+ 400y57+290y67 s.t. x2-x160-y12, x7-x2 45-y27, x3-x210-y23, x4-x220-y24 , x5-x240-y25, x7-x318-y37, x6-x430-y46 , x5-x40 , x7x515-y57, x7-x625-y67, x1 =0, x8 150, y120, y2715, y23 5, y24 10, y25 5, y37 8, y46 10, y575, y780, xi 0，yij 0.（对一切可能的i j)
1. 优先安排关键工序所需的资源。 2. 利用非关键工序的时差，错开各工序的开 始时间。 3. 统筹兼顾工程进度的要求和现有资源的限 制，多次综合平衡。
经过调整，我们让非关 键工序f从第80天开始， 工序h从第110天开始。 找到了时间-资源优化的 方案
58人 64人 42人 26人 65人
60
80
• 若上述工序都按最早开始时间安排，那么从 第60天至第135天的75天里，所需的机械加 工工人人数如下图：
税务-运筹学导论第八版12排队论 精品

税务-运筹学导论第八版12排队论 精品

不是一种优化理论。 而是用于度量排队系统的性能指标，如队列的平均等待时 间和服务设施的效率，这些度量指标可以用来设置服务设 施。 排队论的重点在于实际中排队分析结果的实施； 为了充分理解排队系统的实际问题，就需要了解相当的基 础理论背景。为此，首先介绍下构成排队系统的基本要素， 然后介绍两个重要分布(泊松和指数分布)的“完全随机” 性质。
分析排队系统的最终目的是为了对排队等待的顾客提供满意 的服务。 排队论主要研究服务设施的需求与用户延误之间的关系，其 在分析和规划城市服务设施扮演重要角色，例如地铁闸机的 设置、消防站及消防车的配置以及医疗救护点配置等等；在 工业上的用途包括生产线的设计及布置、加工设备的配置； 服务业中服务人员、柜台的设置及调配。
的顾客在不同队列之间来回排队，以缩短期望排队时间。 （后4种情况被认为是急躁型的顾客） 如果顾客到达模式不随时间改变（随机型到达模式的参 数不随时间变化），则认为是平稳的；反之则为非平稳 的。
15
12.2.2 服务台服务模式
服务率 • 以单位时间内服务的顾客数量 • 以服务一个顾客需要的时间
当讨论服务台服务时间（总假定排队系统是存在顾客要服务） • 确定型 • 随机型，在系统非空条件下服务台的概率分布
排队分析的结果可以用在费用优化模型中，即求两种费用(服 务费用和等待费用)之和的最小值。如下图
8
总费用
服务时 间成本
费用
最优服务水平
顾客等待 时间成本
服务水平
上图显示了一个典型的费用模型，使用费用模型的主要障碍 就是很难估计可靠的等待费用，特别是当人的行为成为操作 的有机组成部分时。
9
研究排队论的目的
（2）服务台服务模式（服务台服务方式）；
（3）排队规则；
第十二章排序与统筹

第十二章排序与统筹


§11.1 车间作业计划模型
如果按照 3、2、4、5、6、1 顺序加工零件， 也可以计算出各零件在车间的停留时间，如表所示
零件 加工时间Pi 停留时间Tj 零件 加工时间Pi 停留时间Tj
3
0.5
0.5
5
1.3
4.7
2
2.0
2.5
6
1.5
6.2
4
0.9
3.4
1
1.8
8
于是各零件平均停留时间为
0.5 2.5 3.4 4.7 6.2 8 4.2（ 2 小时） 6
第一
§11.1 车间作业计划模型
若最小数为 ai，则将零件 i 排在第一位加工； 若最小数为 bj，则将零件 j 排在最后一位加工。
零件 1 2 3 4 5
车床 1.5 2.0 1.0 1.25 0.75
磨床 0.5 0.25 1.75 2.5 1.25
零件加工顺序 第四 第五 第二
第一
§11.1 车间作业计划模型
设 a1， a2，…，an； 和 b1， b2，…，bn 分别是零件 1，2，…，n 在机器 A 和 B 上的加工时间，则使
得全部零件的总加工时间最短的排序算法为：
1). 找出加工时间 a1，a2，…，an，b1，b2，…，bn，中的
最小数。
2). 若最小数为 ai，则将零件 i 排在第一位加工，并从零件集
§11.1 车间作业计划模型
这样可以计算出按照 1、2、3、4、5、6 顺 序加工零件，各零件在车间的停留时间，如表所示
零件 加工时间Pi 停留时间Tj 零件 加工时间Pi 停留时间Tj
1
1.8
1.8
4
0.9
排序和统筹方法

排序和统筹方法


1
60
2
4
e 8 0
8
h 5
9
f
f 10 f g 10 16
0
3 b
15 a
5 d e
8 b,d
7 g
16 d
工序代号 所需时间 紧前工序
page 20 4 February 2016
a
60 —
c
13 a
f
10 d
h
5 e,f,g
38 c
Wu School of Economics
Operations Research
排序与统筹方法
注意：
网络图中不允许出现缺口和回路
1
a 60
2
b 15
4
e 8 0 f 10
8
h 5 0
9
c 13
3 4
d 38
5
g 16
7
4 2
3 1 page 21 2
3 1
4 February 2016
Wu School of Economics
Operations Research
排序与统筹方法
Wu School of Economics
Operations Research
排序与统筹方法
平行机问题：多台同样的机器
例：已知n个零件的加工时间，要在两台
同样的机器上加工这批零件， 如何安排它们的顺序，可以在最短时间内 完成这批零件的加工？ P2| |Tmax 如何安排它们的顺序，可以使零件的 总停留时间最短？ P2| | ∑Tj
管理者，常常要处理一些各个零件在一些机床上 加工的先后次序问题，能否在满足加工工艺流程 的前提下，通过各个零件在各台机床上加工次序 上的合理安排，在各种零件在每台机器上加工的 时间已知的条件下，使得完成这批零件加工任务 所需的总时间最少，能最早地将这批零件交付使 用，或者使得各加工零件在车间里停留的平均时 间最短……

第十二章排序与统筹-PPT精品


零件加工顺序 第四 第五
§11.1 车间作业计划模型
若最小数为 ai，则将零件 i 排在第一位加工； 若最小数为 bj，则将零件 j 排在最后一位加工。
零件 1 2 3 4 5
车床 1.5 2.0 1.0 1.25 0.75
磨床 0.5 0.25 1.75 2.5 1.25
零件加工顺序 第四 第五
磨床 0.5 0.25 1.75 2.5 1.25
零件加工顺序 第五
§11.1 车间作业计划模型
若最小数为 ai，则将零件 i 排在第一位加工； 若最小数为 bj，则将零件 j 排在最后一位加工。
零件 1 2 3 4 5
车床 1.5 2.0 1.0 1.25 0.75
磨床 0.5 0.25 1.75 2.5 1.25
按照某个加工顺序加工零件时，某个零件在车间的停留 时间应该等于在它前面加工的各个零件的加工时间与这 一零件本身的加工时间之和。
如果用 Pi 表示安排在第 i 位加工的零件所需的时间，
用 Tj 表示安排在第 j 位加工的零件总的停留时间，
则有
j
Tj P1P2 Pj Pi i1
§11.1 车间作业计划模型
第一
§11.1 车间作业计划模型
若最小数为 ai，则将零件 i 排在第一位加工； 若最小数为 bj，则将零件 j 排在最后一位加工。
零件 1 2 3 4 5
车床 1.5 2.0 1.0 1.25 0.75
磨床 0.5 0.25 1.75 2.5 1.25
零件加工顺序 第四 第五 第二
第一
§11.1 车间作业计划模型
§11.1 车间作业计划模型
要使6P1+5P2+ 4P3+ 3P4+ 2P5+ P6 的值为最小。

排序与统筹方法共34页PPT

排序与统筹方法
26、机遇对于有准备的头脑有特别的 亲和力 。 27、自信是人格的核心。
28、目标的坚定是性格中最必要的力 量泉源 之一， 也是成 功的利 器之一 。没有 它，天 才也会 在矛盾 无定的 迷径中 ，徒劳 无功。- -查士 德斐尔 爵士。 29、困难就是机遇。--温斯顿．丘吉 尔。 30、我奋斗，所以我快乐。--格林斯 潘。
45、自己的饭量自己知道。——苏联
பைடு நூலகம்
41、学问是异常珍贵的东西，从任何源泉吸 收都不可耻。——阿卜·日·法拉兹
42、只有在人群中间，才能认识自 己。——德国
43、重复别人所说的话，只需要教育； 而要挑战别人所说的话，则需要头脑。—— 玛丽·佩蒂博恩·普尔
44、卓越的人一大优点是：在不利与艰 难的遭遇里百折不饶。——贝多芬
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

管
理
运
筹
学
26
§2 统筹方法
解：据表12-10,绘制网络图如图12-8。
b 45 c
3
10 d 20 e
f 18
1
a
60
2
4
g 30
6 5
h
i 25
7
j 35
8
40
15
图12-8 如图12-8 ,①-②-③-⑦-⑧就是一条关键路线，我们要干完所有的工序 就必须走完所有这样的路线，由于很多工序可以同时进行，所以网络中最 长的路线就决定了完成整个工程所需的最少时间，这条路线称为关键路
图12-10
其次,从网络的收点开始计算出在不影响整个工程最早结束时间的情
况下各个工序的最晚开始时间(缩写为LS)和最晚结束时间（缩写为LF), 显然对同一工序有 LS=LF-t
管 理 运 筹 学
29
§2 统筹方法
运用此法则，可以从收点开始计算出每个工序的LF与LS，如图12-11 所示。
b[60,105] 45[90,135] c[60,70]
工序代号 a b c d e 工序内容 产品设计与工艺设计 外购配套零件 外购生产原料 自制主件 主配可靠性试验 所需时间（天) 60 15 13 38 8 紧前工序 a a c b,d
管
理
运
筹
学
19
§2 统筹方法
解:用网络图表示上述的工序进度表 网络图中的点表示一个事件,是一个或若干个工序的开始或结束,是相
工时间为0.5的零件1放到除第五外的加工顺序的末尾，即第四位加工，同时把 表中的零件1所在
的行划去。如表12-6中黄色线条所示。 下一个最短加工时间为0.75，这个加工时间是车床（第一工序）加工零件5的所需时间，故 把零件5排在加工顺序的第一位上，同时把表中的零件5所在的行划去。如表12-6中蓝色线条所
解：我们把工序ｆ扩充到图12-4发生了问题，由于ｄ是ｆ的紧前工 序，故ｄ的结束应该是ｆ的开始，所以代表ｆ的弧的起点应该是④，
由于工序ｂ的结束也是④，所以工序ｂ也成了工序ｆ的紧前工序，与
题意不符。 为此我们设立虚工序。虚工序是实际上并不存在而虚设的工序，
用来表示相邻工序的衔接关系，不需要人力、物力等资源与时间。
160[0,60] 2
a[0,60]
10[107,117] d[60.80] g[80,110]
3
f[70,88] 18[117,135]
20[60,80]
i[110.135] 4 30[80,110] 625[110,135]
7
j[135,170] 35[135,170]
8
e[60.100] 40[80,120]
线。
管 理 运 筹 学
27
§2 统筹方法
• 下面我们给出找关键路线的办法 首先，从网络的发点开始，按顺序计算出每个工序的最早开始时间 （ES )和最早结束时间（EF) ，设一个工序所需的时间为t，这对于同一 个工序来说，有 EF=ES+t。
工序a的最早 开始时间
工序a的最早 完成时间
1
a[0，60]
管 理 运 筹 学
4
§1
二、两台机器、n个零件
车间作业计划模型
例2.某工厂根据合同定做一些零件，这些零件要求先在车床上车削，然后再在 磨床上加工，每台机器上各零件加工时间如表12-5所示。
表12-5 零件 1 2 3 车床 1.5 2.0 1.0 磨床 0.5 0.25 1.75 零件 4 5 车床 1.25 0.75 磨床 2.5 1.25
1
a 60
2
13 c
b 15 d 38
图12-5
管 理 运 筹
5
e
8
f 4 10
6
3
学
22
§2 统筹方法
在网络图上添加ｇ、ｈ工序得网络图12-6。
1
a 60
2 13 c
b
15
d 38
图12-6
5 8 f
e
6 g 16 h 5 7 10
3
4
在统筹方法的网络图中不允许两个点之间多于一条弧，因此增加 了一个点和虚工序如图12-7。
管
理
运
筹
学
8
§2 统筹方法 用网络图编制的计划称为网络计划，网络计 划技术由计划协调技术（Program Evaluation and Review Technique 简写为 PERT）与关键路径法（Critical Path Method 简写为CPM）组成。
管
理
运
筹
学
9
基本概念
管
理
运
筹
学
10
60 图12-9
1
管
理
运
筹
学
28
§2 统筹方法
b[60,105] 45 f[70,88] 18
c[60,70]
1
a[0,60] 60
2
10 d[60.80] 20
3
4
g[80,110] 30
6
i[110.135] 25
7
j[135,170] 35
8
e[60.100] 40
5
h[100,115] 15
第十二章 排序与统筹方法
在本章中，我们将介绍车间作业计划模型和 统筹方法。这两个问题尽管处理的方法有所不同， 但当我们面临必须完成若干项不能同时进行的工 作时，它们都将帮助我们应该按照怎样的次序、 怎样的时间表来做这些工作，使得效果最佳（例 如完成全部工作所用时间最短或费用最少等等）。
§1 车间作业计划模型 §2 统筹方法
应该如何安排这五个零件的先后顺序才能使完成这五个零件的总的加工时间 为 最少？ 解：由于每个零件必须先进行车床加工，再进行磨床加工，所以在车床上加 工零件的顺序与在磨床上加工零件的顺序是一样的。
如果这些零件在车床上和磨床上加工顺序都为1，2，3，4，5。我们用图12-1
中的线条图来表示各零件加工的开始时间与完成时间，这种图是由一根时间轴和 车床、磨床在每个时间段的状况的图形所构成。
管 理 运 筹 学
25
§2 统筹方法
表12-10
工序代号 a b c d e f g h i j 工序内容 生产线设计 外购零配件 下料、锻件 工装制造1 木模、铸件 机械加工1 工装制造2 机械加工2 机械加工3 装配调试 所需时间（天） 60 45 10 20 40 18 30 15 25 35 紧前工序 / a a a a c d d,e g b,i,f,h
5
h[100,115]
15[120,135
接着，可以计算出每一个工序的时差，把在不影响工程最早结束时间 的条件下，工序最早开始（或结束）的时间可以推迟的时间，成为该工序 的时差，对每个工序来说其时差记为Ts有 Ts=LS-ES=LF-EF
i 1
可知这六个零件的停留时间为： T1 + T2 + T3 + T4 + T5 + T6 ＝ P 1 + ( P 1 + P 2 ) + (P 1 + P 2 + P 3 ) + (P 1 + P 2 + P 3 + P 4 ) + (P1 + P2 + P3 + P4 + P5) + (P1 + P2 + P3 + P4 + P5 + P6 ) ＝ 6 P1 + 5 P2 + 4P3 + 3P4 + 2P5 + P6. 6 P1 5 p 2 4 p 3 3 p 4 2 p 5 p 6 那么各个零件平均停留时间为 6 从上式可知，对于一台机器n个零件的排序问题，只要系数越大，配上加工时 间越少的，即按照加工时间排出加工顺序，加工时间越少的零件排在越前面，加工 时间越多的零件排在越后面，可使各个零件的平均停留时间为最少。
2、每个工序的开始时间与结束时间。 3、关键路线及其应用的关键工序。
4、非关键工序在不影响工程的完成时间的前提下，其开始时间与结束时
间可以推迟多久。 例5、某公司装配一条新的生产线，具体过程如表12-10,求：完成此 工程的最少时间，关键路线及相应的关键工序，各工序的最早开始时间和 非关键工序在不影响工程完成时间的前提下，其开始时间与结束时间可以 推迟多久。
示。
管 理 运 筹 学
7
§1
车间作业计划模型
同样，下一个最短加工时间为1，这是车床加工零件3的所需时间，故 把零件3排在第二位上，同时把零件3所在的行划去。如表12-6中黑色线条 所示。 这样就得到了最优加工顺序：5，3，4，1，2。一共只需7个小时就能 完成全部加工。 从例2中我们可以归纳出关于两台机器n个零件的排序问题，使得全部 任务总的时间 最短的排序算法。 在加工所需时间表上选出最短加工时间tij，这是第i工序加工j零件所 需 时间，当i=1时，将零件j的顺序尽量靠前，若i=2时，将零件j的顺序尽量 靠后。在表上划去零件j的所在行，回到步骤1。
管
理
运
筹
学
1
§1
车间作业计划模型
车间作业计划是指一个工厂生产工序的计划和安排。
一、一台机器、n个零件的排序问题
二、两台机器、n个零件的排序问题
管
理
运
筹
学
2
§1
车间作业计划模型
一、一台机器、n个零件的排序问题
例1.某车间只有一台高精度的磨床，常常出现很多零件同时要求这台
磨床加工的情况，现有六个零件同时要求加工，这六个零件加工所需时间
位，并在表中划去零件2 所在行。如表 表12-6 12-6中红色线条所示。