随机型排序问题－加工时间等参数为随机变量
12
2.5 排序问题的四参数表示方法-Conway
n / m/ A/ B
零件数 机器数 车间类型 目标函数
F：流水线作业排序问题 P：流水线作业排列排序问题 G：一般单件作业排序问题 B：目标函数，通常是使其最小
N个零件经过3台设备加工的流水作业排
n / 3/ P / Cmax
注明
设备空闲时间
20
3.4 甘特图的优点
① 图形化概要，通用技术，易于理解； ② 中小型项目一般不超过30项活动； ③ 有专业软件（微软项目管理软件 (Microsoft Project）支持，无须担心 复杂计算和分析。
21
3.5 甘特图的不足
甘特图事实上仅仅部分地反映了项目管 理的三重约束（时间、成本和范围）， 因为它主要关注进程管理（时间）； 软件的不足。尽管能够通过项目管理软 件描绘出项目活动的内在关系，但是如 果关系过多，纷繁芜杂的线图必将增加 甘特图的阅读难度；
1 1 8 4
1
i k 3 1 / 2 pik pi1 pi 3
1 p11 p13 1 4 3 2 3，3 2，4 1
k 1
2
得到加工工序F max＝28
（1，2，3，4）或（2， 1， 3，4）
40
14
甘特图
15
3.2 甘特图的含义-1
甘特图内在思想简单，基本是一条线条图， 横轴表示时间，纵轴表示活动(项目)，线 条表示在整个期间上计划和实际的活动完 成情况。它直观地表明任务计划在什么时 候进行，及实际进展与计划要求的对比。
管理者由此极为便利地弄清一项任务(项目) 还剩下哪些工作要做，并可评估工作是提 前还是滞后，亦或正常进行。是一种理想 的控制工具。
23
4.1 加工周期的计算-2
① 按给出的顺序S列出加工时间矩阵。 ② 将每个零件的完工时间标在其右上角。


对于第一行第一列的元素其完工时间为自身加工时间；
对于第一行的其它元素，只需从左到右依次将上一列的数值加 上计算列的加工时间；


对于第一列的其它元素，只需从上到下依次将上一行的数值加 上计算行的加工时间；
对加工时间 pik 和 pik用Johnson算法
k 1 k m 1l l m
求m-1次加工顺序，求其中最好。
l 1, 2,, m 1
43
4.3.3 CDS法－穷举法-2
穷举法的操作步骤如下：
• 取首末两道工序，用约翰逊法排序，求F max
• •
•
取首两道工序的和及尾两道工序的和，用约 翰逊法排序，求F max 取首三道工序的和及尾三道工序的和，用约 翰逊法排序，求F max
1.7
2.6 1.0
D
1.8
3.0
29
0
工作中心1 工作中心2 A 2.5
2.5
B 3.8
6.3
C B 1.9 2.6
8.2
D 1.8 C 1.0
10
A 1.7
D
3.0
4.2
8.9
9.9
13
i Pi1 Pi2
A B 2.52.5 3.86.3 1.74.2 2.68.9
C 1.98.2 1.09.9

Used to describe the work sequence on each machine
Work Center Sheet Metal Mechanical Electrical Painting M Job A Job D Job B Job C Job E T W Th Job F Job G Job H Job I F
D 1.810 3.013
30
工作
数据输入时间（h） 核对时间（h）
A
B C D
2.5
3.8 1.9 1.8
1.7
2.6 1.0 3.0
排序方案：
——C
31
工作
数据输入时间（h） 核对时间（h）
A
B
2.5
3.8
1.7
2.6
D
1.8
3.0
排序方案：
——A ——C
32
工作
数据输入时间（h） 核对时间（h）
Pi1
Pi2
1
8
2
4
6
2
3
9
Pi3
Pi
1
2 3
4
13
5
11
8
16
2
14
max pi 16, C 3 Sa (1, 2) Sb (4) (1, 2,3, 4)
42
4.3.3 CDS法－穷举法-1
坎贝尔（Campbell）、杜德克 （Dudek）、史密斯（Smith）三人 提出了一个启发式算法。是Johnson 算法解一般n /m /P /F max的运用。
3
？MRP后企业该干什么
通过MRP确定各车间的零部件投入 出产计划，从而将全厂性的产品出产 计划变成了各车间的生产任务。 各车间要完成生产任务还必须将零部 件投入出产计划转化为车间生产作业 计划，将计划安排到具体的机器和个 人。因而牵涉到任务分配和作业排序 问题。
4
任务分配问题
假定甲单位有甲、乙、丙、丁、戊五 个员工，需要在一定的生产技术组织 条件下，完成A、B、C、D、E五项 任务，每个员工完成每项工作所需要 耗费的工作时间不同。 问：员工与任务之间应当如何进行配 置，才能保证完成工作任务的时间最 短？
1.8
B 3.8
5.6
A 2.5 2.6
8.1
C 1.9 A 1.7
10
工作中心2
D 3.0
B
C 1.0
4.8
8.2
9.9
11
原方案：D—B—A—C
0
工作中心1 工作中心2 A 2.5
2.5
B 3.8
6.3
C B 1.9 2.6
8.2
D 1.8 C 1.0
10
A 1.7
D
3.0
4.2
8.9
9.9
13
5
作业排序问题
1
拟稿时间 8小时
2
5小时
3
7小时
审稿时间
4.5小时
8.5小时
4.5小时
？从哪一项工作开始
6
1 车间作业管理的工作内容
核实MRP产生的计划清单
检查物料、能力、工具等的可用性
下达生产订单
说明零件加工工序顺序和时间
监控在制品生产 与车间生产相关的其它工作
7
2 生产作业计划 2.1 编制生产作业计划的实质-1
35
？从哪一项工作开始
1
拟稿时间 8小时
2
5小时
3
7小时
审稿时间
4.5小时
8.5小时
4.5小时
36
工作 A B C
拟稿时间（h） 8 5 7
审稿时间（h） 4.5 8.5 4.5
试求1、最优排序方案 B—C—A /B—A—C 2、不同排序方案下的Fmax 24.5
26
37
4.3 一般n/m/P/Fmax问题的启发式算法
对于其它元素则要从本行前一列右上角数字和本列上一行的右 上角数字中取大者，加上元素的加工时间。
③ 最后一行的最后一列右上角数字，即为加工周期。
24
例：
有一个6/4/P/Fmax问题，其加工时间如 下表，当按照顺序S=（6，1，5，2，4， 3）加工时，求Fmax
i Pi1 Pi2 Pi3 Pi4 1 4 4 5 4 2 2 5 8 2 3 3 6 7 4 4 1 7 5 3 5 4 4 5 3 6 2 5 5 1
• 单件作业排序问题 (Job-Shop)
－零件加工路线不同
• 流水作业排序问题 (Flow-Shop)
－所有零件的加工路线完全相同
11
2.4 排程问题的分类-2
按工件到达车间的情况不同
静态排序问题－所有零件都已到达，一次排序 动态排序问题－零件陆续到达，随时排序
按参数的性质
确定型排序问题－加工时间等参数为已知量
列排序问题，目标函数是使最长完工时 间C最短
13
3 作业排序的一般方法－－甘特图 3.1 概述
甘特图（Gantt chart ）又叫横道图、条状 图(Bar chart)。它是以图示的方式通过活 动列表和时间刻度形象地表示出任何特定 项目的活动顺序与持续时间。 它是在第一次世界大战时期发明的，以亨 利· 甘特先生的名字命名，他制定了一个 L· 完整地用条形图表示进度的标志系统。由 于甘特图形象简单，在简单、短期的项目 中，甘特图都得到了最广泛的运用。
将资源分配给不同的任务，按照既定 的优化目标，确定各种资源利用的时 间问题，包括确定零部件产品的加工 顺序，加工任务的分配和加工每件零 件开始时间和完成时间的确定。
8
2.2 有关的名词术语
排序
确定零件在机器上的加工顺序。
调度
作业计划编制之后实施生产控制采取的一切 行动。
派工
在作业计划制定后，按照作业计划要求，将 具体的生产任务分配到具体的机床和工人。
8.5小时
4.5小时
27
4.2 2台机器排序问题的最优算法
n/2/P/Fmax
J1 J2 J3 J4
1
2
优先规则： Johnson 规则 列好时间表，从中选最小； 若在第一列，将其排在首； 若在第二列，将其排在尾。
28
工作中心1
工作中心2
工作 A
B C
数据输入时间（h） 核对时间（h） 2.5