《作业计划》PPT课件.ppt

1,第十二章 时间进度安排 Scheduling,2,第十二章 时间进度安排,12.1作业排序的基本概念； 11.2制造业的时间进度安排 11.3少量生产系统的时间进度安排 11.4服务业的时间进度安排,3,教学目的与手段,教学目的： 使学生对排序的相关问题有一定认识，了解排序在企业生产运营管理中的地位与应用。 教学手段：讲述 (1) 了解车间作业管理的主要工作； (2) 了解作业排序的目标与分类； (3) 掌握制造业作业排序的一般方法与数学方法； (4) 了解服务业排序的原则与方法。 教学重点 流水线的排序 单件生产排序 服务业的排序 教学难点 排序规则、排序算法,4,12.1作业排序的基本概念,一、基本概念 二、作业排序问题的分类 三、作业排序的任务和目标 四、作业排序方案的评价标准 五、优先调度规则,5,排序的作用,实例1：油漆生产顺序 某企业生产白、灰、红、蓝四种油漆，每次生产前都有清洗容器的调整准备时间。按怎样的顺序，总的调整准备时间最少？ 实例2：复印排序问题 有四人同时到达复印室，每人的复印量不同，如何安排顺序，使得他们的平均等待时间和平均流程时间最小？,6,方案1：白-灰-红-蓝 T-setup=12 方案2：蓝-红-灰-白 T-setup=20,7,一、基本概念,1、排序（Sequencing）： 排序就是要将不同的工作任务安排一个执行的顺序，使预定的目标最优化。 实际上就是要解决如何按时间的先后，将有限的人力、物力资源分配给不同工作任务，使预定目标最优化的问题。,将MRP转化为各个车间、班组、工作地的任务,8,一、基本概念,排序中常用的几个概念 “机器”，可以是工厂里的各种机床，也可以是维修工人；可以是轮船要停靠的码头，也可以是电子的计算机中央处理单元、存贮器和输入、输出单元。一句话，表示“服务者” “零件”代表“服务对象”。零件可以是单个零件，也可以是一批相同的零件 “加工路线”是零件加工的工艺过程决定的，它是零件加工在技术上的约束 “加工顺序”则表示每台机器加工n个零件的先后顺序，是排序和编制作业计划要解决的问题,9,有关的名词术语 “派工” (Dispatching)是在作业计划制定以后，按照作业计划的要求，将具体生产任务通过工票或施工单的形式下达到具体的机床和工人，属于通常所说的“调度”范围。 “赶工” (Expediting)是在实际进度已落后于计划进度时采取的行动，也属于通常所说的“调度”范围。 “调度”是作业计划编制后实施生产控制所采取的一切行动，“编制作业计划”是加工制造发生之前的活动 作业排序也就是要确定工件在机器上的加工顺序，可用一组工件代号的一种排列来表示。 如，用（1，6，5，4，3，2）表示加工顺序：J1J6J5J4J3J2。,10,一、基本概念,2、作业计划（Scheduling） 作业计划与排序不是一回事，它不仅要确定工件的加工顺序，而且还要确定每台机器加工每个工件的开工时间和完工时间。 如果按最早可能开（完）工时间来编排作业计划，则排序完后，作业计划也就确定了。 3 、制定作业计划的影响因素 工件到达的方式(The job arrival pattern) 车间内机器的数量(Number and variety of machines in the shop) 车间拥有的人力资源(Number of workers in the shop) 工件移动方式(Particular flow patterns) 不同调度准则的评价(Evaluations of alternative rules),11,4 、作业计划与控制的关系 作业计划：给生产活动(Production Activities)制定详细时间表 生产控制：以生产计划和作业计划为依据，检查、落实计划执行情况，发现偏差即采取纠正措施，保证实现各项各项计划目标 5、排序与编制作业计划的差别 上面讲了编制作业计划的问题. 在编制作业计划过程中,有一个问题需要管理人员注意,即投入生产过程的作业顺序的安排. 作业计划是安排零部件（作业、活动）的出产数量、设备及人工使用、投入时间及出产时间。 排序，给出零部件在一台或一组设备上加工的先后顺序的工作。,12,所以,编制作业计划与排序的概念和目的都是不同的。但是，编制作业计划的主要工作之一就是要确定出最佳的作业顺序。 确定出最佳的作业顺序看似容易，只要列出所有的顺序，然后再从中挑出最好的就可以了，但要实现这种想法几乎是不可能的。 例如，考虑32项任务（工件），有32！2.61035种方案,假定计算机每秒钟可以检查1 billion个顺序, 全部检验完毕需要8.41015个世纪. 如果只有16个工件, 同样按每秒钟可以检查1 billion个顺序计算, 也需要2/3年. 以上问题还没有考虑其他的约束条件, 如机器、人力资源、厂房场地等，如果加上这些约束条件，所需要的时间就无法想象了。 所以，很有必要去寻找一些有效算法，解决管理中的实际问题。,13,编制作业计划要解决的问题,通过制定作业计划，可以使企业： 满足交货期要求 Meet Due Dates 使在制品库存最小 Minimize work-in-process inventory 使平均流程时间最小 Minimize the average flow time through the system 提供准确的工件状态信息 Provide for accurate job status information 提高机器/工人的时间利用率 Provide for high machine/worker time utilization(Minimize worker idle time) 减少调整准备时间 Reduce setup times 使生产和人工成本最低 Minimize production and worker costs,14,二、作业排序问题的分类,（一）两种基本形式,1、劳动力作业排序（人员排序）：主要确定人员何时工作,2、生产作业排序：将不同工件安排到不同设备上或安排不同的人做不同的工作。,在制造业中，生产作业排序是最主要的加工工件是焦点；,在服务业中，劳动力作业排序是主要的服务的及时性是影响公司竞争力的主要因素。,15,（二）制造业作业排序的分类,1、按机器的种类和数量,2、按工件到达车间的情况,单件作业（Job-shop）排序问题： 工件的加工路线不同,流水作业（Flow-shop）排序问题： 所有工件的加工路线完全相同,3、按目标函数的性质,16,（三）其他分类,车间作业计划(Job Floor scheduling) 人力计划(Personnel Scheduling) 设施计划(Facilities Scheduling) 车辆调度计划(Vehicle Scheduling) 供应商计划(Vendor Scheduling) 工程项目计划(Project Scheduling) 动态计划和静态计划(Dynamic versus Static Scheduling),17,三、作业排序的任务和目标,有效的作业排序应做到以下几点：,1、对将要做的工作进行优先权设定，以使工作任务按最有效顺序排列；,2、针对具体设备分配任务及人力，通常以可利用的能力为基础；,3、以实施为目标分配工作，以使工作任务如期完成。,18,四、作业排序方案的评价标准,1、工件流程时间：从工件开始加工至完工的时间。 包括在各个机器之间的移动时间、等待时间、加工时间等。,2、全部完工时间（最长流程时间） 完成一组工件所需的全部时间从第一个工件在第一台机器 开始加工，到最后一个工件在最后一台机器上完成加工时为止所经过的时间。,3、延迟：比预定完工时间延迟的时间部分,4、在制品库存,5、总库存：计划入库量与现有库存量的总和,6、利用率：一台机器或一个工人的有效生产时间占总工作时间 的百分比。,注：这些标准之间并不完全独立,19,五、优先调度规则,1、SPT（Shortest Processing Time）规则（最短加工时间规则） 优先选择加工时间最短的工件 使工件的平均流程时间最短，从而减少在制品量。,2、FCFS（First Come First Served）规则（先到先服务规则）,按订单的先后顺序进行加工（优先选择最早进入可排工序 集合的工件）来自排队论，对工件较公平,3、EDD（Earliest Due Date）规则 优先选择完工期限最紧的工件 使工件延误时间最少,根据不同的目标确定优先规则，按优先规则确定各任务的优先权，由此排定加工顺序。,4、MWKR（Most Work Remaining）规则 优先选择余下加工时间最长的工件 使不同工作量的工件完工时间尽量接近。,20,5、LWKR（Least Work Remaining ）规则 优先选择余下加工时间最短的工件 使工作量小的工件尽快完成,6、MOPNR（Most Operations Remaining）规则 优先选择余下工序数最多的工件,7、SCR（Smallest Critical Ratio）规则 优先选择临界比最小的工件使工件延误时间最小,临界比=工件允许停留时间/工件余下加工时间,8、RANDOM规则 随机地挑选下一个,按优先调度法则挑选工序比随意挑选一道工序的方法更能符合计划编制者的要求，同时又不必列出所有可能的作业计划，从而计算量小。 迄今，人们已提出了100多个优先调度法则,21,优先调度规则事例,在理论方面，排序问题的难度随着机床数量的增加而增大，而 不是随需加工的作业数量的增加而增大。 （一）n个作业单台机床的排序,22,用SPT规则得出的作业排序,平均在制品库存 102/44=2.32（个）,平均总库存 120/44=2.78（个）,D,0,3,3,3,18,18,15,B,3,6,9,9,12,12,3,A,9,8,17,17,10,17,7,E,17,12,29,29,22,29,7,C,29,15,44,44,20,44,24,102,120,18,38,20.4,3.6,7.6,23,EDD规则,平均在制品库存 115/44=2.61（个）,平均总库存 118/44=2.68（个）,A,0,8,8,8,10,10,2,B,8,6,14,14,12,14,2,D,14,3,17,17,18,18,1,C,17,15,32,32,20,32,12,E,32,12,44,44,22,44,22,115,118,3,36,23,0.6,7.2,24,11.2制造业的时间进度安排,一、假设条件与符号说明 二、流水作业排序问题 一）最长流程时间的计算 二）两台机器排序问题的最优算法 三）多台机器排序问题的启发式算法 四）相同零件不同移动方式下加工周期的计算 三、作业排序的一般方法,25,一、假设条件与符号说明,一个工件不能同时在几台不同的机器上面加工 工件在加工过程中采取平行移动的方式 不允许中断 每道工序只在一台机器上面完成 工件数,机器数和加工时间已知,加工时间与加工顺序无关 每台机器同时只能加工一个工件,26,符号说明,Ji -工件i Mj -机器j pij -工件i在机器j上的加工时间, Pi -工件i总的加工时间 Pi = pij ri -工件i的到达时间 di -工件i的完工期限,27,wij -工件i在第j道工序的等待时间 Wi -工件i总的等待时间 Wi = wij Ci -工件i的完工时间 Ci = ri +Wi+Pi Fi -工件i的流程时间 Fi = Ciri= Wi+Pi Li -工件i的延迟时间 Li = Cidi,28,排序问题的表示法,一般正规的表示方法为：n/m/A/B n：工件数； m：机器数； A：车间类型（F、P、G）； 同顺序排列（P） 一般流水型(F):流水车间(Flow-shop) 非流水型(G):单件车间(Job-shop) B：目标函数 加工周期 交货期 总费用,29,说明,一般来说，排列排序问题的最优解不一定是相应流水车间排序问题的最优解，但一般是比较好的解。而对于仅有2台或3台机器的情况，则排列排序问题的最优解一定是相应流水车间排序问题的最优解。 流水线是流水车间(Flow shop) 典型的代表，每个零件的加工路线都一致。 只要加工路线一致：M1， M2, M3，Mm,不要求每个零件都经过每台机器加工,30,二、流水作业排序问题,流水车间(Flow shop):工件的加工路线都一致，典型的如流水线 一）最长流程时间的计算 二）两台机器排序问题的最优算法 三）多台机器排序问题的启发式算法,31,一）最长流程时间的计算,目标函数Fmax最短；n/m/p/ Fmax问题 从第一个工件在第一台机器开始加工时算起，到最后一个工件在最后一台机器上完成时为止所经过的时间 假设：所有工件的到达时间都为零,32,例11.1 按顺序S=(6,1,5,2,4,3) 加工 求Fmax,6/4/p/ Fmax问题,序号为1的工件在序号为1的机器上面的加工时间为4,33,流水作业排序问题工件加工路线相同 6个零件以相同的顺序经过4台机床 每个零件在每台机床上面的加工时间可以不一样,1,2,3,4,34,按顺序S=(6,1,5,2,4,3)列出加工时间矩阵,工件代号i,6 1 5 2 4 3,Pi1 Pi2 Pi3 Pi4,35,按顺序S=(6,1,5,2,4,3)列出加工时间矩阵,工件代号i,6 1 5 2 4 3,Pi1 2 Pi2 5 Pi3 5 Pi4 1,36,按顺序S=(6,1,5,2,4,3)列出加工时间矩阵,工件代号i,6 1 5 2 4 3,Pi1 2 4 Pi2 5 4 Pi3 5 5 Pi4 1 4,37,按顺序S=(6,1,5,2,4,3)列出加工时间矩阵,工件代号i,6 1 5 2 4 3,Pi1 2 4 4 2 1 3 Pi2 5 4 4 5 7 6 Pi3 5 5 5 8 5 7 Pi4 1 4 3 2 3 4,38,按顺序S=(6,1,5,2,4,3)列出加工时间矩阵,工件代号i,6 1 5 2 4 3,Pi1 2 4 4 2 1 3 Pi2 5 4 4 5 7 6 Pi3 5 5 5 8 5 7 Pi4 1 4 3 2 3 4,2,39,按顺序S=(6,1,5,2,4,3)列出加工时间矩阵,工件代号i,6 1 5 2 4 3,Pi1 2 4 4 2 1 3 Pi2 5 4 4 5 7 6 Pi3 5 5 5 8 5 7 Pi4 1 4 3 2 3 4,2 6 10 12 13 16,40,按顺序S=(6,1,5,2,4,3)列出加工时间矩阵,工件代号i,6 1 5 2 4 3,Pi1 2 4 4 2 1 3 Pi2 5 4 4 5 7 6 Pi3 5 5 5 8 5 7 Pi4 1 4 3 2 3 4,2 6 10 12 13 16,7,12,13,41,按顺序S=(6,1,5,2,4,3)列出加工时间矩阵,工件代号i,6 1 5 2 4 3,Pi1 2 4 4 2 1 3 Pi2 5 4 4 5 7 6 Pi3 5 5 5 8 5 7 Pi4 1 4 3 2 3 4,2 6 10 12 13 16,7,12,13,比较的目的是确定生产能否连续，是否有机器等待时间,42,按顺序S=(6,1,5,2,4,3)列出加工时间矩阵,工件代号i,6 1 5 2 4 3,Pi1 2 4 4 2 1 3 Pi2 5 4 4 5 7 6 Pi3 5 5 5 8 5 7 Pi4 1 4 3 2 3 4,2 6 10 12 13 16,7,12,13,11,7+4=11,43,按顺序S=(6,1,5,2,4,3)列出加工时间矩阵,工件代号i,6 1 5 2 4 3,Pi1 2 4 4 2 1 3 Pi2 5 4 4 5 7 6 Pi3 5 5 5 8 5 7 Pi4 1 4 3 2 3 4,2 6 10 12 13 16,7,12,13,11,17,12+5=17,44,按顺序S=(6,1,5,2,4,3)列出加工时间矩阵,工件代号i,6 1 5 2 4 3,Pi1 2 4 4 2 1 3 Pi2 5 4 4 5 7 6 Pi3 5 5 5 8 5 7 Pi4 1 4 3 2 3 4,2 6 10 12 13 16,7,12,13,11,17,21,15,22,25,20,30,32,27,35,38,33,42,46,45,课堂练习：,已知加工时间矩阵：,顺序S=(1,4,6,3,5,2),46,工件代号i,1 4 6 3 5 2,Pi1 4 5 3 4 8 6 Pi2 3 9 1 3 7 5 Pi3 7 6 8 2 5 9 Pi4 5 6 3 9 2 4,4 9 12 16 24 30,7 18 19 22 31 36,14 24 32 34 39 48,19 30 35 44 46 52,47,二）两台机器排序问题的最优算法,约翰森法则 如果Min(ai, bj) Min (aj, bi),则工件i应该排在工件j之前。 约翰逊规则（方法）目标函数是使全部完工时间最少 约翰森算法 Step1 找出最短加工时间 Step2 如果最短加工时间发生在第一台设备上，则把该零件安排在序列的最前端；如果最短加工事件发生在地二台设备上，则把该零件安排在序列的最末端 Step3 如果同时有两个以上最短时间，可以任选一个，先进行排序 Step4 重复以上步骤，直到所有零件排完为止,48,约翰森法则示例,49,举例,工件号 1 2 3 4 5 6,ai 5 1 8 5 3 4,bi 7 2 2 4 7 4,将工件2排在第1位 2 将工件3排在第6位 2 3 将工件5排在第2位 2 5 3 将工件6排在第3位 2 5 6 3 将工件4排在第5位 2 5 6 4 3 将工件1排在第4位 2 5 6 1 4 3 最优加工顺序为S=(2,5,6,1,4,3), Fmax =28,50,Johnson算法的改进,1. 将所有ai bi的工件按ai值不减的顺序排成一个序列A； 2. 将aibi的工件按bi值不增的顺序排成一个序列B； 3. 将A放到B之前，就构成了一个最优加工顺序。,51,举例,工件号 1 2 3 4 5 6,ai 5 1 8 5 3 4,bi 7 2 2 4 7 4,A=2 5 6 1,B=4 3,S= 2 5 6 1 4 3 ,52,课后习题,i 1 2 3 4 5 6 7 8,ai 9 7 10 8 2 1 5 4,bi 6 2 3 1 5 8 7 4,53,课后习题1,i 1 2 3 4 5 6 7 8,ai 9 7 10 8 2 1 5 4,bi 6 2 3 1 5 8 7 4,S=,6,4,5,2,3,8,7,1,S=,6,4,5,2,3,8,7,1,54,最优顺序：6 5 8 7 1 3 2 4,1 2 4 5 9 10 7 8 8 5 4 7 6 3 2 1,3 7 12 21 31 38 46,9 14 18 25 31 34 40 47,ai,bi,最优顺序下的加工周期为47,S=,6,4,5,2,3,8,7,1,55,1 2 5 9 4 10 7 8 8 5 7 6 4 3 2 1,3 8 17 21 31 38 46,9 14 21 27 31 34 40 47,ai,bi,S=,6,4,5,2,3,8,7,1,最优顺序：6 5 7 1 8 3 2 4,最优顺序下的加工周期为47,56,三）多台机器排序问题的 启发式算法,要求最优，计算量相当大，甚至连计算机也难以求解无法用于实际生产中。人们提出了多种启发式算法，以便以最小的计算量得到足够好的结果。 关键工件法 1. 计算每个工件的总加工时间，将加工时间最长的工件作为关键工件C； 2. 对于余下的工件，若pi1pim则按pi1不减的顺序排成一个序列Sa ,若pi1pim 则按pim不增的顺序排成一个序列Sb; 3. 顺序（Sa,C,Sb）即为所求顺序。,57,举例,工件i 1 2 3 4,Pi1 2 1 6 3 Pi2 4 8 2 9 Pi3 5 4 8 2,11 13 16 14,C,Sa (2,1),Sb(4),所求顺序： （2,1,3,4）,58,四）相同零件不同移动方式下加工周期的计算,当n个零件相同，则无排序问题。但不同移动方式下的加工周期不同 三种典型的移动方式 顺序移动方式：一批零件全部加工完成后，整批移动到下道工序加工 平行移动方式：单个零件加工完成后，立即移动到下道工序加工 平行顺序移动方式：两者混合,59,顺序移动方式,优点：运输次数少、设备利用充分、管理简单 缺点：加工周期长,60,设零件批量为n（件），工序数目为m，一批零件不计算工序间运输时间，只考虑加工时间，设其加工的周期为T（分钟），零件在i道工序的单件工时为 （分钟/件），i=1.2n. 则该批零件的加工周期为：,61,平行移动方式,工序,1,2,3,4,时间,加工周期,优点：加工周期短 缺点：运输频繁、设备空闲时间多且零碎,62,零件平行移动的加工周期 为：,tL =最长单件工序时间,63,平行顺序移动方式,特点：既保持一批零件顺序加工，有尽可能使相邻工序加工时间平行进行。如图所示：,1,2,3,4,时间,加工周期,工序,（4-1）*5=15,（4-1）*10=30,64,平行顺序移动方式（续）,平行顺序移动加工周期计算,T=4*(10+5+15+10)-(4-1)*(5+5+10)=100分钟,-,65,三、作业排序的一般方法,1、甘特图 甘特图是作业排序中最常用的一种工具。它是由亨利劳伦斯甘特(Henry L.Gantt)在1917年首先提出来的。甘特是泰勒创立和推广科学管理制度的亲密的合作者，也是科学管理运动的先驱者之一。 这种方法是基于作业排序目的，将活动与时间联系起来的最早尝试之一。有两种基本形式的甘特图：作业进度图和机器图。,66,甘特图：,机床1,机床2,A2（4）,空闲,A1（12）,A2（5）,空闲,A4（15）,A1（22）,A5（10）,A4（6）,A3（5）,A5（8）,A3（3）,空闲,比较：A2、A3、A5、A1、A4,机床1,机床2,A2（4）,空闲,A3（5）,A2（5）,A5（10）,A3（3）,A1（12）,A5（10）,空闲,空闲,A4（15）,A1（22）,空闲,A4（6）,全部流程时间：55、59,67,2、 I/O控制 I/O控制，是input/output控制的缩写，它是制造计划和控制系统的主要特征。它的主要原则是：工作中心的输入永远不能超过工作中心的输出。 当输入超过输出时，就会在工作中心产生物流堆积，结果将会延长上游作业的预计提前期。,68,3、作业排序的数学方法,3.1 约翰逊法 约翰逊法是作业排序中比较常用的一种排序方法。 它适用的条件是：n个工件经过两台设备(有限台设备)加工，所有工件在有限设备上加工的次序相同。 约翰逊法操作步骤： (1) 选出最短加工时间i，若最短加工时间有多个，任选1个； (2) 若i出现在机床1，它对应的工件先安排加工，否则放在最后安排，安排后划去该工件； (3) 重复上两个步骤，直到所有工件都排序完毕。,69,3.2 C-D-S法 CDS法，即穷举法，是坎贝尔(Campbell)、杜德克(Dudek)、史密斯(Smith)3人提出的一个启发式算法，简称C-D-S法。 穷举法的基本思想是不重复、不遗漏地穷举所有可能情况，从中寻找满足条件的结果。 穷举法的操作步骤： (1) 取首末两道工序，用约翰逊法排序，求Fmax； (2) 取首两道工序的和及尾两道工序的和，用约翰逊法排序，求Fmax； (3) 取首三道工序的和及尾三道工序的和，用约翰逊法排序，求Fmax。 以此类推，直到所有的情况(m-1种)都考虑到后，比较得到的Fmax，找出其中最小的那个排序方案为所求排序方案。,70,3.3 匈牙利法 1. 匈牙利法的基本原理 匈牙利法基于下面两个性质： 设一个指派模型的效益矩阵为(cij). 若(cij)的第i行元素均减去一个常数ui (i1,2,n)，第j列元素均减去一个常数vj(j1,2,n)，得到一个新的效益矩阵(bij)，其中每一元素 bijcij-ui-vj，则以(bij)为效益矩阵的指派模型的最优解也是以(cij)为效益矩阵的指派模型的最优解。 如果取ui(i1,2,n)为第i行元素的最小值，vj( j=1,2,n)为第j行元素的最小值，则得到新的效益矩阵(bij)为非负矩阵(即所有元去均为非负数)。这说明可以通过求以(bij)为效益矩阵的指派模型的最优解得到原指派模型的最优解,71,直观地讲，求最优解方阵就是在效益矩阵中找到n个元素，要求在不同行、不同列上，使这些元素之和最小。将这n个元素所在位置赋值为“1”，其他元素均为“0”，就得到最优解方阵。效益矩阵(bij)中每行、每列的最小元素为“0”，因此，求指派模型(P)的最优解又转化为在矩阵(bij)中找出n个在不同行、不同列上的“0”元素，这就是匈牙利法的基本思路。,72,2. 匈牙利法求解步骤 匈牙利法求解具体步骤如下。 第一步：从效益矩阵C的每行减去该行的最小元素，从所得矩阵的每列减去该列的最小元素，得新的效益矩阵B。 第二步：构造效益矩阵B的补矩阵D。 第三步：判断D是否为最优方案。是，则转第五步。 第四步：检查bij的每行、每列，从中找出“0”元素最少的一排(即行或列)，从该排圈出一个“0”元素，若该排有多个“0”元素，则任圈一个，用表示，把刚得到的元素所在行、列划去，在剩下的矩阵中重复上述过程，直至找到n个。将n个所在的位置赋值“1”，其他元素赋值为“0”，得到的矩阵就是原指派模型的最优解矩阵。,73,作业排序总结,1.n个工件在一台设备上加工 2. n个工件在二台设备上加工，且加工顺序相同 3. n个工件在三台设备上加工 4. 2个工件在m台设备上加工 5. n个工件在m台设备上加工,SPT,约翰逊和贝尔曼规则,虚拟机床,图解法,计算机处理,74,课后习题3,已知： n=4 m=5 t1=10 t2=4 t3=8 t4=12 t5=6 求：T顺、T平、T平顺,75,解： T顺= =4*(10+4+8+12+6)=160 T平= T平顺=,=(10+4+8+12+6)+3*12=76,=160-3*(4+4+8+6)=94,76,11.3少量生产系统的时间进度安排,一、问题的描述 二、两种作业计划的构成 三、求解一般n/m/G/Fmax问题的启发式方法,77,一、问题的描述,D=,1,1,1 1,2,3 1,3,2 2,1,3 2,2,1 2,3,2,T=,2 4 1 3 4 5,问题描述 流水 (i,j) (工件，工序) 单件 (i,j,k) (工件，工序，机器) (i，j，k)：表示工件i的第j道工序是在机器k上进行。 加工描述矩阵D：每一行描述一个工件的加工，每一列的工序序号相同。,78,一、问题的描述,加工时间矩阵T：与D相对应。,79,一、问题的描述,加工顺序矩阵S：每一行与机器相对应，每一列与工件相对应。,S=,1,1,1 2,2,1,1,3,2 2,3,2,2,1,3 1,2,3,80,一、问题的描述,用方块图表示：,81,二、两种作业计划的构成,1、能动作业计划的构成 各工序都按最早可能开(完)工时间安排且任何一台机器的每段空闲时间都不足以加工一道可加工工序。 符号说明： Ot 第t步可以排序的工序的集合 St t步之前已排序的工序构成的部分作业计划 Tk Ot中工序Ok的最早可能开工时间 Tk Ot中工序Ok的最早可能完工时间,82,二、两种作业计划的构成,2、能动作业计划的构成步骤： 设t1，St为空，Ot为各工件第一道工序的集合 求最小的最早完工时间 T*= minTk ,并找到出现T*的机器M*，若有多台，任选一台。 从Ot中跳出满足以下两条件的工序Oj 需要机器M*加工； Tj T* 将确定的Oj放入St，从Ot中消去Oj并将Oj的紧后工序放入Ot中，使t=t+1。 若还有未安排的工序，转步骤；否则，停止。,83,一个实例：,i,1,Ot,Tk,Tk,T*,M*,Oj,1,1,1,0,2,2,M1,1,1,1,2,1,3,0,3,2,1,2,3,2,6,3,M3,2,1,3,2,1,3,0,3,3,1,2,3,3,7,7,M3,1,2,3,2,2,1,3,7,4,1,3,2,7,8,7,M1,2,2,1,2,2,1,3,7,5,1,3,2,7,8,8,M2,1,3,2,2,3,2,7,12,6,13,M2,2,3,2,2,3,2,8,13,84,得到加工顺序矩阵：,1,1,1,2,1,3,1,2,3,2,2,1,1,3,2,2,3,2,M1,M2,M3,2,3,7,7,3,8,13,85,二、两种作业计划的构成,2、无延迟作业计划的构成 没有任何延迟出现的能动作业计划。所谓“延迟”，指有工件等待加工时，机器出现空闲，即使这段空闲时间不足以完成一道工序。,86,二、两种作业计划的构成,无延迟作业计划的构成步骤： 设t1，St为空，Ot为各工件第一道工序的集合。 求最小的最早完工时间 T*= minTk ,并找到出现T*的机器M*，若有多台，任选一台。 从Ot中跳出满足以下两条件的工序Oj 需要机器M*加工； Tj = T* 将确定的Oj放入St，从Ot中消去Oj并将Oj的紧后工序放入Ot中，使t=t+1。 若还有未安排的工序，转步骤；否则，停止。,87,一个实例：,i,1,Ot,Tk,Tk,T*,M*,Oj,1,1,1,0,2,0,M1,1,1,1,2,1,3,0,3,2,1,2,3,2,6,0,M3,2,1,3,2,1,3,0,3,3,1,2,3,3,7,3,M3,1,2,3,2,2,1,3,7,4,1,3,2,7,8,3,M1,2,2,1,2,2,1,3,7,5,1,3,2,7,8,7,M2,2,3,2,2,3,2,7,12,6,12,M2,1,3,2,2,3,2,12,13,0,M3,3,M1,7,M2,88,得到加工顺序矩阵：,1,1,1,2,1,3,1,2,3,2,2,1,1,3,2,2,3,2,M1,M2,M3,2,3,7,7,3,12,13,89,三、三类启发式算法,能动作业计划和无延迟作业计划尽管不一定是最优作业计划，但一般是较好的作业计划，特别是无延迟作业计划能提供令人满意的解。 一般能动作业计划和无延迟作业计划都有多个，可用启发式方法从中选择结果较好的作业计划。 一般来说，以构成无延迟作业计划的步骤为基础的启发式算法比以构成能动作业计划的步骤为基础的启发算法的效果要好。 （1）优先调度法则 构成两种作业计划的第（3）步一般都有多道工序可以满足，按不同的优先调度法则来选择工序，可以得出满足不同目标函数的作业计划 计算量小 已经提出100多种优先调度法则,90,优先调度法则 FCFS（first come, first served）选择最早进入可排序集合的工序 SPT( shortest processing time）选择加工时间最短的工序 EDD（earliest due date）选择完工期限最紧的工序 SCR(smallest critical ratio)选择临界比最小的工件 MWKR(most work remaining)选择余下加工时间最长的工件 LWKR(least work remaining)选择余下加工时间最短的工件 MOPNR(most operations remaining)选择余下工序数最多的工件 RANDOM 随机挑选一个工件,91,（2）随机抽样法 从全部能动计划或无延迟计划中随机抽样，得出多个作业计划，从中取优。 （3）概率调度法 将优先调度法则与随机抽样法结合 对不同工件将优先调度法则分配不同的挑选概率，效果较好,92,11.4服务业的时间进度安排,一、服务业的作业排序 二、随机服务系统 三、人员班次计划,93,一、服务业的作业排序,1、服务作业排序与生产作业排序的主要区别 所提供产品的类型 由于服务过程有顾客参与,作业排序对他们有直接影响,并因此成为服务的一部分,而在生产作业排序对产品的最终使用者没有直接影响 排序内容 在服务业中, 排序要定义服务交易的时间或消耗点；而在制造业中仅仅定义产品生产的操作步骤 过程控制 在服务业中,顾客参与服务过程,并且对全部操作过程施加影响. 人员规模 在顾客化服务中,服务的输出与劳动力的最佳规模之间的关系很难确定；而生产作业中,两者之间的关系有紧密联系,因此最佳的作业顺序可以被计算出来,94,2、服务业有两种基本的排序方式： 1）服务作业排序方法之一安排顾客需求 将顾客需求分配到服务能力的不同时间段内； 预约：如医生、律师等的服务 预定：顾客预定旅馆房间、火车或飞机票 排队等待：一种为顾客排序的不太准确的方法是允许需求积压，让顾客排队等待。例如，餐馆、银行、零售商店等。 2）服务作业排序方法之二安排服务人员 将服务人员安排到顾客需求的不同时间段内。 当需要快速响应顾客需求、且需求量大致可以预计时，通常使用这种方法。如邮局营业员、护士、警察的工作日和休息日安排；一天营业24小时、一周7天都营业的商店保安人员安排；等等,一、服务业的作业排序,95,二、随机服务系统,研究排队现象有助于确定服务能力，控制队长，发挥发挥设施能力 （1）由于顾客到达和服务时间的随机性，现实中的排队现象几乎不可避免； （2）排队过程，通常是一个随机过程， 排队论又称“随机服务系统理论”； 2.1 随机服务系统的构成 2.2 最简单的随机服务系统,96,2.1 随机服务系统的构成,重要问题：应尽量使顾客等待时间缩短排队论的方法,97,2.1 随机服务系统的构成,排队规则,顾客排队方式：等待制/即时制(损失制); 排队系统容量：有限制/无限制; 排队队列数目: 单列/多列; 是否中途退出: 允许/禁止; 是否列间转移: 允许/禁止; (仅研究禁止退出和转移的情形),98,2.1 随机服务系统的构成,99,2.1 随机服务系统的构成 结构类型,单队，单阶段,多队，单阶段,单队，多阶段,100,多队，多阶段,混合式,2.1 随机服务系统的构成 结构类型,101,2.1 随机服务系统的构成,Kendall 分类法：A/B/C A: 到达过程 B: 服务过程 C: 机器台数 M: 指数分布 (Markovian过程) G: 完全一般的分布 D: 常数分布（确定性情形）.,A,B,C,队,服务员,102,对于排队问题的建议 为顾客确定一个可以接受的等待时间 在等待过程中尽量分散顾客注意力 及时告诉顾客他们期望了解的情况 决不能让顾客看到雇员未在工作 对顾客进行分类 对服务员进行培训 鼓励顾客在非高峰时间到达 制定可以改善顾客服务的计划,2.1 随机服务系统的构成,103,2.2 最简单的随机服务系统,最简单的随机服务系统是单队单阶段，按FIFS规则的等待制系统 设到达率服从泊松分布，则单位随机到达x个顾客的概率为：,式中，e为自然对数的底，e=2.71828; x=0,1,2,3,；,104,2.2 最简单的随机服务系,105,设系统服务率服从负指数分布， 其概率密度和分布函数分别为 则 ETs=1/ ; Var Ts=1/ 2 ; Ts=1/ (2) ETs=1/ ：每个顾客的平均(期望)服务时间； :单位时间服务的顾客数，平均(期望)服务率；,2.2 最简单的随机服务系统,106,其它要用到的符号为：,107,2.2 最简单的随机服务系统,例：某医院急诊室有一个外科医生全日工作。急诊病人的到达率服从泊松分布，外科医生的服务率服从负指数分布。问： (1)该外科医生平均有多少时间在救护病人？ （2）急诊病人平均等多久才能得到治疗？,解：,已知,108,课堂练习,平均服务率=60人/小时 平均到达率=45人/小时 求：快餐店空闲的概率 快餐店平均服务时间（平均服务率） 顾客平均等待时间 （1）快餐店空闲的概率 P0=1-/ =1-45/60=25% (2）平均服务率= 利用率 =/ =45/60=75% （3）顾客平均等待时间 Wq=Wt-1/=/ (-)= 45/60*（60-45） =0.05小时=3分钟,109,三、人员班次的计划,人员班次安排涉及人力资源的具体使用 既要考虑工作需要，又要保证员工每周2天休息 人员班次计划，一般以周为计划的时间单位。 采取周一至周日的表示法，一周内有5天平常日和2天周末日。 每个工人每天只能分配一个班次，不同天可以被分配到不同种类的班次，如白班、晚班、夜班等。 周末休息频率用A/B表示：在任意连续B周内，工人有A周在周末休息。,110,一）人员班次计划的分类,按班次计划的特点 个人班次（individual schedule） 公共班次(common schedule) 班次的种类 单班次和多班次 工人的种类 全职与兼职 参数的性质 确定型或随机型班次问题,111,二）单班次问题,特点 每天只有一个班次的工人当班，是最简单、最基本的班次问题 可作为某些特殊的多班次问题的合理近似 求解单班次问题的思想和方法，对建立求解一般的人员班次问题的方法能提供一些启示。,112,设某单位每周工作7天，每天一班，平常日需要N人，周末需要n人。求在以下条件下的班次计划 (1）保证工人每周有两个休息日； （2）保证工人每周的两个休息