《第14章作业排序课件.ppt》由会员分享，可在线阅读，更多相关《第14章作业排序课件.ppt（44页珍藏版）》请在三一办公上搜索。
1、,1,四章作业排序,2,第十三章 作业排序,作业排序概述 优先调度法则 Johnson 法 甘特图 服务业的作业排序,3,一、作业排序概述,一般来说，凡是有多个不同的任务要完成，就有作业计划，作业排序问题。,4,5,排序的重要性,在排序不恰当的车间，经常会出现作业等待时间和排队时间占总生产周期的 95%，从而造成一个较长的工作周期，再加上库存时间和其他时间，就会使生产周期延长、在制品增多、占用大量资金。,生产周期,6,作业排序的目标,满足交货期 极小化生产提前期 极小化准备时间或成本 极小化在制品库存 极大化设备或劳动力的利用,减少等待时间、缩短生产周期、提高设备利用率,7,作业计划和排序的关
2、系,1 排序,Sequencing 决定不同加工件在加工中心的加工顺序;2 作业计划 Scheduling 作业计划的主要问题不但要确定工件在各台机器上加工顺序，而且，在通常情况下都规定开工时间和结束时间。,时间单位具体到小时、分钟！,8,生产作业计划：是生产计划的具体实施计划。把生产计划规定的任务，具体地分配到每个生产单元，以及每个工作中心和每个操作工人，确定他们在月、周、日以及每个轮班中的具体工作内容。,9,作业排序的分类,1、按排序的对象分类,劳动力作业排序：确定人员何时工作（服务业）生产作业排序：将不同工件安排在不同的设备上（制造业）,2、按加工设备的种类和数量不同分类,单台设备排序：
3、多种工件在一台设备-n/1多台设备排序：多种工件在多台设备n/m,3、按工件到达车间的情况不同分类,静态排序：排序时，所有工件都已到达，一次性进行排序动态排序：排序时，工件陆续到达，需要随时安排加工顺序,10,评价标准,工件流程时间全部完工时间（平均流程时间）延迟在制品库存利用率,11,二、优先调度法则 n 工件到1台机器（n/1）,先到先服务法则（FCFS）First Come First Served最早交货期法则(EDD）Earliest Due Date最短加工时间法则（SPT或SOT）Shortest Operating/Processing Time 随机法则（RANDOM）,12
4、,二、优先调度法则 n 工件到1台机器（n/1）,剩余时间最长优先法则（MWKR）Most work remaining剩余时间最短优先法则(LWKR)Least work remaining剩余工序最多优先法则(MOPNR)Most operations remaining临界比最小法则（SCR）Smallest critical ratio,13,举例,例：n个作业单台工作中心排序问题。在一周的开始，有5位顾客提交了他们的订单。原始数据为：,订单（以到达的顺序）加工时间（天）交货期（天）,ABCDE,34261,56792,14,方案一利用FCFS规则,加工顺序 加工时间 交货日期 流程时
5、间 延期时间,ABCDE,34261,56792,0+3=33+4=77+2=99+6=1515+1=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天。,012614,15,方案二 利用SPT（最短加工时间）规则,加工顺序 加工时间 交货日期 流程时间 延期时间,ECABD,12346,27569,0+1=11+2=33+3=66+4=1010+6=16,总流程时间=1+3+6
6、+10+16=36（天）平均流程时间=36/5=7.2天订单E和C将在交货日期前完成，订单A仅延期1天。每个订单的平均延期时间为（0+0+1+4+7）/5=2.4天。,00147,16,方案三 利用EDD(最早交货期)规则,加工顺序 加工时间 交货日期 流程时间 延期时间,EABCD,13426,25679,0+1=11+3=44+4=88+2=1010+6=16,总流程时间=1+4+8+10+16=39（天）平均流程时间=39/5=7.8天在这种情况下，订单B，C和D将会延期，平均延期时间为（0+0+2+3+7）/5=2.4天。,00237,17,方案四利用随机规则,加工顺序 加工时间 交货
7、日期 流程时间 延期时间,DCAEB,62314,97526,0+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天,0161010,18,优先调度规则比较,规则 总的完成时间 平均完成时间 平均延期,FCFSSPTEDD随机,50363953,107.27.810.6,4.62.42.45.4,19,三、n个作业两台设备排序（n/2),20,约翰逊法,约翰逊法：S.M.Johnson于1954年提出，其目的是极小化从第一个作业开始到最后一个作业为止的全部流
8、程时间。约翰逊规则的步骤如下：,列出每个作业（Operation）在两台工作中心上的作业时间表；找出最短的作业时间；如果最短的作业时间来自第一台工作中心，则将它排到前面；如果最短的作业时间来自第二个工作中心，则将该作业排到最后；对剩余作业重复进行步骤 B和 C，直到排序完成,21,B,C,D,2.5,3.8,1.9,1.8,1.7,2.6,1.0,3.0,加工时间（小时）,核对时间（小时）,A,工作,C,排序方案：,Johnson 法,22,Johnson 法,B,D,2.5,3.8,1.8,1.7,2.6,3.0,加工时间（小时）,核对时间（小时）,A,工作,C,排序方案：,A,23,B,D
9、,3.8,1.8,2.6,3.0,加工时间（小时）,核对时间（小时）,工作,C,排序方案：,A,D,Johnson 法,24,C,排序方案：,A,D,B,25,两种方案的比较,C,新排序方案：,A,D,B,原方案：,D,C,A,B,26,练习,27,四、甘特图,甘特图又叫作业进度计划表或横道图，可以用来帮助制定计划和跟踪作业。它不仅用于协调已计划好的活动，而且还用于项目计划的制定、项目的控制,作业 周一 周二 周三 周四 周五,ABC,甘特图符号,活动的开始活动的结束计划所用时间实际工作进程非生产时间,28,29,30,31,32,五、服务运作活动的特殊性,难点:如何使供需平衡？,1、服务需求
10、的特点：随机性很强 很短的响应时间2、服务能力的特点：只能在需求到达的同时加以利用 能力随时间的流逝而消失,33,如何安排需求:1、预约(医生、律师、咨询、汽车修理等)2、预订(饭店、航空、铁路等)3、排队等待(餐馆、银行、邮局、理发店等),管理方法之一：安排与调节顾客需求,34,如何安排能力：1、促使顾客主动参与 2、扩大服务人员技能 3、改进服务系统的设计与布置 4、灵活的日程计划（轮班计划）,管理方法之二：安排与调整运作能力,35,护士排班问题的目标,总目标：人力资源成本最低某一时期内护士总人数最少护士加班时间最短护士满意度最大工作量平衡满足护士调班换班需求,36,约束,每人每周的工作时
11、间40小时尽可能保证连续2天休息日护士技能水平不通，人员搭配（护士长、护师、护士）换班约束，比如刚下夜班接着安排早班不允许护士的连续工作时间12小时（疲劳）每天不同时段繁忙程度不同，满足各阶段需求，又避免空闲,37,解决办法,数学模型 目标规划法 整数规划 数据包络分析离散事件仿真 启发式算法信息技术为支持,38,简单示例,急诊室的运营时间是每周7天，每天24小时。每一工作日被分成3个班次，每班8小时。仅考虑白班需要的护士总数见表。现在急诊室主任需要制订一份工作安排以使所需的护土人数最少。且保证护土们每周工作5天，连续休息2天。,39,定义变量：xi分配到班次i中的员工数量，这里第i天是两个连
12、续休息日的开始(例如分配到x2的员工在周二周三休息)。bi第i天所需员工人数。目标函数：Min x1+x2+x3+x4+x5+x6+x7约束条件：周一 x2+x3+x4+x5+x6 b1周二 x3+x4+x5+x6+x7 b2周三 x1+x4+x5+x6+x7 b3周四 x1+x2 x5+x6+x7 b4周五 x1+x2+x3+x6+x7 b5周六 x1+x2+x3+x4+x7 b6周日 x1+x2+x3+x4+x5 b7 xi0且为整数,40,该模型有多个最优解，其中一个最优解为：x1=x2=x3=0；x4=3；x5=1；x6=4；x7=2，最少需要的护士数为10人。据此编制的排班计划见下表。,41,每周护士工作安排表,42,启发式算法,(1)从每天的人员需求量中，找出全部具有人员需求量最少的两个连续日。例如，上例中具有最少人员需求量的两个连续日发生在周六和周日。如有相同的两个最小总需求量，则可任选其一，或按照预先约好的方法选择其一，如优先选择周六和周日。(2)指定1名人员在上述找出的两日需求量总和最小的日期休息，即在周六和周日休息。在其余准备安排该人员工作的各日的人员需求量中减去一人的需求量。例如在本例中，周1至周五的各日人员需求量分别变成7，7，6，6和5。(3)重复步骤(1)和(2)，直至全部需求被满足，或所有人员的工作都被分配。,43,44,The end,
