2016/7/19
三、排序问题的分类 （一）按照机器数目的不同 1、单台机器的排序问题 2、多台机器的排序问题 按照工件加工路线的不同，又可以分为： ①流水型（flow shop)的排序问题 所有工件的工艺路线都相同 ②非流水型（job shop)的排序问题 每个工件的工艺路线各不相同 （二）按照工件的到达情况的不同 1、静态排序▁当排序时，所有的工件都已到达，并 已准备就绪，可以对全部工件进行一次性排序。 2、动态排序▁若工件陆续到达，要随时安排它们的 加工顺序。
(a) J1 - J2 - J3- J4 - J5
A B
0
30
(b) J4 - J2 - J3- J5 - J1
A B
26 可以看出，初始作业顺序的总加工周期是30，用约翰逊法排出的作业 顺序总加工周期是26，显然后者的结果优于前者。
2016/7/19
服务作业计划
人员班次计划
将服务员工安排到不同的服务需求时间上的作 业计划是服务员工轮班问题。
【例6-1】下表是在某工作中心等待加工的6项作业的加工时 间（包含换产时间）与预定日期，假设工作的到达顺序与 表中顺序相符 。根据以下规则来决定其作业顺序：① FCFS②SPT③EDD并对它们分别进行评价。
作 业 A B C D E F 加工时间（天） 2 8 4 10 5 12 预定日期（天） 7 16 4 17 15 18
按EDD规则
• 作业顺序是C-A-E-B-D-F
顺序 C A E B D F 合计 加工时间 4 2 5 8 10 12 41 流程时间 4 6 11 19 29 41 110 预定交货期 4 7 15 16 17 18 延期天数(如果为负 则赋值0) 0 0 0 3 12 23 38
平均
110/6=18.33
第六章 生产作业排序
2016/7/19
一、作业排序的概念 作业排序就是确定工件在设备上的加工顺序， 使预定的目标得以实现的过程。 二、作业排序的目标 1、总流程时间最短 流程时间=加工时间+等待时间+运输时间 2、平均流程时间最短 3、平均在制品占用量最小 4、最大延迟时间最短 5、平均延迟时间最短 6、延迟工件最少
机器空闲
2016/7/19
【例6-3】某一班组有A、B两台设备，要完成5个工件的加工 任务。每个工件在设备上的加工时间如下表所示。求总加 工周期最短的作业顺序。 工件在两台设备上的加工时间
工件编号 J1 设备A 设备B 3 2 J2 6 8 J3 7 6 J4 1 4 J5 5 3
2016/7/19
2016/7/19
2、多项作业、两台机器的排序 -- Johnson方法
• N项作业，2台机器，所有工件的加工路 线都相同。（S.M.Johnson，1954，）
A B
•目标：使全部完工时间最小。 •条件：每种工件在每台机器上的加工时间均为已知。
2016/7/19
Johnson方法
• 步骤：
1.选择最短的作业时间； 2.如果最短时间的作业在第1个加工中心，则安 排在最前面，若在第2个加工中心，则安排在 最后； 3.在等待的队列中，取消第2步安排了的作业； 4.重复1，2，3步。
2016/7/19
仪器 工序1 工序2
Y1 12 22
Y2 Y3 4 5 5 3
Y4 15 16
Y5 10 8
Y2-Y1--Y4--Y5-Y3
作业排序结果的图示：
0
工序1 工序2
4
16
31
41 46 Y5 Y3 Y4 38
机器空闲
Y2 0
Y1 Y2 4 9
Y4 Y1
16
Y5 Y3 54 62 65
【例6-4】邮局一周内每天的员工需求如表6-1所示 。工会要求每名员工连续工作五天，然后连续休 息两天。试制定排班计划。
表6-1 一周内每天的员工需求量
日期 员工 需求 量
周一 3
周二 6
周三 5
周四 6
周五 5
周六 5
周日 5
解：
员工 A B C D E F G H
在岗员 工 需要员 工 多余员 工
2016/7/19
以上这些规则各有其特点，不同的规则适用于不同的 目标。例如，FCFS规则比较公平；SPT规则可使平均流 程时间最短，从而减少在制品数量；EDD规则可使工件的 最大延迟时间最小、平均延误时间最小；Moore法则可使 延迟的工件数最少等。
2016/7/19
FCFS、SPT、EDD优先规则的应用
（2）线性规划法
对于员工每周工作 5 天，连续休息 2 天的轮班问题，可以用一个通用的整数线性 规划模型来准确表述。首先定义变量：
xi 为从第 i 天开始工作的员工数量； bi 为第 i 天所需的员工数量；
那么可以建立如下模型：
min Z x1 x 2 x3 x 4 x 5 x 6 x 7 s.t. x1 x 4 x5 x 6 x 7 b （星期一的约束） 1 x1 x 2 x5 x 6 x 7 b（星期二的约束） 2 x1 x 2 x3 x 6 x 7 b （星期三的约束） 3 x1 x 2 x3 x 4 x 7 b（星期四的约束） 4 x1 x 2 x3 x 4 x5 b （星期五的约束） 5 x 2 x3 x 4 x 5 x 6 b（星期六的约束） 6 x3 x 4 x5 x 6 x 7 b（星期日的约束） 7 xi 0且为整数
表6-2 每周员工安排表（循环排序法） 周一 3(*) 3(*) 3 2 1(*) 1 0(*) 0 4 3 1 周二 6 5(*) 5 4 3 2 1(*) 1 6 6 0 周三 5 4 3 2(*) 2 1 0 பைடு நூலகம் 7 5 2 周四 6 5 4 3(*) 3 2 1 0(*) 6 6 0 周五 5 4 3(*) 3 2 1(*) 1 0(*) 5 5 0 周六 5 4 3(*) 3 2 1(*) 1 0 6 5 1 周日 5（*) 5 4 3 2(*) 2 1 0 6 5 1
2016/7/19
（三）按照目标函数的不同 1、平均流程时间最少 2、延期工件最少
2016/7/19
四、单台设备上的作业排序方法
排序规则： （1）最短加工时间优先规则SPT(Shortest processing time) （2）最短交货期优先规则EDD(Earliest due date) （3）先到先加工规则FCFS(First come first served) （4）最小松动时间优先规则STR(Slack time remaining) （松动时间=交货期-加工时间） （5）临界比率最小优先规则SCR(Smallest critical ratio) 交货期－当前日期 CR= 作业时间 （6）综合规则（综合使用两种规则，如先按照交货期优先 排序，然后按照最短加工时间优先的原则排序） （7）后到先加工规则 （8）随机规则 （9）延迟工件最少的规则（Moore法则）
1、单班次问题：每天只有一个班次，部门每天都 要营业
（1）启发方法: 如循环排序法 （2）最优化方法:如整数线性规划法 (3）解析法
2、多班次问题：每天有多班，一般为两班或三班
（1）循环排序法
循环排序法是一种既简单又实用的启发式方法，其基本步骤 如下： 1、从每周的员工需求人数中找到所需员工数量之和最小的连 续两个工作日,安排一名员工在这两天中休息。 若有相同的两个最小总需求量，则可任选其一；或按照预先 约定好的方法选择其一，如优先选择周六~周日。 2、使该两天的需求人数保持不变, 其他日期的需求人数减 1(如果是0不变) 3、在新一行中找出所需员工数量最少的连续两天，并再次循 环。将下一名员工分配到剩余的工作日中。 4、重复上述过程（步骤2和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 2016/7/19
（3）单班次问题的解析法 (Brownell and Lowerre,1976)
求解以下问题的单班次人员安排问题： 1、保证每人每周休息两天 2、保证每人每周连休两天 3、保证每人每周休息两天 ，隔一周在周末休息 4、保证每人每周连休两天，隔一周在周末休息
1、保证每人每周休息两天
■设某单位每周工作7天，每天一班，平常日需要N人，周末 需要n人。 W表示所需劳动力下限。 求解步骤： （1）Wi = max {n , N+ [ 2n / 5 ]} （2）安排[Wi – n ]名工人在周末休息； （3）对余下的n名工人从1到n编号，1号至[Wi – N]号工人周 一休息； （4）安排紧接着的[Wi – N]名工人第二天休息，这里，工人1 紧接着工人n ； （5）如果5 Wi > 5N + 2n ，则有多余的休息日供分配，此时 可按需要调整班次计划，只要保证每名工人一周休息两天，平 日有N人当班即可。
按FCFS规则排序
• 排序的结果是A-B-C-D-E-F。
延期天数(如果为负 则赋值0) 0 0 10 7 14 23 54
顺序 A B C D E F 合计
加工时间 2 8 4 10 5 12 41