当前位置：文档之家 › 作业排序例题

作业排序例题

  • 格式：pptx
  • 大小：171.33 KB
  • 文档页数：33

下载文档原格式

  / 33

合集下载

第10章 排序 作业

第10章 排序 作业

第10章排序一、填空题1. 大多数排序算法都有两个基本的操作：和。

2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较次。

3. 在插入和选择排序中，若初始数据基本正序，则应选用排序算法；若初始数据基本反序，则应选用排序算法。

4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用；若初始记录基本无序，则最好选用。

5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是。

若对其进行快速排序，在最坏的情况下所需要的时间是。

6. 对于n个记录的集合进行归并排序，所需要的平均时间是，所需要的附加空间是。

7．对于n个记录的表进行2路归并排序，整个归并排序需进行趟（遍）。

8. 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则：冒泡排序一趟扫描的结果是；初始步长为4的希尔（shell）排序一趟的结果是；归并排序一趟扫描的结果是；快速排序一趟扫描的结果是；堆排序初始建堆的结果是。

9. 分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表进行排序，则最省时间的是算法，最费时间的是算法。

10、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为。

二、单项选择题1、下列四个序列中，（）是堆。

A. 75,65,30,15,25,45,20,10B. 75,65,45,10,30,25,20,15C. 75,45,65,30,15,25,20,10D. 75,45,65,10,25,30,20,152．排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）Ａ. 希尔排序Ｂ. 冒泡排序Ｃ. 插入排序Ｄ. 选择排序3．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为（）Ａ. 希尔排序Ｂ. 归并排序Ｃ. 插入排序Ｄ. 选择排序4．对ｎ个不同的排序码进行冒泡排序，在下列（）情况下比较的次数最多。

作业排序优制材料

作业排序优制材料

i2
P
i3
p
i
i
1
2
3
4
P
i1
1
2
6
3
P
8
4
2
9
4
5
8
2
13
11
16
例：一批制品，批量n =4件，须经四道工序加工，各工序时间分别为：t1=10, t2=5, t3=15, t4=10。
n——加工批量； m——工序数目； ti——工件在第i工序的单件工时；
四、相同零件、不同移动方式下加工周期的计算
一批零件在上道工序全部加工完毕后,才整批转移 到下道工序加工。
n——加工批量； m——工序数目； ti——工件在第i工序的单件工时；
3、平行顺序移动方式
工序
M1
M2
M3
M4
T平顺
t2
t1
t3
时间
t4
第2种情况：ti≥ ti+1 考虑设备加工的连续性
第1个工序的所有工件加工完成的时刻为基准，向前推（n-1）个t2时间，作为第2个工序的开始时间。即从红线开始向前推3个作为第2个工序的开始时间。
3、平行顺序移动方式
x
T=nt1+t2+x+t4
k=1，2，3...m
例：有一个4/3/P/ Fmax 问题，其加工时间如下表所示，用Palmer法求解。
表
11
-
5
加工时间矩阵
i
1 2 3 4
P
i1
1 2 6 3
P
i2
8 4 2 9
二、n/2/F/Fmax问题的最优算法
（一）Johnson算法： ① 从加工时间矩阵中找出最短的加工时间。 ② 若最短的加工时间出现在M1上，则对应的零件尽可能往前排；若最短加工时间出现在M2上，则对应零件尽可能往后排。然后，从加工时间矩阵中划去已排序零件的加工时间。若最短加工时间有多个，则任挑一个 ③ 若所有零件都已排序，停止。否则，转步骤①。

作业排序管理(1)

作业排序管理(1)
3) 将已经排定的零件除去，再重复前两步， 直到全部零件排完为止。
例12-2
Ji J1 J2 J3 J4 J5
t（小时）
tiA
6 8 12 3 7
tiB
11 9 5 3 4
加工顺序如下： J4—J1 —J2—J3—J5
或 J1 —J2 —J3—J5—J4
2、确定总流程时间
• 甘特图法 画法与零件移动方式图的画法相同；
（二）三台设备的流水型排序问题
约翰逊—贝尔曼拓展法：
设有A、B、C三台加工设备，在满足： mintiA≥maxtkB 或mintiC≥maxtkB
两条件之一的情况下，可将三台设备转换为 两台假想设备G与H，且：
tiG=tiA+tiB tiH=tiB+tiC
例12-3
Ji J1
J2
J3
J4
t
tiA
设零件Ji（i=1、2、…，n）的加
工顺序是从设备A到设备B， t和iA
tiB 分别是零件Ji在A和B上的加工时间。
约翰逊—贝尔曼规则步骤：
1) 以零件编号为列，零件在机床上的加工 时间为行列表，从中找最小值（如果有 多个最小值，可任取一个）；
2) 如果上述最小值属于tiA行，则对应零件 应尽先安排；如果上述最小值属于 tiB 行，则对应零件应尽后安排；
二、影响作业排序的因素
1、生产任务的到达、生产工艺流程方式
三、作业排序的任务和目标
（1） 进行优先权设定； （2）针对具体设备分配任务及人力； （3）为目标分配工作，使工作任务按期完成； （4）不断监督以确保任务的完成； （5）对实施过程中的问题或异常辨识； （6）作业排序进行检查和修改。
12.2 制造业作业排序

第九章流水作业的排序问题精品文档

第九章流水作业的排序问题精品文档

9.2 流水作业排序问题
一、最长流程时间Fmax的计算
工件 Si在机器MK 上的完工时间为CKSi • 工件 Si在机器MK 上的加工时间为PSiK
• C1Si= C1Si-1+PSi1 • CKSi=max｛ C(k-1)Si, CkSi-1 ｝+PSik
举例：有一个6/4/p/ Fmax问题，其加工时间如下 表所示。当按顺序S＝（6，1，5，2，4，3） 加工时，求Fmax。
• （1，2，3，4）或（2，1，3，4）
i12 Pi1 11 2 3 Pi2 89 4 13 Pi3 413 518
Fmax=28
3
4
69
312
215
924
8 26 2 28
i21 Pi1 22 13 Pi2 46 814 Pi3 511 418
3
4
69
312
216
925
8 26 2 28
Fmax=28 加工顺序（1，2，3，4）或（2，1，3，4）
3
4
69
312
215
924
8 26 2 28
举例
J1
J2
J3
J4
J5
J6
机器1 pi1
5
5
4
1
2 10
机器2 pi2
5
5
5
3
6 10
机器3
4
机器4 pi4
2
8
2
1
5
6
机器5 pi5
5
2
1
2
8 10
总和
25 23 15 11 28 40
具体过程
（1）找出关键工件：工作负荷最大的40，对应的是工 件 6， Jc=J6

生产运作管理---第十一章流水作业的排序问题

生产运作管理---第十一章流水作业的排序问题

假设条件
1.一个工件不能同时在几台不同的机器上加工。 2.工件在加工过程中采取平行移动方式，即当上一道工
序完工后，立即送下道工序加工。 3.不允许中断。当一个工件一旦开始加工，必须一直进
行到完工，不得中途停止插入其它工件。 4.每道工序只在一台机器上完成。 5.工件数、机器数和加工时间已知，加工时间与加工顺
Fi----工件Ji 的流程时间，即工件在车间的实际停留时间，在工
件都已到达的情况下, Fi= Pi+ Wi
Li----工件Ji 的延误时间, Li= Ci- di , Li<=0 按期或完成提前；
Li>0 延误
Fmax----最长流程时间， Fmax＝max{Fi}
二、排序问题的分类和表示法
1、排序问题的分类：
排序问题常用四个符号来描述: 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。
(a) J1 - J2 - J3- J4 - J5
A B
30
(b) J4 - J2 - J3- J5 - J1
A B
26
比较
可以看出，初始作业顺序的总加工周期是 30，用约翰逊法排出的作业顺序总加工周 期是26，显然后者的结果优于前者。
两台机器排序问题的算法（续）
I
1
2
3
4
5
6
Ai

作业排序与生产作业计划

作业排序与生产作业计划

17.10.2024
6
第一节 作业排序的基本概念
二、假设条件与符号说明
为了便于采用数学模型来分析研究排序问题，做下列假设：
1. 一个工件不能同时在几台不同的机器上被加工。 2. 采取平行移动方式移送被加工的工件。 3. 不允许中断。当一个工件一旦开始加工,必须一直进行到完
工,不得中途停止插入其它工件。 4. 工件在每道工序的加工只在一台机器上进行。 5. 工件数（或批量）、机器数已知，单件加工时间已知, 完
第一节 作业排序的基本概念
一、编制生产作业计划与排序的关系
编制生产作业计划与作业排序不同，排序只是确 定工件在机器上的加工顺序，可以用一组工件的代 号的排列来表示这组工件的加工顺序，而编制生产 作业计划不仅包括确定工件的加工顺序，而且包括 确定机器加工每个工件的开始时间和完成时间。所 以，只有生产作业计划才能指导工人的生产活动。
显然，当ri = 0 时， Fmax = Cm(sn)
在知道了上述计算Fmax 公式后，便可直接在工件加工的 时间矩阵上从左向右计算完工时间。
第二节 流水作业排序问题
例11.1有一个6/4/p/Fmax问题,其加工时间如下表所示。 当按顺序S=(6,1,5,2,4,3)加工时,求Fmax
表11-1 加工时间矩阵
i
1
2
3
4
5
6
Pi1
4
2
3
1
4
2
Pi2
4
5
6
7
4
5
Pi3
5
8
7
5
5
5
Pi4
4
2
4
3
3
1
表11-2 顺序S下的加工时间矩阵

sjf算法例题详解(一)

sjf算法例题详解(一)SJF算法例题1. 什么是SJF算法？•SJF算法（Shortest Job First，短作业优先算法）是一种操作系统调度算法。

•它的原则是按照作业的执行时间来进行调度，执行时间短的作业会被优先调度执行。

•SJF算法适用于一些具有明确执行时间的作业，能够提高作业的响应速度和系统的整体利用率。

2. SJF算法的例题考虑以下作业列表及其执行时间：作业列表：[A, B, C, D]执行时间：[5, 3, 8, 2]3. 算法过程按照SJF算法的原则，我们需要对作业列表进行排序，排序的依据是作业的执行时间。

排序后的作业列表如下：作业列表：[D, B, A, C]执行时间：[2, 3, 5, 8]4. 执行顺序根据排序后的作业列表，我们按照顺序执行作业。

执行顺序为：D -> B -> A -> C5. 算法优势SJF算法的优势在于能够减少作业的等待时间和响应时间，提高系统的整体效率。

6. 算法局限性SJF算法的局限性在于对作业的执行时间需求较高，如果无法准确估计作业的执行时间，可能会导致调度不准确。

7. 结论SJF算法是一种高效的操作系统调度算法，适用于有明确执行时间的作业。

它能够提高作业的响应速度和系统的整体利用率，但对作业的执行时间估计要求较高。

在实际应用中，可以根据任务的执行时间情况选择合适的调度算法以提高系统性能。

以上是对SJF算法例题的详细解释，希望能够对读者有所帮助。

SJF算法例题1. 什么是SJF算法？•SJF算法（Shortest Job First，短作业优先算法）是一种操作系统调度算法。

•它的原则是按照作业的执行时间来进行调度，执行时间短的作业会被优先调度执行。

•SJF算法适用于一些具有明确执行时间的作业，能够提高作业的响应速度和系统的整体利用率。

2. SJF算法的例题考虑以下作业列表及其执行时间：•作业列表：[A, B, C, D]•执行时间：[5, 3, 8, 2]3. 算法过程按照SJF算法的原则，我们需要对作业列表进行排序，排序的依据是作业的执行时间。

流水作业的排序问题


i
12
Pi1
4
2
Pi2
4
5
Pi3
5
8
pi4
4
2
345
6
3142
6745
7555
433
1
i 61 5243
Pi1 22 4 6 410 212 113 316 Pi2 57 4 11 415 520 727 633 Pi3 512 517 5 22 8 30 535 742 pi4 113 4 21 325 2 32 338 446
25 23 15 11 28 40
具体过程
（1）找出关键工件：工作负荷最大的40，对应的是工 件 6， Jc=J6
（2）满足Pi1≦Pi5的工件有J1 、J4、J5, 按Pi1值由小到
大排在关键工件前面，所以有 J4 – J5 –J1 -J6
（3）满足pi1>pi5的工件有J2、J3，按Pi5值由大到小排 在关键工件的后面, 所以有 – J6 – J2 –J3
J4 – J5 –J1 – J6 – J2 –J3
Fmax=51
（三）CDS法
Campbell, Dudek, Smith三人于1970年共
同提出了一个启发式算法，简称CDS法。他们把
Johnson算法用于一般的n /m /P/Fmax问题，
得到（m一1)个加工顺序，取其中优者。
l
m
具体做法是，对加工时间
求得最优顺序下的Fmax＝28
Johnson算法的改进
• 1. 将所有ai ≤ bi的工件按ai值不减的 顺序排成一个序列A；
• 2. 将ai＞，就构成了一个最优 加工顺序。
J1 J2
J3
J4

生产计划与控制 05-3 作业计划(排序)


3、符号说明
Ji：工件i i=1，2，┅，n Mj：机器j j=1，2，┅，m Pij： Ji在Mj上的加工时间 ri：Ji的到达时间（到达车间） Ci： Ji的完工时间 Ci= ri+Σ(ωij+ Pij)= ri+ Wi+Pi Wi：Ji在加工过程中总的等待时间 Cmax：最大完工时间：当多个工件共同进入某个车间需要加工
※ 其最优解不一定是相应的流水作业排序问题的最优解，但一般是比较好的解 ※ 对于仅有2台和3台机器的特殊情况，排列排序问题最优解一定是相应流水作业排
序问题的最优解
2、最长流程时间Fmax 的计算
J2
J5
J6
J1
ai
1
3
4
5
bi
2
7
4
7
14
8
13
18
M1
J5
J6
J1
J4
J4
J3
5
8
4
2
26 J3
M2
1、名词术语（续）
（4）机器——服务者 例如：工厂里的各种机床，维修工人，轮船要停靠的码头，……
（5）工件——服务对象 例如：单个零件，或一批相同零件
（6）工序——服务步骤 （7）加工时间——服务时间 （8）加工顺序——每台机器加工n 个工件的先后顺序 （9）加工路线——工件加工在技术上的工序顺序约束
M2
48
5 13
6 19
726
4 30
5 35
M3
5 13
8 21
7 28
533
5 38
5 43
M4
4 17
2 23
4 32
336

作业排序


作业：用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时间，作为
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

E
1
2
1
D
6
9
1+6=7
C
2
7
7+2=9
B
4
6
9+4=13
A
3
5
13+3=16
总流程时间＝1＋7＋9＋13＋16＝46（天）
平均流程时间＝46/5=9.2 （天）
每个订单平均延期（0＋1＋2＋6＋14）/5=4.0 （天）
第4页/共33页
方案5 随机次序规则。 加工顺序 加工时间
交货日期 流程时间
最优分配及其成本
• 作业I分配给机床E
$3
• 作业II分配给机床B $4
• 作业III分配给机床C $2
• 作业IV分配给机床D $5
• 作业V分配给机床A $3
• 总成本
$17
第16页/共33页
生产能力不平衡
• 假设要加工5件产品，加工顺序是从工序A 到工序B,工序A、B之间无库存。工序A的 平均加工时间为10小时，标准差为2小时； 工序B的加工时间为常数（10小时）。
交货日期 流程时间
E
1
2
1
C
2
7
1+2=3
A
3
5
3+3=6
B
4
6
6+4=10
D
6
9
10+6=16
总流程时间＝1＋3＋6＋10＋16＝36（天）
平均流程时间＝36/5=7.5 （天）
每个订单平均延期（0＋0＋1＋4＋7）/5=2.4 （天）
第2页/共33页
方案3 DDATE规则。 加工顺序 加工时间
D
7
4
第二和第三步：选择最短的作业时间并作标记。
第四步：重复第二步和第三步，直到排序完成。
第8页/共33页
运用Johnson规则的最优作业排序
机床1 作业C 作业B 作业D 作业A 空闲但可以进行另外工作 机床2 空闲 作业C 作业B 作业D 作业A
0
5
11
19 23 25
第9页/共33页
例 指派方法
作业 A B C D
E
I 13 0 2
0
II 1 0 4 1
1
III 2 2 0 1
3
IV 4 0 1 0
1
V 04 1 0
3
第14页/共33页
最优方案——用“线检验”
作业 A B C D
E
I 13 0 2
0
II 1 0 4 1
1
III 2 2 0 1
3
IV 4 0 1 0
1
V 04 1 0
3
第15页/共33页
6 第104页/共33页 5
5
步骤1：行减——从每一行中减去本行最小数
作业 A B C D
E
I 23 1 5
0
II 2 0 5 4
1
III 2 1 0 3
2
IV 5 0 2 3
1
V 03 1 2
2
第11页/共33页
步骤2：列减——从每一列中减去本列最小数
作业 A B C D
E
I 23 1 3
0
II 2 0 5 2
1
0
10
10
1
10
6
16
2
10
10
20
2
20
8
28
3
20
10
30
3
30
10
40
4
30
10
40
4
40
12
52
5
40
10
50
5
52
14
66
从工序B到工序A的加工与完工时间
第18页/共33页
制造的基本类型
1 瓶颈供给非瓶颈 2非瓶颈供给瓶颈 3瓶颈与非瓶颈的产品 装配成成品 4瓶颈与非瓶颈独立 向市场提供产品
1
III 2 1 0 1
2
IV 5 0 2 1
1
V 03 1 0
2
第12页/共33页
步骤3：应用线检验
作业 A B C D
E
I 23 1 3
0
II 2 0 5 2
1
III 2 1 0 1
2
IV 5 0 2 1
1
V 03 1 0
2
第13页/共33页
步骤4：将未被覆盖的数减去其中的最小数，并 将该最小数加到直线的交点上
D
6
9
6
C
2
7
6+2=8
A
3
5
8+3=11
E
1
2
11+1=12
B
4
6
12+4=16
总流程时间＝6＋8＋11＋12＋16＝53（天）
平均流程时间＝53/5=10 .6（天）
每个订单平均延期（0＋6＋8＋11＋12）/5=5.4 （天）
第5页/共33页
方案6 STR规则。 加工顺序 加工时间
交货日期 流程时间
39
LCFS
46
随机
53
STR
43
平均完成时间 平均延期
10
4.6
7.2
2.4
7.8
2.4
9.2
4.0
10.6
5.4
8.6
3.2
第7页/共33页
N个作业两台机床的排序
用4个作业在两台机床上排序来说明这个程序。
第一步：列作业时间
作业 在第一台机床上的作业时间
在第二台机床上的作业时间
A
3
2
B
6
8
C
5
6
交货日期 流程时间
E
1
2
1
A

5
1+3=4
B
4
6
4+4=8
C
2
7
8+2=10
D
6
9
10+6=16
总流程时间＝1＋4＋8＋10＋16＝39（天）
平均流程时间＝39/5=7.8 （天）
每个订单平均延期（0＋0＋2＋3＋7）/5=2.4 （天）
第3页/共33页
方案4 LCFS规则。 加工顺序 加工时间
交货日期 流程时间
产品号 开始时间 加工时间 完工时间 产品号 开始时间 加工时间 完工时间
1
0
14
14
1
14
10
24
2
14
12
26
2
26
10
36
3
26
10
36
3
36
10
46
4
36
8
44
4
46
10
56
5
44
6
50
5
56
10
66
从工序A到工序B的加工与完工时间
第17页/共33页
产品号 开始时间 加工时间 完工时间 产品号 开始时间 加工时间 完工时间
E
1
2
1
A
3
5
1+3=4
B
4
6
4+4=8
D
6
9
8+6=14
C
2
7
14+2=16
总流程时间＝1＋4＋8＋14＋16＝43（天）
平均流程时间＝43/5=8.6 （天）
每个订单平均延期（0＋1＋4＋8＋14）/5=3.2 （天）
第6页/共33页
优先调度规则比较
规则 总的完成时间
FCFS
50
SOT
36
Ddate
X Y 市场 Y X 市场 X 最终 市场 Y 装配 X 市场 Y 市场
第19页/共33页
控制方法
• 资源X和资源Y都是生产多种产品的工作 中心，每个工作中心每个月都有200个小 时可以利用。为简化起见，假设我们只 生产一种产品，根据条件不同分为四种 情况。X加工每单位产品要用一小时，市 场每月对该产品的需求为200单位； Y加 工每单位产品要用45分钟，市场每月对 该产品的需求为200单位。
• 假定一个调度员有5项作业要完成，每项 作业可在5台机床的任一台上完成(n=5)。 完成每项作业的成本见下表。计划员想 设计一个最小成本分配方案。
• 表1 每项作业的机床加工成本分配矩阵
作业 A B C D
E
I 56 4 8
3
II 6 4 9 8
5
III 4 3 2 5
4
IV 7 2 4 5
3
V
3
方案1 FCFS规则。 加工顺序 加工时间
交货日期 流程时间
A
3
5
3
B
4
6
3+4=7
C
2
7
7+2=9
D
6
9
9+6=15
E
1
2
15+1=16
总流程时间＝3＋7＋9＋15＋16＝50（天）
平均流程时间＝50/5=10 （天）
每个订单平均延期（0＋1＋2＋6＋14）/5=4.6 （天）
第1页/共33页
方案2 SOT规则。 加工顺序 加工时间