作业计划课件

第十二章时间进度安排

Scheduling1第十二章时间进度安排§12.1作业排序的基本概念；§11.2制造业的时间进度安排§11.3少量生产系统的时间进度安排§11.4服务业的时间进度安排2教学目的与手段教学目的：使学生对排序的相关问题有一定认识，了解排序在企业生产运营管理中的地位与应用。教学手段：讲述(1)了解车间作业管理的主要工作；(2)了解作业排序的目标与分类；(3)掌握制造业作业排序的一般方法与数学方法；(4)了解服务业排序的原则与方法。教学重点流水线的排序单件生产排序服务业的排序教学难点排序规则、排序算法3排序的作用实例1：油漆生产顺序某企业生产白、灰、红、蓝四种油漆，每次生产前都有清洗容器的调整准备时间。按怎样的顺序，总的调整准备时间最少？实例2：复印排序问题有四人同时到达复印室，每人的复印量不同，如何安排顺序，使得他们的平均等待时间和平均流程时间最小？

5方案1：白-灰-红-蓝T-setup=12

方案2：蓝-红-灰-白T-setup=20

6一、基本概念1、排序（Sequencing）：排序就是要将不同的工作任务安排一个执行的顺序，使预定的目标最优化。实际上就是要解决如何按时间的先后，将有限的人力、物力资源分配给不同工作任务，使预定目标最优化的问题。流程规划战略能力计划综合计划主生产计划（MPS）物料需求计划（MRP）生产作业计划——将MRP转化为各个车间、班组、工作地的任务7有关的名词术语“派工”(Dispatching)是在作业计划制定以后，按照作业计划的要求，将具体生产任务通过工票或施工单的形式下达到具体的机床和工人，属于通常所说的“调度”范围。“赶工”(Expediting)是在实际进度已落后于计划进度时采取的行动，也属于通常所说的“调度”范围。“调度”是作业计划编制后实施生产控制所采取的一切行动，“编制作业计划”是加工制造发生之前的活动作业排序也就是要确定工件在机器上的加工顺序，可用一组工件代号的一种排列来表示。如，用（1，6，5，4，3，2）表示加工顺序：J1—J6—J5—J4—J3—J2。9一、基本概念2、作业计划（Scheduling）作业计划与排序不是一回事，它不仅要确定工件的加工顺序，而且还要确定每台机器加工每个工件的开工时间和完工时间。如果按最早可能开（完）工时间来编排作业计划，则排序完后，作业计划也就确定了。3、制定作业计划的影响因素工件到达的方式(Thejobarrivalpattern)车间内机器的数量(Numberandvarietyofmachinesintheshop)车间拥有的人力资源(Numberofworkersintheshop)工件移动方式(Particularflowpatterns)不同调度准则的评价(Evaluationsofalternativerules)104、作业计划与控制的关系作业计划：给生产活动(ProductionActivities)制定详细时间表生产控制：以生产计划和作业计划为依据，检查、落实计划执行情况，发现偏差即采取纠正措施，保证实现各项各项计划目标5、排序与编制作业计划的差别上面讲了编制作业计划的问题.在编制作业计划过程中,有一个问题需要管理人员注意,即投入生产过程的作业顺序的安排.·作业计划是安排零部件（作业、活动）的出产数量、设备及人工使用、投入时间及出产时间。·排序，给出零部件在一台或一组设备上加工的先后顺序的工作。11编制作业计划要解决的问题通过制定作业计划，可以使企业：满足交货期要求MeetDueDates使在制品库存最小Minimizework-in-processinventory使平均流程时间最小Minimizetheaverageflowtimethroughthesystem提供准确的工件状态信息Provideforaccuratejobstatusinformation提高机器/工人的时间利用率Provideforhighmachine/workertimeutilization(Minimizeworkeridletime)减少调整准备时间Reducesetuptimes使生产和人工成本最低Minimizeproductionandworkercosts13二、作业排序问题的分类（一）两种基本形式1、劳动力作业排序（人员排序）：主要确定人员何时工作2、生产作业排序：将不同工件安排到不同设备上或安排不同的人做不同的工作。在制造业中，生产作业排序是最主要的——加工工件是焦点；在服务业中，劳动力作业排序是主要的——服务的及时性是影响公司竞争力的主要因素。14（二）制造业作业排序的分类1、按机器的种类和数量单台机器的排序问题多台机器的排序问题2、按工件到达车间的情况单件作业（Job-shop）排序问题：工件的加工路线不同流水作业（Flow-shop）排序问题：所有工件的加工路线完全相同静态排序问题动态排序问题3、按目标函数的性质平均流程时间最短的排序问题使误期完工的工件数最少的排序问题……15三、作业排序的任务和目标有效的作业排序应做到以下几点：1、对将要做的工作进行优先权设定，以使工作任务按最有效顺序排列；2、针对具体设备分配任务及人力，通常以可利用的能力为基础；3、以实施为目标分配工作，以使工作任务如期完成。目标满足交货期要求极小化提前期极小化准备时间或成本极大化设备利用或劳动力的利用17四、作业排序方案的评价标准1、工件流程时间：从工件开始加工至完工的时间。包括在各个机器之间的移动时间、等待时间、加工时间等。2、全部完工时间（最长流程时间）完成一组工件所需的全部时间——从第一个工件在第一台机器开始加工，到最后一个工件在最后一台机器上完成加工时为止所经过的时间。3、延迟：比预定完工时间延迟的时间部分4、在制品库存5、总库存：计划入库量与现有库存量的总和6、利用率：一台机器或一个工人的有效生产时间占总工作时间的百分比。注：这些标准之间并不完全独立18五、优先调度规则1、SPT（ShortestProcessingTime）规则（最短加工时间规则）优先选择加工时间最短的工件——使工件的平均流程时间最短，从而减少在制品量。2、FCFS（FirstComeFirstServed）规则（先到先服务规则）按订单的先后顺序进行加工（优先选择最早进入可排工序集合的工件）——来自排队论，对工件较公平3、EDD（EarliestDueDate）规则优先选择完工期限最紧的工件——使工件延误时间最少根据不同的目标确定优先规则，按优先规则确定各任务的优先权，由此排定加工顺序。4、MWKR（MostWorkRemaining）规则

优先选择余下加工时间最长的工件——使不同工作量的工件完工时间尽量接近。19优先调度规则事例在理论方面，排序问题的难度随着机床数量的增加而增大，而不是随需加工的作业数量的增加而增大。（一）n个作业单台机床的排序零件所需标准加工时间（h）顾客预计取货时间（h）A810B612C1520D318E122221用SPT规则得出的作业排序加工顺序开始工作加工时间结束工作流程时间预计取货时间实际取货时间提前小时数拖延时间

总数

平均

平均在制品库存102/44=2.32（个）平均总库存120/44=2.78（个）D0333181815B369912123A98171710177E1712292922297C29154444204424102120183820.43.67.622EDD规则加工顺序开始工作加工时间结束工作流程时间预计取货时间实际取货时间提前小时数拖延时间

总数

平均

平均在制品库存115/44=2.61（个）平均总库存118/44=2.68（个）A088810102B86141412142D143171718181C17153232203212E32124444224422115118336230.67.223一、假设条件与符号说明一个工件不能同时在几台不同的机器上面加工工件在加工过程中采取平行移动的方式不允许中断每道工序只在一台机器上面完成工件数,机器数和加工时间已知,加工时间与加工顺序无关每台机器同时只能加工一个工件25符号说明Ji------工件iMj------机器jpij------工件i在机器j上的加工时间,Pi------工件i总的加工时间Pi=pijri------工件i的到达时间di------工件i的完工期限

26说明一般来说，排列排序问题的最优解不一定是相应流水车间排序问题的最优解，但一般是比较好的解。而对于仅有2台或3台机器的情况，则排列排序问题的最优解一定是相应流水车间排序问题的最优解。流水线是流水车间(Flowshop)典型的代表，每个零件的加工路线都一致。只要加工路线一致：M1，M2,

M3，…..，Mm,不要求每个零件都经过每台机器加工29二、流水作业排序问题流水车间(Flowshop):工件的加工路线都一致，典型的如流水线一）最长流程时间的计算二）两台机器排序问题的最优算法三）多台机器排序问题的启发式算法Work

Center#1WorkCenter#2Output30一）最长流程时间的计算目标函数Fmax最短；n/m/p/Fmax问题从第一个工件在第一台机器开始加工时算起，到最后一个工件在最后一台机器上完成时为止所经过的时间假设：所有工件的到达时间都为零31例11.1按顺序S=(6,1,5,2,4,3)加工

求Fmax6/4/p/Fmax问题序号为1的工件在序号为1的机器上面的加工时间为432流水作业排序问题——工件加工路线相同6个零件以相同的顺序经过4台机床每个零件在每台机床上面的加工时间可以不一样123433按顺序S=(6,1,5,2,4,3)列出加工时间矩阵工件代号i615243Pi1

Pi2

Pi3

Pi4

34按顺序S=(6,1,5,2,4,3)列出加工时间矩阵工件代号i615243Pi12Pi25Pi35Pi4135按顺序S=(6,1,5,2,4,3)列出加工时间矩阵工件代号i615243Pi124Pi254Pi355Pi41436按顺序S=(6,1,5,2,4,3)列出加工时间矩阵工件代号i615243Pi1244213Pi2544576Pi3555857Pi414323437按顺序S=(6,1,5,2,4,3)列出加工时间矩阵工件代号i615243Pi1244213Pi2544576Pi3555857Pi4143234238按顺序S=(6,1,5,2,4,3)列出加工时间矩阵工件代号i615243Pi1244213Pi2544576Pi3555857Pi4143234261012131639按顺序S=(6,1,5,2,4,3)列出加工时间矩阵工件代号i615243Pi1244213Pi2544576Pi3555857Pi414323426101213167121340按顺序S=(6,1,5,2,4,3)列出加工时间矩阵工件代号i615243Pi1244213Pi2544576Pi3555857Pi4143234261012131671213比较的目的是确定生产能否连续，是否有机器等待时间41按顺序S=(6,1,5,2,4,3)列出加工时间矩阵工件代号i615243Pi1244213Pi2544576Pi3555857Pi4143234261012131671213117+4=1142按顺序S=(6,1,5,2,4,3)列出加工时间矩阵工件代号i615243Pi1244213Pi2544576Pi3555857Pi4143234261012131671213111712+5=1743按顺序S=(6,1,5,2,4,3)列出加工时间矩阵工件代号i615243Pi1244213Pi2544576Pi3555857Pi414323426101213167121311172115222520303227353833424644课堂练习：已知加工时间矩阵：顺序S=(1,4,6,3,5,2)45工件代号i146352Pi1453486Pi2391375Pi3768259Pi456392449121624307181922313614243234394819303544465246二）两台机器排序问题的最优算法约翰森法则如果Min(ai,bj)<Min(aj,bi),则工件i应该排在工件j之前。约翰逊规则（方法）——目标函数是使全部完工时间最少约翰森算法Step1找出最短加工时间Step2如果最短加工时间发生在第一台设备上，则把该零件安排在序列的最前端；如果最短加工事件发生在地二台设备上，则把该零件安排在序列的最末端Step3如果同时有两个以上最短时间，可以任选一个，先进行排序Step4重复以上步骤，直到所有零件排完为止47约翰森法则示例

ABCD加工周期时间工序1234连续生产情况下，总加工周期为A+B+C+D，所以A和D较小时可以减少总周期48举例工件号123456ai518534bi722474将工件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

=2849Johnson算法的改进1.将所有ai≤

bi的工件按ai值不减的顺序排成一个序列A；2.将ai＞bi的工件按bi值不增的顺序排成一个序列B；3.将A放到B之前，就构成了一个最优加工顺序。50举例工件号123456ai518534bi722474A={2561}B={43}S={256143}51课后习题i12345678ai971082154bi6231587452课后习题1i12345678ai971082154bi62315874S=64523871S=6452387153最优顺序：65871324

12459107885476321

3

7

12

21

313846914182531344047aibi最优顺序下的加工周期为47S=6452387154

12594107885764321

3

8

17

21

313846914212731344047aibiS=64523871最优顺序：65718324最优顺序下的加工周期为4755三）多台机器排序问题的启发式算法要求最优，计算量相当大，甚至连计算机也难以求解——无法用于实际生产中。人们提出了多种启发式算法，以便以最小的计算量得到足够好的结果。关键工件法1.计算每个工件的总加工时间，将加工时间最长的工件作为关键工件C；2.对于余下的工件，若pi1≤pim则按pi1不减的顺序排成一个序列Sa

,若pi1>pim则按pim不增的顺序排成一个序列Sb;3.顺序（Sa,C,Sb）即为所求顺序。56举例工件i1234Pi12163Pi24829Pi3548211131614CSa(2,1)Sb(4)所求顺序：（2,1,3,4）57四）相同零件不同移动方式下加工周期的计算当n个零件相同，则无排序问题。但不同移动方式下的加工周期不同三种典型的移动方式顺序移动方式：一批零件全部加工完成后，整批移动到下道工序加工平行移动方式：单个零件加工完成后，立即移动到下道工序加工平行顺序移动方式：两者混合58顺序移动方式

加工周期时间工序1234顺序移动方式优点：运输次数少、设备利用充分、管理简单缺点：加工周期长59

设零件批量为n（件），工序数目为m，一批零件不计算工序间运输时间，只考虑加工时间，设其加工的周期为T（分钟），零件在i道工序的单件工时为（分钟/件），i=1.2…n.则该批零件的加工周期为：

60平行移动方式工序1234时间加工周期优点：加工周期短缺点：运输频繁、设备空闲时间多且零碎61零件平行移动的加工周期为：

tL=最长单件工序时间62平行顺序移动方式特点：既保持一批零件顺序加工，有尽可能使相邻工序加工时间平行进行。如图所示：1234时间加工周期工序（4-1）*5=15（4-1）*10=3063平行顺序移动方式（续）平行顺序移动加工周期计算

T=4*(10+5+15+10)-(4-1)*(5+5+10)=100分钟-64三、作业排序的一般方法1、甘特图甘特图是作业排序中最常用的一种工具。它是由亨利·劳伦斯·甘特(HenryL.Gantt)在1917年首先提出来的。甘特是泰勒创立和推广科学管理制度的亲密的合作者，也是科学管理运动的先驱者之一。这种方法是基于作业排序目的，将活动与时间联系起来的最早尝试之一。有两种基本形式的甘特图：作业进度图和机器图。65

甘特图：机床1机床2A2（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机床2A2（4）空闲A3（5）A2（5）A5（10）A3（3）A1（12）A5（10）空闲空闲A4（15）A1（22）空闲A4（6）全部流程时间：55、59662、I/O控制I/O控制，是input/output控制的缩写，它是制造计划和控制系统的主要特征。它的主要原则是：工作中心的输入永远不能超过工作中心的输出。当输入超过输出时，就会在工作中心产生物流堆积，结果将会延长上游作业的预计提前期。673、作业排序的数学方法3.1约翰逊法约翰逊法是作业排序中比较常用的一种排序方法。它适用的条件是：n个工件经过两台设备(有限台设备)加工，所有工件在有限设备上加工的次序相同。约翰逊法操作步骤：(1)选出最短加工时间i，若最短加工时间有多个，任选1个；(2)若i出现在机床1，它对应的工件先安排加工，否则放在最后安排，安排后划去该工件；(3)重复上两个步骤，直到所有工件都排序完毕。683.2C-D-S法CDS法，即穷举法，是坎贝尔(Campbell)、杜德克(Dudek)、史密斯(Smith)3人提出的一个启发式算法，简称C-D-S法。穷举法的基本思想是不重复、不遗漏地穷举所有可能情况，从中寻找满足条件的结果。穷举法的操作步骤：(1)取首末两道工序，用约翰逊法排序，求Fmax；(2)取首两道工序的和及尾两道工序的和，用约翰逊法排序，求Fmax；(3)取首三道工序的和及尾三道工序的和，用约翰逊法排序，求Fmax。以此类推，直到所有的情况(m-1种)都考虑到后，比较得到的Fmax，找出其中最小的那个排序方案为所求排序方案。693.3匈牙利法1.匈牙利法的基本原理匈牙利法基于下面两个性质：设一个指派模型的效益矩阵为(cij).若(cij)的第i行元素均减去一个常数ui(i＝1,2,…,n)，第j列元素均减去一个常数vj(j＝1,2,…,n)，得到一个新的效益矩阵(bij)，其中每一元素bij＝cij-ui-vj，则以(bij)为效益矩阵的指派模型的最优解也是以(cij)为效益矩阵的指派模型的最优解。如果取ui(i＝1,2,…,n)为第i行元素的最小值，vj(

j=1,2,…,n)为第j行元素的最小值，则得到新的效益矩阵(bij)为非负矩阵(即所有元去均为非负数)。这说明可以通过求以(bij)为效益矩阵的指派模型的最优解得到原指派模型的最优解70直观地讲，求最优解方阵就是在效益矩阵中找到n个元素，要求在不同行、不同列上，使这些元素之和最小。将这n个元素所在位置赋值为“1”，其他元素均为“0”，就得到最优解方阵。效益矩阵(bij)中每行、每列的最小元素为“0”，因此，求指派模型(P)的最优解又转化为在矩阵(bij)中找出n个在不同行、不同列上的“0”元素，这就是匈牙利法的基本思路。712.匈牙利法求解步骤匈牙利法求解具体步骤如下。第一步：从效益矩阵C的每行减去该行的最小元素，从所得矩阵的每列减去该列的最小元素，得新的效益矩阵B。第二步：构造效益矩阵B的补矩阵D。第三步：判断D是否为最优方案。是，则转第五步。第四步：检查bij的每行、每列，从中找出“0”元素最少的一排(即行或列)，从该排圈出一个“0”元素，若该排有多个“0”元素，则任圈一个，用⊙表示，把刚得到的⊙元素所在行、列划去，在剩下的矩阵中重复上述过程，直至找到n个⊙。将n个⊙所在的位置赋值“1”，其他元素赋值为“0”，得到的矩阵就是原指派模型的最优解矩阵。72作业排序总结1.n个工件在一台设备上加工2.n个工件在二台设备上加工，且加工顺序相同3.n个工件在三台设备上加工4.2个工件在m台设备上加工5.n个工件在m台设备上加工SPT约翰逊和贝尔曼规则虚拟机床图解法计算机处理73课后习题3已知：n=4m=5t1=10t2=4t3=8t4=12t5=6求：T顺、T平、T平顺74解：T顺==4*(10+4+8+12+6)=160T平=T平顺==(10+4+8+12+6)+3*12=76=160-3*(4+4+8+6)=9475§11.3少量生产系统的时间进度安排一、问题的描述二、两种作业计划的构成三、求解一般n/m/G/Fmax问题的启发式方法76一、问题的描述D=1,1,11,2,31,3,22,1,32,2,12,3,2T=241345问题描述流水(i,j)(工件，工序)单件(i,j,k)(工件，工序，机器)(i，j，k)：表示工件i的第j道工序是在机器k上进行。加工描述矩阵D：每一行描述一个工件的加工，每一列的工序序号相同。77一、问题的描述加工时间矩阵T：与D相对应。D=1,1,11,2,31,3,22,1,32,2,12,3,2T=46357478一、问题的描述加工顺序矩阵S：每一行与机器相对应，每一列与工件相对应。D=1,1,11,2,31,3,22,1,32,2,12,3,2S=1,1,12,2,11,3,22,3,22,1,31,2,379一、问题的描述用方块图表示：D=1,1,11,2,31,3,22,1,32,2,12,3,2S=1,1,12,2,11,3,22,3,22,1,31,2,3T=4635741,1,12,1,31,2,32,2,11,3,22,3,2M1M2M380二、两种作业计划的构成1、能动作业计划的构成各工序都按最早可能开(完)工时间安排且任何一台机器的每段空闲时间都不足以加工一道可加工工序。符号说明：{Ot}第t步可以排序的工序的集合{St}t步之前已排序的工序构成的部分作业计划Tk{Ot}中工序Ok的最早可能开工时间T’k{Ot}中工序Ok的最早可能完工时间81二、两种作业计划的构成2、能动作业计划的构成步骤：①设t＝1，{St}为空，{Ot}为各工件第一道工序的集合②求最小的最早完工时间T*=min{T’k},并找到出现T*的机器M*，若有多台，任选一台。③从{Ot}中跳出满足以下两条件的工序Oj需要机器M*加工；Tj<T*④将确定的Oj放入{St}，从{Ot}中消去Oj并将Oj的紧后工序放入{Ot}中，使t=t+1。⑤若还有未安排的工序，转步骤②；否则，停止。82一个实例：D=1,1,11,2,31,3,22,1,32,2,12,3,2T=241345i1{Ot}TkT’kT*M*Oj1,1,1022M11,1,12,1,30321,2,3263M32,1,32,1,30331,2,3377M31,2,32,2,13741,3,2787M12,2,12,2,13751,3,2788M21,3,22,3,2712613M22,3,22,3,281383得到加工顺序矩阵：S=1,1,12,2,11,3,22,3,22,1,31,2,31,1,12,1,31,2,32,2,11,3,22,3,2M1M2M32377381384二、两种作业计划的构成2、无延迟作业计划的构成没有任何延迟出现的能动作业计划。所谓“延迟”，指有工件等待加工时，机器出现空闲，即使这段空闲时间不足以完成一道工序。85二、两种作业计划的构成无延迟作业计划的构成步骤：①设t＝1，{St}为空，{Ot}为各工件第一道工序的集合。②求最小的最早完工时间T*=min{Tk},并找到出现T*的机器M*，若有多台，任选一台。③从{Ot}中跳出满足以下两条件的工序Oj需要机器M*加工；Tj=T*④将确定的Oj放入{St}，从{Ot}中消去Oj并将Oj的紧后工序放入{Ot}中，使t=t+1。⑤若还有未安排的工序，转步骤②；否则，停止。86一个实例：D=1,1,11,2,31,3,22,1,32,2,12,3,2T=241345i1{Ot}TkT’kT*M*Oj1,1,1020M11,1,12,1,30321,2,3260M32,1,32,1,30331,2,3373M31,2,32,2,13741,3,2783M12,2,12,2,13751,3,2787M22,3,22,3,2712612M21,3,22,3,212130M33M17M287得到加工顺序矩阵：S=1,1,12,2,12,3,21,3,22,1,31,2,31,1,12,1,31,2,32,2,11,3,22,3,2M1M2M323773121388三、三类启发式算法能动作业计划和无延迟作业计划尽管不一定是最优作业计划，但一般是较好的作业计划，特别是无延迟作业计划能提供令人满意的解。一般能动作业计划和无延迟作业计划都有多个，可用启发式方法从中选择结果较好的作业计划。一般来说，以构成无延迟作业计划的步骤为基础的启发式算法比以构成能动作业计划的步骤为基础的启发算法的效果要好。（1）优先调度法则构成两种作业计划的第（3）步一般都有多道工序可以满足，按不同的优先调度法则来选择工序，可以得出满足不同目标函数的作业计划计算量小已经提出100多种优先调度法则89优先调度法则FCFS（firstcome,firstserved）选择最早进入可排序集合的工序SPT(shortestprocessingtime）选择加工时间最短的工序EDD（earliestduedate）选择完工期限最紧的工序SCR(smallestcriticalratio)选择临界比最小的工件MWKR(mostworkremaining)选择余下加工时间最长的工件LWKR(leastworkremaining)选择余下加工时间最短的工件MOPNR(mostoperationsremaining)选择余下工序数最多的工件RANDOM随机挑选一个工件90（2）随机抽样法从全部能动计划或无延迟计划中随机抽样，得出多个作业计划，从中取优。（3）概率调度法将优先调度法则与随机抽样法结合对不同工件将优先调度法则分配不同的挑选概率，效果较好91§11.4服务业的时间进度安排一、服务业的作业排序二、随机服务系统三、人员班次计划92一、服务业的作业排序1、服务作业排序与生产作业排序的主要区别所提供产品的类型由于服务过程有顾客参与,作业排序对他们有直接影响,并因此成为服务的一部分,而在生产作业排序对产品的最终使用者没有直接影响排序内容在服务业中,排序要定义服务交易的时间或消耗点；而在制造业中仅仅定义产品生产的操作步骤过程控制在服务业中,顾客参与服务过程,并且对全部操作过程施加影响.人员规模在顾客化服务中,服务的输出与劳动力的最佳规模之间的关系很难确定；而生产作业中,两者之间的关系有紧密联系,因此最佳的作业顺序可以被计算出来

932、服务业有两种基本的排序方式：1）服务作业排序方法之一——安排顾客需求将顾客需求分配到服务能力的不同时间段内；预约：如医生、律师等的服务预定：顾客预定旅馆房间、火车或飞机票排队等待：一种为顾客排序的不太准确的方法是允许需求积压，让顾客排队等待。例如，餐馆、银行、零售商店等。2）服务作业排序方法之二——安排服务人员将服务人员安排到顾客需求的不同时间段内。当需要快速响应顾客需求、且需求量大致可以预计时，通常使用这种方法。如邮局营业员、护士、警察的工作日和休息日安排；一天营业24小时、一周7天都营业的商店保安人员安排；等等

一、服务业的作业排序94二、随机服务系统研究排队现象有助于确定服务能力，控制队长，发挥发挥设施能力（1）由于顾客到达和服务时间的随机性，现实中的排队现象几乎不可避免；（2）排队过程，通常是一个随机过程，排队论又称“随机服务系统理论”；2.1随机服务系统的构成2.2最简单的随机服务系统952.1随机服务系统的构成排队系统顾客源排队结构顾客到来排队规则服务规则顾客离去服务机构。。。重要问题：应尽量使顾客等待时间缩短——排队论的方法962.1随机服务系统的构成排队规则顾客排队方式：等待制/即时制(损失制);排队系统容量：有限制/无限制;排队队列数目:单列/多列;是否中途退出:允许/禁止;是否列间转移:允许/禁止;(仅研究禁止退出和转移的情形)972.1随机服务系统的构成服务台(员)为顾客服务的顺序:a)先到先服务(FCFS);b)后到先服务(LCFS);c)随机服务;d)优先服务;98

2.1随机服务系统的构成

结构类型单队，单阶段多队，单阶段单队，多阶段99多队，多阶段混合式

2.1随机服务系统的构成

结构类型1002.1随机服务系统的构成

Kendall分类法：A/B/CA:到达过程B:服务过程C:机器台数M:指数分布(Markovian过程)G:完全一般的分布D:常数分布（确定性情形）.ABC队服务员101对于排队问题的建议为顾客确定一个可以接受的等待时间在等待过程中尽量分散顾客注意力及时告诉顾客他们期望了解的情况决不能让顾客看到雇员未在工作对顾客进行分类对服务员进行培训鼓励顾客在非高峰时间到达制定可以改善顾客服务的计划

2.1随机服务系统的构成1022.2最简单的随机服务系统最简单的随机服务系统是单队单阶段，按FIFS规则的等待制系统设到达率服从泊松分布，则单位随机到达x个顾客的概率为：式中，e为自然对数的底，e=2.71828;x=0,1,2,3,…；

1032.2最简单的随机服务系模型分布服务阶段顾客源到达人数排队规则服务时间队列长度1单通道单一无限泊松FCFS指数无限2单通道单一无限泊松FCFS常数无限3多通道单一无限泊松FCFS指数无限4单通道单一有限泊松FCFS指数无限104设系统服务率服从负指数分布，其概率密度和分布函数分别为

则E[Ts]=1/;Var[Ts]=1/2;[Ts]=1/(2)E[Ts]=1/：每个顾客的平均(期望)服务时间；

:单位时间服务的顾客数，平均(期望)服务率；2.2最简单的随机服务系统105

其它要用到的符号为：1062.2最简单的随机服务系统例：某医院急诊室有一个外科医生全日工作。急诊病人的到达率服从泊松分布，外科医生的服务率服从负指数分布。问：(1)该外科医生平均有多少时间在救护病人？（2）急诊病人平均等多久才能得到治疗？解：已知107课堂练习平均服务率=60人/小时平均到达率λ=45人/小时求：快餐店空闲的概率快餐店平均服务时间（平均服务率）顾客平均等待时间（1）快餐店空闲的概率P0=1-λ/=1-45/60=25%(2）平均服务率=利用率

ρ=λ/=45/60=75%（3）顾客平均等待时间Wq=Wt-1/=λ/(-λ)=45/[60*（60-45）]=0.05小时=3分钟108三、人员班次的计划人员班次安排涉及人力资源的具体使用既要考虑工作需要，又要保证员工每周2天休息人员班次计划，一般以周为计划的时间单位。采取周一至周日的表示法，一周内有5天平常日和2天周末日。每个工人每天只能分配一个班次，不同天可以被分配到不同种类的班次，如白班、晚班、夜班等。周末休息频率用A/B表示：在任意连续B周内，工人有A周在周末休息。109一）人员班次计划的分类按班次计划的特点个人班次（individualschedule）公共班次(commonschedule)班次的种类单班次和多班次工人的种类全职与兼职参数的性质确定型或随机型班次问题110二）单班次问题特点每天只有一个班次的工人当班，是最简单、最基本的班次问题可作为某些特殊的多班次问题的合理近似求解单班次问题的思想和方法，对建立求解一般的人员班次问题的方法能提供一些启示。111设某单位每周工作7天，每天一班，平常日需要N人，周末需要n人。求在以下条件下的班次计划(1）保证工人每周有两个休息日；（2）保证工人每周的两个休息日为连休；（3）除保证条件（1）外，连续2周内，每名工人有一周在周末休息。（4）除保证条件（2）以外，连续2周内，每名工人有一周在周末休息。设Wi为条件（i）下最少的工人数；[x]为大于等于x的最小整数；X在作业计划中表示休息日。

112条件（1），每周休息2天。对条件（1），所需劳动力下限为W1＝max{n,N+[2n/5]}求解步骤：安排[W1－n]名工人在周末休息；对余下的n名工人从1到n编号，1号至N号工人周一休息；安排紧接着的[W1－N]名工人第二天休息，这里，工人1紧接着工人n；如果5W1>5N+2n，则有多余的休息日供分配，此时可按需要调整班次计划，只要保证每名工人一周休息两天，平日有N人当班即可。113例：N=5,n=8，求班次安排。解：W1＝max{8,5+[2×8/5]}＝9工人号一二三四五六日一二三四五六日1××××2××××3××××4××××5××××6××××7××××8××××9××××条件1下的班次计划114条件（2），每周连休2天。对