第十一章 排队论与作业排序

空间复杂度 O (1) O (1) O (1) O (log n)
稳定性 稳定 不稳定 稳定 不稳定
排序优化
1
减少比较次数
通过优化比较顺序或使用特定的排序算
减少交换次数
2
法，减少不必要的比较操作。
通过优化交换顺序或使用特定的排序算
法，减少不必要的交换操作。
3
快速排序优化
使用优化的基准元素选择策略，避免最
《作业排序》PPT课件
# 作业排序 PPT课件 ## 简介 - 什么是作业排序 - 为什么需要作业排序 - 作业排序的原则
算法分类
冒泡排序
一种简单的排序算法，通过不断交换相邻的元 素，将最大（或最小）序
通过不断选择剩余元素中的最小（或最大）元 素，并与当前位置的元素交换，将最小（或最 大）元素逐渐从前往后排。
归并排序优化
4
坏情况的发生。
使用迭代代替递归，减少函数调用和额 外的内存消耗。
实战演练
无序数据
给定一组无序数据，使用不同的 排序算法进行排序。
优缺点分析
分析不同算法的优缺点，了解它 们适用的场景和限制。
优化思考
思考如何优化排序算法，提升效 率。
总结
1 排序算法的应用场景
了解哪些场景需要使用排序算法，例如数据分析、搜索和数据库操作。
插入排序
通过将每个元素插入到已排序部分的正确位置， 逐步构建排序序列。
快速排序
一种分治法的排序算法，通过选择一个基准元 素，将数组分为两个子数组，递归排序子数组， 然后将结果合并。
算法比较
算法 冒泡排序 选择排序 插入排序 快速排序
时间复杂度 O (n^ 2) O (n^ 2) O (n^ 2) O (n log n)

11.2.3 n/2排序问题
• 是指n种工件在2台机器设备上进行加工的排 序问题。
• 当两台设备上流水加工工件所用的完工时间 最少时，第二台设备的闲置时间也得到最小 化。
Johnson算法
使用条件： 1、排序的目标是使全部完工时间最小 2、工件在两台设备上的加工顺序完全相同 3、所有工件同时到达第一台设备等待加工 4、每种工件在每台设备上的加工时间均已知
例题
• 假设某银行的一个储蓄所有8名储蓄工作人员，储蓄 所根据历史数据，估计每天顾客对储蓄工作人员的需 求量数据如下表。该所的所长需要为这8名储蓄工作 人员安排工作日，在不影响服务水平的前提下，使这 8名员工每周都能享受2天连续的休息日，并且尽量安 排在周末休息。另外，所长还想了解根据目前的客户 量，储蓄工作人员数是否能够满足需求，是存在人员 不足的问题，还是人员冗余的问题。
1 2 n
Mห้องสมุดไป่ตู้
a11 a21
a12 a22
a1n a2n
1 2
aij表示工件j(j 1,2,, n)在设备i(i 1,2)的加工时间。
假设有六个工件（ABCDEF）需要在机床X和Y上加工， 加工顺序是先X后Y，每个工件所需加工时间（单位：
小时）见表，管理者希望找到一个最优化的排序方 案，使所有工件的加工总时间最少。
顾客到达
排队规则
排队系统
服务机构
顾客离去
排队规则
• 先到先服务 • 后到先服务 • 随机服务 • 有优先权的服务
服务结构
• 是指提供服务的服务人员数或者服务台数量。
2）调整顾客到达率的措施
• 采用预约系统 • 采用预订系统 • 采用差异定价措施
11.3.2服务人员排序

5 2 7 4 6 5
在M中寻找到的最小值为2，对应的产品为B，
对应的设备为磨床，因此，应 将产品B排在 最后加工。在M中划去产品B，得余下的工时 矩阵M1 :
A B C D E F A C D E F 车床 磨床
3 7 4 6 8 9
M=
5 2 7 4 6 5
3 4 6 8 9
车床 磨床
M 1=
(3)所有工件同时到达第一台设备等待加工;
(4)每种工件在每台设备上的加工时间均已知。 约翰逊算法的基本思路在于:尽量减少第二台设备上
的等待加工的时间，因此，在第二台设备上加工时 间长的工件先加工，在第二台设备上加工时间短的 工件后加工。
约翰逊算法的步骤如下: (1)先作n个工件在两台设备上的加工时间的
磨工序定额工时h
Ⅰ
Ⅱ Ⅲ Ⅳ
6
4 6 2
2
6 4 4
如何具体地组织生产活动、安排作业顺序和
及时反馈信息，对生产活动进行调整与控制， 使各种资源得到合理利用，同时又能按期完 成各项订单任务，是作业排序与控制所需要 研究和解决的问题。
作业排序的主要目标包括:
(1)满足交货日期的需要
(2)降低在制品库存，加快流动资金周转
为C和D，其对应的设备分别为车床和磨床， 因此，应将产品C排在产品A之后加工，而将 产品D排在产品B之前加工。在M2中划去户 品C和D，得余下的工时矩阵M3:
C D E F E 车床 磨床 F
4 6 8 9
8
9
车床 磨床
M 2=
7 4 6 5
M 3=
6 5
在M3中找到的最小值为5，对应的产品为F，
n/m(m≥3)的流水作业排序是一个复杂的问题。

16
如果这些零件在车床上和磨床上加工顺序都为 1、 2、3、4、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
零件加工顺序： 零件加工顺序： 第一： 第一： 第二： 第二： 第三： 第三： 第四： 第四： 第五： 第五： 零件 2
23
接着， 接着，我们又找到最短加工时间为 0.5，这一时间与 ， 磨床有关， 磨床有关，我们把磨床加工时间为 0.5 的零件 1 放 到第四位加工，同时把表中的零件 1 所在行划去。 到第四位加工， 所在行划去。 下一个最短的加工时间为 0.75，这个加工时间是车 ， 床加工零件 5 的所需时间，故我们把零件 5 排在加 的所需时间， 工顺序的第一位上， 所在的行划去。 工顺序的第一位上，并把零件 5 所在的行划去。同 理下一个最短加工时间是车床加工零件 3，所用时间 所用时间 排在第二位上， 为 1，故把零件 3 排在第二位上，并划去零件 3 所 ， 在行。 在行。
3
一、一台机器、几个零件的排序问题 一台机器、 某车间有一台磨床，现有六个零件都要求加工， 例1. 某车间有一台磨床，现有六个零件都要求加工， 这六个零件加工所需要的时间如下表所示： 这六个零件加工所需要的时间如下表所示：
加工时间（h） 零件 加工时间 加工时间（h） 零件 加工时间 1 1.8 4 0.9 2 2.0 5 1.3 3 0.5 6 1.5