2、两台机器排序问题 、
两台机器排序的目标是使最大完成时间（ 两台机器排序的目标是使最大完成时间（总 加工周期） 加工周期）Fmax最短 。 最短 实现两台机器排序的最大完成时间Fmax最 最 实现两台机器排序的最大完成时间 短的目标， 短的目标，一优化算法就是著名的约翰逊法 (Johnson’s Law)。其具体求解过程如下例所 。 示。
3 2
6 8
7 6
1 4
5 3
求解过程
由约翰逊法可知， 中最小加工时间值是1个时间单位 由约翰逊法可知，表5-8中最小加工时间值是 个时间单位， 它又 中最小加工时间值是 个时间单位， 是出现在设备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
排序常用的符号
Ji----工件 ，i=1,2,..n。 工件i 工件 Mj ---- 机器 ，j＝1，2，…，m. 机器j， ＝ ， ， ， di----工件 的完工期限。 工件Ji 工件 的完工期限。 pij----工件 在机器 上的加工时间 工件Ji在机器 上的加工时间,j=1,…,m 工件 在机器Mj上的加工时间 Pi----工件 的加工时间, 工件Ji的加工时间 工件 的加工时间 wij----工件 在机器 前的等待时间 j=1,…,m 工件Ji在机器 前的等待时间, 工件 在机器Mj前的等待时间 Wi----工件 在加工过程中总的等待时间 工件Ji在加工过程中总的等待时间 工件 在加工过程中总的等待时间, Ci----工件 的完成时间 工件Ji 工件 的完成时间, Fi----工件 的流程时间，即工件在车间的实际停留时间，在工 工件Ji 工件 件都已到达的情况下, 件都已到达的情况下 Fi= Pi+ Wi Li----工件 的延误时间 Li= Ci- di , Li<=0 按期或完成提前； 工件Ji 工件 的延误时间, Li>0 延误 Fmax----最长流程时间， Fmax＝max{Fi} 最长流程时间， 最长流程时间
I Ai Bi 1 5 7 2 1 2 3 8 2 4 5 4 5 3 7 6 4 4
•将工件 排在第 位 将工件2排在第 将工件 排在第1位 •将工件 排在第 位 将工件3排在第 将工件 排在第6位 •将工件 排在第 位 将工件5排在第 将工件 排在第2位 •将工件 排在第 位 将工件6排在第 将工件 排在第3位 •将工件 排在第 位 将工件4排在第 将工件 排在第5位 将工件1排在第 位 将工件 排在第4位 排在第
(3)如果该最小值是在设备 上，将对应的工件 如果该最小值是在设备1上 如果该最小值是在设备 • 排在前面，如果该最小值是在设备2上，则将对 排在前面，如果该最小值是在设备 上 • 应的工件排在后面。 应的工件排在后面。
•
(4)排除已安排好的工件，在剩余的工件中重 排除已安排好的工件， 排除已安排好的工件 复步骤(2)和 ，直到所有工件都安排完毕。 复步骤 和(3)，直到所有工件都安排完毕。
第十一章 流水作业的排序问题
一、排序问题的基本概念
排序是确定工件（零部件） 排序是确定工件（零部件）在一台 是确定工件 或一组设备上加工的先后顺序。 或一组设备上加工的先后顺序。 在一定约束条件下， 在一定约束条件下，寻找总加工时 间最短的安排产品加工顺序的方法，就 间最短的安排产品加工顺序的方法， 生产作业排序。 是生产作业排序。
举例
J1 机器1 机器 机器2 机器 机器3 机器 机器4 机器 机器5 机器 总和 pi1 pi2 pi3 pi4 pi5 5 5 8 2 5 25 J2 5 5 3 8 2 23 J3 4 5 3 2 1 15 J4 1 3 4 1 2 11 J5 2 6 7 5 8 28 J6 10 10 4 6 10 40
举例
• AB两台设备完成 个零件的加工任务，每个 两台设备完成5个零件的加工任务 两台设备完成 个零件的加工任务， 工件在设备上的加工时间如下表所示。 工件在设备上的加工时间如下表所示。求总 加工周期最短的作业顺序。 加工周期最短的作业顺序。 •
设备 \工件编号 工件编号
J1
J2
J3
J4
J5
设备A 设备 设备B 设备
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
16
最长流程时间的计算 i Pi1 Pi2 Pi3 pi4 1 4 3 7 5 4 5 9 6 6 6 3 1 8 3 3 4 3 2 9
举例2 5 8 7 5 2 2 6 5 9 4
二、排序问题的分类和表示法
1、排序问题的分类： 、排序问题的分类：
• 根据机器数的多少 单台机器的排序问题 多台机器的排序问题 • 根据加工路线的特征 单件作业排序(Job Shop) 单件作业排序 流水作业排序(Flow Shop) 流水作业排序 • 根据工件到达系统的情况 静态排序 动态排序
• 根据参数的性质 确定型排序 随机型排序 • 根据要实现的目标 单目标排序 多目标排序
假设条件
1.一个工件不能同时在几台不同的机器上加工。 一个工件不能同时在几台不同的机器上加工。 一个工件不能同时在几台不同的机器上加工 2.工件在加工过程中采取平行移动方式，即当上一道工 工件在加工过程中采取平行移动方式， 工件在加工过程中采取平行移动方式 序完工后，立即送下道工序加工。 序完工后，立即送下道工序加工。 3.不允许中断。当一个工件一旦开始加工，必须一直进 不允许中断。 不允许中断 当一个工件一旦开始加工， 行到完工，不得中途停止插入其它工件。 行到完工，不得中途停止插入其它工件。 4.每道工序只在一台机器上完成。 每道工序只在一台机器上完成。 每道工序只在一台机器上完成 5.工件数、机器数和加工时间已知，加工时间与加工顺 工件数、 工件数 机器数和加工时间已知， 序无关。 序无关。 6.每台机器同时只能加工一个工件。 每台机器同时只能加工一个工件。 每台机器同时只能加工一个工件
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
最长流程时间的计算 i Pi1 Pi2 Pi3 pi4 6 2 7 5 12 5 13 1
2
1 4 11 4 17 5 21 4
6
5 4 15 4 22 5 25 3
2、排序问题的表示法 排序问题的表示法
排序问题常用四个符号来描述: 排序问题常用四个符号来描述 n/m/A/B 其中, 工件数； 其中 n-----工件数； 工件数 m-----机器数； 机器数； 机器数 A----车间类型； 车间类型； 车间类型 F=流水型排序， P=排列排序 流水型排序， 排列排序 流水型排序 G=一般类型 即单件型排序 一般类型,即单件型排序 一般类型 B-----目标函数 目标函数
(a) J1 - J2 - J3- J4 源自 J5AB30
(b) J4 - J2 - J3- J5 - J1
A
B
26
比较
可以看出， 可以看出，初始作业顺序的总加工周期 是30，用约翰逊法排出的作业顺序总加工 ， 周期是26，显然后者的结果优于前者。 周期是 ，显然后者的结果优于前者。
两台机器排序问题的算法（续）
三、流水作业排序问题
1、最长流程时间Fmax的计算 、最长流程时间 的计算 举例：有一个6/4/p/ Fmax问题，其加工时 问题， 举例：有一个 问题 间如下表所示。当按顺序S＝（ ＝（6， ， ， 间如下表所示。当按顺序 ＝（ ，1，5， 2，4，3）加工时，求Fmax。 ， ， ）加工时， 。
约翰逊－ 约翰逊－贝尔曼法则
• 约翰逊法解决这种问题分为 个步骤： 约翰逊法解决这种问题分为4个步骤： 个步骤 • (1)列出所有工件在两台设备上的作业时间。 列出所有工件在两台设备上的作业时间。 列出所有工件在两台设备上的作业时间
•
(2)找出作业时间最小者。 (2)找出作业时间最小者。 找出作业时间最小者
排序困难性
例如，考虑 项任务 工件）， 项任务（ ），有 ！ 例如，考虑32项任务（工件），有32！≈2.6×1035种 × 方案,假定计算机每秒钟可以检查 假定计算机每秒钟可以检查1 个顺序, 方案 假定计算机每秒钟可以检查 billion个顺序 个顺序 全部检验完毕需要8.4× 个世纪。 全部检验完毕需要 ×1015个世纪。 如果只有16个工件 同样按每秒钟可以检查1 个工件, 如果只有 个工件 同样按每秒钟可以检查 billion 个顺序计算, 也需要2/3年 个顺序计算 也需要 年。 以上问题还没有考虑其他的约束条件, 如机器、 以上问题还没有考虑其他的约束条件 如机器、人 力资源、厂房场地等，如果加上这些约束条件， 力资源、厂房场地等，如果加上这些约束条件，所 需要的时间就无法想象了。 需要的时间就无法想象了。 所以，很有必要去寻找一些有效算法， 所以，很有必要去寻找一些有效算法，解决管理中 的实际问题。 的实际问题。