第14章作业排序课件.ppt

《第14章作业排序课件.ppt》由会员分享，可在线阅读，更多相关《第14章作业排序课件.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、四章作业排序1第十三章 作业排序v 作业排序概述作业排序概述v 优先调度法则优先调度法则v Johnson Johnson 法法v 甘特图甘特图v 服务业的作业排序服务业的作业排序2一、作业排序概述 一般来说，凡是有多个不同的任务要完成，就一般来说，凡是有多个不同的任务要完成，就有作业计划，作业排序问题。有作业计划，作业排序问题。组织组织管理者必须作出以下排程管理者必须作出以下排程医院医院手术室使用、医生护士工作安排手术室使用、医生护士工作安排大学大学教室安排、学生与教师课程安排教室安排、学生与教师课程安排工厂工厂多个工件在一台机器前等待加工多个工件在一台机器前等待加工航空公司航空公司飞机维修

2、、起飞降落时间表飞机维修、起飞降落时间表日常生活日常生活期末考试、考研究生期末考试、考研究生34排序的重要性排序的重要性 在排序不恰当的车间，经常会出现作业等待时间和排队时间占总生产周期的 95%，从而造成一个较长的工作周期，再加上库存时间和其他时间，就会使生产周期延长、在制品增多、占用大量资金。输入输入移动移动时间时间排队排队时间时间准备准备时间时间运转运转时间时间 输出输出等待等待时间时间生产周期生产周期5作业排序的目标v 满足交货期满足交货期v 极小化生产提前期极小化生产提前期v 极小化准备时间或成本极小化准备时间或成本v 极小化在制品库存极小化在制品库存v 极大化设备或劳动力的利用极大

3、化设备或劳动力的利用6作业计划和排序的关系1 1 排序排序,Sequencing,Sequencing 决定不同加工件在加工中心的加工顺序决定不同加工件在加工中心的加工顺序;2 2 作业计划作业计划 Scheduling Scheduling 作业计划的主要问题不但要确定工件在各台机作业计划的主要问题不但要确定工件在各台机器上加工顺序，而且，在通常情况下都规定开工器上加工顺序，而且，在通常情况下都规定开工时间和结束时间。时间和结束时间。时间单位具体到小时、分钟！时间单位具体到小时、分钟！7 生产作业计划：是生产计划的具体实施生产作业计划：是生产计划的具体实施计划。把生产计划规定的任务，具体计划

4、。把生产计划规定的任务，具体地分配到每个生产单元，以及每个工地分配到每个生产单元，以及每个工作中心和每个操作工人，确定他们在作中心和每个操作工人，确定他们在月、周、日以及每个轮班中的具体工月、周、日以及每个轮班中的具体工作内容。作内容。8作业排序的分类1 1、按排序的对象分类、按排序的对象分类劳动力作业排序：确定人员何时工作（服务业）劳动力作业排序：确定人员何时工作（服务业）生产作业排序：将不同工件安排在不同的设备上（制造业）生产作业排序：将不同工件安排在不同的设备上（制造业）2 2、按加工设备的种类和数量不同分类、按加工设备的种类和数量不同分类单台设备排序：多种工件在一台设备单台设备排序：多

5、种工件在一台设备-n/1-n/1多台设备排序：多种工件在多台设备多台设备排序：多种工件在多台设备n/mn/m3 3、按工件到达车间的情况不同分类、按工件到达车间的情况不同分类静态排序：排序时，所有工件都已到达，一次性进行排序静态排序：排序时，所有工件都已到达，一次性进行排序动态排序：排序时，工件陆续到达，需要随时安排加工顺序动态排序：排序时，工件陆续到达，需要随时安排加工顺序9评价标准o工件流程时间o全部完工时间（平均流程时间）o延迟o在制品库存o利用率10二、优先调度法则 n 工件到1台机器（n/1）o先到先服务法则（先到先服务法则（FCFSFCFS）First Come First Ser

6、vedFirst Come First Servedo最早交货期法则最早交货期法则(EDD(EDD）Earliest Due DateEarliest Due Dateo最短加工时间法则（最短加工时间法则（SPTSPT或或SOTSOT）o Shortest Operating/Processing Time Shortest Operating/Processing Time o随机法则（随机法则（RANDOMRANDOM）11二、优先调度法则 n 工件到1台机器（n/1）n剩余时间最长优先法则（MWKR）Most work remainingn剩余时间最短优先法则(LWKR)Least wo

7、rk remainingn剩余工序最多优先法则(MOPNR)n Most operations remainingn临界比最小法则（SCR）Smallest critical ratio12举例例：例：n个作业单台工作中心排序问题。在一个作业单台工作中心排序问题。在一周的开始，有周的开始，有5位顾客提交了他们的订单。位顾客提交了他们的订单。原始数据为：原始数据为：订单（以到达的顺序）加工时间（天）交货期（天）ABCDE342615679213方案一利用FCFS规则 加工顺序 加工时间 交货日期 流程时间 延期时间ABCDE34261567920+3=33+4=77+2=99+6=1515+1=

8、16总流程时间总流程时间=3+7+9+15+16=50（天）（天）平均流程时间平均流程时间=50/5=10天天将每个订单的交货日期与其流程时间相比较，发现只将每个订单的交货日期与其流程时间相比较，发现只有有A订单能按时交货。订单订单能按时交货。订单B，C，D和和E将会延期交将会延期交货，延期时间分别为货，延期时间分别为1,2,6,14天。每个订单平均延期天。每个订单平均延期（0+1+2+6+14）/5=4.6天。天。01261414方案二 利用SPT（最短加工时间）规则 加工顺序 加工时间 交货日期 流程时间 延期时间ECABD12346275690+1=11+2=33+3=66+4=1010

9、+6=16总流程时间总流程时间=1+3+6+10+16=36（天）（天）平均流程时间平均流程时间=36/5=7.2天天订单订单E和和C将在交货日期前完成，订单将在交货日期前完成，订单A仅延期仅延期1天。每个订单天。每个订单的平均延期时间为（的平均延期时间为（0+0+1+4+7）/5=2.4天。天。0014715方案三 利用EDD(最早交货期)规则 加工顺序 加工时间 交货日期 流程时间 延期时间EABCD13426256790+1=11+3=44+4=88+2=1010+6=16总流程时间总流程时间=1+4+8+10+16=39（天）（天）平均流程时间平均流程时间=39/5=7.8天天在这种情

10、况下，订单在这种情况下，订单B，C和和D将会延期，平均延期时间为将会延期，平均延期时间为（0+0+2+3+7）/5=2.4天。天。0023716方案四利用随机规则 加工顺序 加工时间 交货日期 流程时间 延期时间DCAEB62314975260+6=66+2=88+3=1111+1=1212+4=16总流程时间总流程时间=6+8+11+12+16=53（天）（天）平均流程时间平均流程时间=53/5=10.6天天平均延期（平均延期（0+1+6+10+10）/5=5.4天天016101017优先调度规则比较 规则 总的完成时间 平均完成时间 平均延期FCFSSPTEDD随机50363953107.

11、27.810.64.62.42.45.418BCD2.53.81.91.81.72.61.03.0加工时间（小时）加工时间（小时）核对时间（小时）核对时间（小时）A工作工作工作中心工作中心1工作中心工作中心2工作中心工作中心1工作中心工作中心2A02.5B6.3C1.93.88.2D 1.810A1.74.23.8B2.68.91.0C9.9D3.013三、n个作业两台设备排序（n/2)19约翰逊法约翰逊法：约翰逊法：S.M.JohnsonS.M.Johnson于于19541954年提出，其目的是极小化年提出，其目的是极小化从第一个作业开始到最后一个作业为止的全部流程时间。从第一个作业开始到最

12、后一个作业为止的全部流程时间。约翰逊规则的步骤如下：约翰逊规则的步骤如下：A.A.列出每个作业（列出每个作业（Operation Operation）在两台工作中心上的）在两台工作中心上的作业时间表作业时间表 ；B.B.找出最短的作业时间；找出最短的作业时间；C.C.如果最短的作业时间来自第一台工作中心，则将它如果最短的作业时间来自第一台工作中心，则将它排到前面；如果最短的作业时间来自第二个工作中排到前面；如果最短的作业时间来自第二个工作中心，则将该作业排到最后；心，则将该作业排到最后；D.D.对剩余作业重复进行步骤对剩余作业重复进行步骤 B B和和 C C，直到排序完成，直到排序完成20BC

13、D2.53.81.91.81.72.61.03.0加工时间（小时）加工时间（小时）核对时间（小时）核对时间（小时）A工作工作C排序方案：排序方案：Johnson 法法21Johnson 法法BD2.53.81.81.72.63.0 加工时间（小时）加工时间（小时）核对时间（小时）核对时间（小时）A工作工作C排序方排序方案：案：A22BD3.81.82.63.0 加工时间（小时）加工时间（小时）核对时间（小时）核对时间（小时）工作工作C排序方案：排序方案：ADJohnson 法23C排序方案：排序方案：ADB工作中心工作中心1工作中心工作中心2D01.8B5.6A2.53.88.1C 1.910

14、D 3.04.83.8B2.68.21.7A9.9C 1.011BCD2.53.81.91.81.72.61.03.0加工时间（小时）加工时间（小时）核对时间（小时）核对时间（小时）A工作工作工作中心工作中心1工作中心工作中心224两种方案的比较C新排序方案：新排序方案：AD B原方案：原方案：DCA B工作中心工作中心1工作中心工作中心2A02.5B6.3C1.93.88.2D 1.810A1.74.23.8B2.68.91.0C9.9D3.013工作中心工作中心1工作中心工作中心2D01.8B5.6A2.53.88.1C 1.910D 3.04.83.8B2.68.21.7A9.9C 1.

15、01125练习iM1M2A57B12C82D54E37F4426四、甘特图 甘特图又叫作业进度计划表或横道图，可以用来帮助制定计甘特图又叫作业进度计划表或横道图，可以用来帮助制定计划和跟踪作业。它不仅用于协调已计划好的活动，而且还用划和跟踪作业。它不仅用于协调已计划好的活动，而且还用于项目计划的制定、项目的控制于项目计划的制定、项目的控制作业 周一 周二 周三 周四 周五ABC甘特图符号活动的开始活动的结束计划所用时间实际工作进程非生产时间2728293031五、服务运作活动的特殊性难点难点:如何使供需平衡？如何使供需平衡？1 1、服务需求的特点：、服务需求的特点：随机性很强随机性很强 很短的

16、响应时间很短的响应时间2 2、服务能力的特点：、服务能力的特点：只能在需求到达的同时加以利用只能在需求到达的同时加以利用 能力随时间的流逝而消失能力随时间的流逝而消失32 如何安排需求如何安排需求:1 1、预约、预约(医生、律师、咨询、汽车修理等医生、律师、咨询、汽车修理等)2 2、预订、预订(饭店、航空、铁路等饭店、航空、铁路等)3 3、排队等待、排队等待(餐馆、银行、邮局、理发店等餐馆、银行、邮局、理发店等)管理方法之一：管理方法之一：安排与调节顾客需求安排与调节顾客需求33 如何安排能力：如何安排能力：1 1、促使顾客主动参与、促使顾客主动参与 2 2、扩大服务人员技能、扩大服务人员技能

17、 3 3、改进服务系统的设计与布置、改进服务系统的设计与布置 4 4、灵活的日程计划（轮班计划）、灵活的日程计划（轮班计划）管理方法之二：管理方法之二：安排与调整运作能力安排与调整运作能力34护士排班问题的目标总目标：人力资源成本最低总目标：人力资源成本最低某一时期内护士总人数最少某一时期内护士总人数最少护士加班时间最短护士加班时间最短护士满意度最大护士满意度最大工作量平衡工作量平衡满足护士调班换班需求满足护士调班换班需求35约束o每人每周的工作时间每人每周的工作时间40小时小时o尽可能保证连续尽可能保证连续2天休息日天休息日o护士技能水平不通，人员搭配（护士长、护师、护士技能水平不通，人员搭

18、配（护士长、护师、护士）护士）o换班约束，比如刚下夜班接着安排早班不允许换班约束，比如刚下夜班接着安排早班不允许o护士的连续工作时间护士的连续工作时间12小时（疲劳）小时（疲劳）o每天不同时段繁忙程度不同，满足各阶段需求，每天不同时段繁忙程度不同，满足各阶段需求，又避免空闲又避免空闲36解决办法o数学模型数学模型o 目标规划法目标规划法o 整数规划整数规划o 数据包络分析数据包络分析o离散事件仿真离散事件仿真 o启发式算法启发式算法o信息技术为支持信息技术为支持37简单示例o急诊室的运营时间是每周急诊室的运营时间是每周7天，每天天，每天24小时。每一工作日小时。每一工作日被分成被分成3个班次，

19、每班个班次，每班8小时。仅考虑白班需要的护士总数小时。仅考虑白班需要的护士总数见表。见表。o现在急诊室主任需要制订一份工作安排以使所需的护土人现在急诊室主任需要制订一份工作安排以使所需的护土人数最少。且保证护土们每周工作数最少。且保证护土们每周工作5天，连续休息天，连续休息2天。天。日期日期周一周一周二周二周三周三周四周四周五周五周六周六 周日周日护士护士数量数量887765438o定义变量：定义变量：xi分配到班次分配到班次i中的员工数量，这里第中的员工数量，这里第i天是两个连续天是两个连续休息日的开始休息日的开始(例如分配到例如分配到x2的员工在周二周三休息的员工在周二周三休息)。bi第第

20、i天天所需员工人数。所需员工人数。o目标函数：目标函数：Min x1+x2+x3+x4+x5+x6+x7o约束条件：约束条件：o周一周一 x2+x3+x4+x5+x6 b1o周二周二 x3+x4+x5+x6+x7 b2o周三周三 x1 +x4+x5+x6+x7 b3o周四周四 x1+x2 x5+x6+x7 b4o周五周五 x1+x2+x3 +x6+x7 b5o周六周六 x1+x2+x3+x4 +x7 b6o周日周日 x1+x2+x3+x4+x5 b7o xi 0且为整数且为整数 39o该模型有多个最优解，其中一个最优解为：x1=x2=x3=0；x4=3；x5=1；x6=4；x7=2，最少需要的

21、护士数为10人。据此编制的排班计划见下表。40每周护士工作安排表护士周一周二周三周四周五周六AxxxxxBxxxxxCxxxxDxxxxExxxxFxxxxGxxxxxHxxxxxIxxxxxJxxxxx总计81010765需求人数887765过剩人数023000周日xxxx44041启发式算法(1)从每天的人员需求量中，找出全部具有人员需求量最少的两个连续日。例如，上例中具有最少人员需求量的两个连续日发生在周六和周日。如有相同的两个最小总需求量，则可任选其一，或按照预先约好的方法选择其一，如优先选择周六和周日。(2)指定1名人员在上述找出的两日需求量总和最小的日期休息，即在周六和周日休息。在

22、其余准备安排该人员工作的各日的人员需求量中减去一人的需求量。例如在本例中，周1至周五的各日人员需求量分别变成7，7，6，6和5。(3)重复步骤(1)和(2)，直至全部需求被满足，或所有人员的工作都被分配。42护士人员需要量（人）说明周一周二周三周四周五周六周日A887765-4-安排最少总需求量的周六和周日休息B776655-4-安排最少总需求量的周六和周日休息C665545-4-安排最少总需求量的周六和周日休息D5544-3-54安排最少总需求量的周四和周五休息E443434-3-安排最少总需求量的周六和周日休息F3323-2-43安排最少总需求量的周四和周五休息G22-1-3232安排最少总需求量的周二和周三休息H1-2-12121安排最少总需求量的周一和周二休息I120101-0-任意安排最少总需求量的两天休息J0-100010-周日和周一休息在岗人数8898854需求人数8877654过剩人数002120043The end44