流水作业排列排序问题18页PPT

7
7
14
9
6 6
1
8 3
3
2 9
7
5
31
39
5
9 4
5 19
2 46
2、两台机器排序问题
两台机器排序的目标是使最大完成时间（总 加工周期）Fmax最短 。 实现两台机器排序的最大完成时间Fmax最短 的目标，一优化算法就是著名的约翰逊法 (Johnson’s Law)。其具体求解过程如下例所 示。
1
2 1 8
5
8 7 22
6
10 10 30
机器3
机器4 总和
pi3
pi4
练习
J5
机器1 机器2 pi1 pi2 2 2 7 15 3
J2
5 15 17 4
J6
9 21 31 8
J1
17 23 36
J3
J4
5 22 4 26
5
8
8
2
6
10
2
5
2
1
25 37
1
2
27 39
机器3
机器4
pi3
pi4
7 22 5 27 10 41 5 46 4 50 1 51
–顺序移动方式：一批零件全部加工完成后， 整批移动到下道工序加工 –平行移动方式：单个零件加工完成后，立 即移动到下道工序加工 –平行顺序移动方式：两者混合
2、排序问题的表示法
排序问题常用四个符号来描述: n/m/A/B 其中, n-----工件数； m-----机器数； A----车间类型； F=流水型排序， P=排列排序 G=一般类型,即单件型排序 B-----目标函数
三、流水作业排序问题
1、最长流程时间Fmax的计算 举例：有一个6/4/p/ Fmax问题，其加工时 间如下表所示。当按顺序S＝（6，1，5， 2，4，3）加工时，求Fmax。

件。 ⑺ MOPNR：优先选择余下工序数最多的工件。
作业排序管理
例12-1
生产任务编 J1
J2
J3
J4
J5
J6
号Ji
加工时间ti
4
8
2
5
9
3
(天)
预定交货期 24 23
8
di (天)
6 32 13
作业排序管理
• 加工顺序为： J3 —J6 —J1 —J4 —J2 —J5
生产任务编 J3
J6
J1
J4
作业排序管理
⑴ FCFS规则：优先选择最早到达的工件。 ⑵ SPT规则：优先选择加工时间最短的工件。 ⑶ EDD规则：优先选择交货期最短的工件。 ⑷ SCR：优先选择临界比最小的工件。临界比
为工件允许停留时间和工件余下加工时间之比。 ⑸ MWKR规则：优先选择余下加工时间最长的
工件。 ⑹ LWKR规则：优先选择余下加工时间最短的工
生产任务编 J4
J3
J6
J2
J1
J5
号Ji
完成时间Ci
5
(天)
7 10 18 22 31
交货延期量 0
0
0
0
0
0
Li (天)
最大延期量和平均延期量均为零，而平均流程时间为：
F 1 6i 6 1F i1 65 7 1 0 1 8 2 2 3 1 1.5 5
作业排序管理
（一）两台设备的流水型排序问题 1、排序方法： 约翰逊—贝尔曼规则
J2
J5
号Ji
完成时间Ci
2
5
9 14 22 31
(天)
交货延期量 0
0
0
8
0

第十三章 作业排序
精选
1
作业排序的概念
作业排序是主生产计划的具体执行 计划。它是在物料需求计划的牵引下， 把企业全年的生产任务具体地分配到各 工作地(车间、工段、班组以至每台设备 和工人），规定他们在月、旬、周、日 以至轮班和小时内的具体生产任务，从 而保证按品种、质量、数量、期限和成 本完成企业的生产任务。
P277
精选
8
加工顺序—甘特图
一、作业进度甘特图 二、机器甘特图
精选
9
多工件、单工作地调度方法
精选
10
多工件、两工作地调度方法
精选
11
生产控制概述
一、生产控制系统的特点 输入－转换－输出联系着计划、组
织、和控制三个职能，三者之间的整体 配合协调是必需的。
进度、质量、库存、成本四种控制 之间的关系
精选
12
二、生产进度控制 1．投入进度控制 2．过程进度控制 3．出产进度控制
精选
13
三、影响生产进度的原因 1．企业内部因素 2．设备故障 3．停工待料 4．质量问题 5．员工缺勤
精选
14
精选
15
精选
16
精选
17
精选
18
精选
19
精选
20
精选
21
精选
22
精选
4Байду номын сангаас
作业工作地的确定
N
0层
A(1)
1
B(2)
C(2)
2
D(3) E(1) F (3) D(3) E(1) D(2) 3
G(3kg) H(2.5) H(2.5) G(3kg) H(2.5) G(3kg) 4

作业：用Palmer法求解
2、关键工件法
（1）计算每个工件的总加工时间，找出加工时间最长 的工件C，将其作为关键工件； （2）对于余下的工件若Pi1≤Pim，则按Pi1 不减的顺序排 成一个序列Sa ，若Pi1＞Pim， 则按Pim 不增的顺序排列成 一个序列Sb。 （3）顺序（ Sa，C，Sb）即为所求顺序。
K = 1
m
i [k (3 1) / 2]Pik
k 1
m
i [k 2]Pik
k 1
m
=(1-2) Pi1+(2-2) Pi2+(3-2) Pi3
=- P i1 + P i3
λi =- P i1 + P i3 λ1 = - P 11 + P 13= -1+4 = 3 λ2 = -P21 + P23= -2 + 5= 3 λ3 =- P31 + P33 = -6 + 8 = 2 λ4 =-P 41+P43 = -3 + 2 = -1 按λi不增的顺序排列，得到加工顺序 （1，2，3，4）和（2，1，3，4）， 两者均为最优顺序，Fmax=28。
例：有一个4/3/P/ Fmax 问题，其加工时间如下 表所示，用Palmer法求解。
表11 加工时间矩阵 -5 i Pi1 Pi2 Pi3 1 1 8 4 2 2 4 5 3 6 2 8 4 3 9 2
解
i [k (m 1) / 2]Pik , (k 1,2,3, )
k 1
M2
M3 M4
t1 t2 t3 t T平顺
4
时间 第1个工序的所有工件加工完成的时刻为基准，向前推（n-1）个t2时间，作为

5个零件的加工任务，每个 工件在设备上的加工时间如下表所示。求总 加工周期最短的作业顺序。 •
设备 \工件编号
J1
J2
J3
J4
J5
设备A 设备B
3 2
6 8
7 6
1 4
5 3
求解过程
由约翰逊法可知，表5-8中最小加工时间值是1个时间单位，它又是 出现在设备1上，根据约翰逊法的规则，应将对应的工件4排在 第一位，即得： J4 - * - * - * - * 去掉 J4，在剩余的工件中再找最小值，不难看出，最小值是 2个 时间单位，它是出现在设备 2 上的，所以应将对应的工件 J1 排 在最后一位，即： J4 - * - * - * - J1 再去掉 J1，在剩余的 J2、J3、J5 中重复上述步骤，求解过程为： J4 - * - * - J5 - J1 J4 - J2 - * - J5 - J1 J4 - J2 - J3- J5 - J1 当同时出现多个最小值时，可从中任选一个。最后得 J4 - J2 - J3- J5 - J1
(a) J1 - J2 - J3- J4 - J5
A
B
30
(b) J4 - J2 - J3- J5 - J1
A
B
26
比较
可以看出，初始作业顺序的总加工周期 是30，用约翰逊法排出的作业顺序总加工 周期是26，显然后者的结果优于前者。
两台机器排序问题的算法（续）
I Ai Bi 1 5 7 2 1 2 3 8 2 4 5 4 5 3 7 6 4 4
10
2 2 20 5 30 8 32 2
12
4 1 27 7 35 5 38 3
13
3 3 33 6 42 7 46 4

生产任务编 J4
J3
J6
J2
J1
J5
号Ji
完成时间Ci
5
(天)
7 10 18 22 31
交货延期量 0
0
0
0
0
0
Li (天)
最大延期量和平均延期量均为零，而平均流程时间为：
F 1 6i 6 1F i1 65 7 1 0 1 8 2 2 3 1 1.5 5
作业排序管理
（一）两台设备的流水型排序问题 1、排序方法： 约翰逊—贝尔曼规则
作业排序管理
一、排序问题的假设 ⑴ 一个工件不能同时在几台机器上加工； ⑵ 每台机器同时只能加工一个工件； ⑶ 每道工序只在一台机器上完成； ⑷ 工件在加工过程中采取平行移动方式； ⑸ 工件在加工过程中不允许中断； ⑹ 工件数、机器数和加工时间均已知；
作业排序管理
• 总流程时间最短； • 平均流程时间最短； • 最大延迟时间或最大误期最短； • 平均延迟或平均误期最短； • 平均在制品占用量最小； • 总调整时间最小；
3) 将第1、2、3台设备的加工时间合并、第 （m-2）、（m-1）、m台设备上的加工时 间合并，所得到的两组加工时间，排出方 案3；
作业排序管理
4) 重复以上运算。最后将第1、2、…、 （m-1）台共（m-1）台机床的加工时 间合并，第2、3、…、m台共（m-1） 台机床的加工时间合并，所得到的两组 加工时间，排出方案m-1；
件。 ⑺ MOPNR：优先选择余下工序数最多的工件。
作业排序管理
例12-1
生产任务编 J1
J2
J3
J4
J5
J6
号Ji
加工时间ti
4
8
2

39、没有不老的誓言，没有不变的承 诺，踏 上旅途 ，义无 反顾。 40、对时间的价值没有没有深切认识 的人， 决不会 坚韧勤 l 62、少而好学，如日出之阳；壮而好学 ，如日 中之光 ；志而 好学， 如炳烛 之光。 ——刘 向 63、三军可夺帅也，匹夫不可夺志也。 ——孔 丘 64、人生就是学校。在那里，与其说好 的教师 是幸福 ，不如 说好的 教师是 不幸。 ——海 贝尔 65、接受挑战，就可以享受胜利的喜悦 。——杰纳勒 尔·乔治·S·巴顿
流水作业的排序问题
36、“不可能”这个字(法语是一个字 )，只 在愚人 的字典 中找得 到。--拿 破仑。 37、不要生气要争气，不要看破要突 破，不 要嫉妒 要欣赏 ，不要 托延要 积极， 不要心 动要行 动。 38、勤奋，机会，乐观是成功的三要 素。(注 意：传 统观念 认为勤 奋和机 会是成 功的要 素，但 是经过 统计学 和成功 人士的 分析得 出，乐 观是成 功的第 三要素 。
谢谢！

（3）单班次问题旳解析法 (Brownell and Lowerre,1976)
求解下列问题旳单班次人员安排问题： 1、确保每人每七天休息两天 2、确保每人每七天连休两天 3、确保每人每七天休息两天 ，隔一周在周末休息 4、确保每人每七天连休两天，隔一周在周末休息
1、确保每人每七天休息两天
■设某单位每七天工作7天，每天一班，日常日需要N人，周 末需要n人。 W表达所需劳动力下限。
2023/12/10
以上这些规则各有其特点，不同旳规则合用于不同旳 目旳。例如，FCFS规则比较公平；SPT规则可使平均流 程时间最短，从而降低在制品数量；EDD规则可使工件旳 最大延迟时间最小、平均延误时间最小；Moore法则可使 延迟旳工件数至少等。
2023/12/10
FCFS、SPT、EDD优先规则旳应用
第六章 生产作业排序
2023/12/10
一、作业排序旳概念 作业排序就是拟定工件在设备上旳加工顺序，
使预定旳目旳得以实现旳过程。 二、作业排序旳目旳
1、总流程时间最短 流程时间=加工时间+等待时间+运送时间
2、平均流程时间最短 3、平均在制品占用量最小 4、最大延迟时间最短 5、平均延迟时间最短 6、延迟工件至少
仪器
Y1 Y2 Y3 Y4 Y5
工序1 工序2
12 4 22 5
5 15 10 3 16 8
Y2-Y1--Y4--Y5-Y3
作业排序成果旳图示：
04
16
31 41 46
机器空闲
工序1 Y2 Y1
Y4 Y5 Y3
工序2
Y2
Y1
Y4 Y5 Y3
0 4 9 16
38
54 62 65

j1
j2
j3
j4
j5
j6
j7
j8
2 3 5 8 6 7 12 3 11 7 10 9 5 4 3 2 11 13 12 15 16 11 12 14
9
求最优解条件，满足如下条件之一：
min ta, j maxtb, j min tc, j maxtb, j
10
上例中，满足条件： min tc, j max tb, j
的排序，用解析法求最优方案几乎是不可能的。
实践中多采用排序规则的方法，分别为每一生产设备 排序，或采用仿真方法进行排序。
例:两个工件在m台设备上加工的 RND问题：
J1 =
A(2) – B(1) – C(8) –D(2) 14
J2 = A(1) - D(4) - B(1) - C(4)
J2
C4
转换两台假想设备，结果如下表：
任务 Mg tgj Mh thj
j1
j2
j3
j4
j5
j6
j7
j8
13
10
15
17
11
11
15
5
22
20
22
24
21
15
15
16
用哈姆表算法计算流程时间
11
任务
j8
j2
j5
j6
j1
j3
j7
j4
Ma taj 3 3 6 7 2 5 12 8 3 6 12 19 21 26 38 46
B1
b’ b
D4
A1
a
0
21 AB
8 C
e d
c
2 D
J1

二、排序问题的分类和表示法
1、排序问题的分类：
• 根据机器数的多少 单台机器的排序问题 多台机器的排序问题 • 根据加工路线的特征 单件作业排序(Job Shop) 流水作业排序(Flow Shop) • 根据工件到达系统的情况 静态排序 动态排序
• 根据参数的性质 确定型排序 随机型排序 • 根据要实现的目标 单目标排序 多目标排序
具体做法是，对加工时间 Pik和
k 1 l
k m 1l
Pik
m
（ l=1，2，…，m-1），用 Johnson 算法求 （m-1)次加工顺序，取其中最好的结果。
举例
有一个4/3/P/Fmax问题，其加工时间如下 表所示，用Palmer法求解。
i Pi1 Pi2 Pi3
1 1 8 4
1
2 1 8
5
8 7 22
6
10 10 30
机器3
机器4 总和
pi3
pi4
练习
J5
机器1 机器2 pi1 pi2 2 2 7 15 3
J2
5 15 17 4
J6
9 21 31 8
J1
17 23 36
J3
J4
5 22
6
10
2
5
2
1
25 37
1
2
27 39
机器3
机器4
pi3
pi4
7 22 5 27 10 41 5 46 4 50 1 51
• • • • • •
将工件2排在第1位 将工件3排在第6位 将工件5排在第2位 将工件6排在第3位 将工件4排在第5位 将工件1排在第4位
2 2 2 2 2 2
5 5 5 5