5作业计划与控制11.13.ppt

第第5章章 作业计划与控制作业计划与控制Operations Scheduling and Controlling排序问题的基本概念排序问题的基本概念单台机器的排序问题单台机器的排序问题多台机器的排序问题多台机器的排序问题生产作业控制生产作业控制编制作业计划要解决的问题编制作业计划要解决的问题任务分配任务分配任务分配任务分配：每个工人、每个工作地的日生产任务：每个工人、每个工作地的日生产任务编制作业计划（编制作业计划（Scheduling Scheduling）：将资源分配给）：将资源分配给不同的任务，按照既定的优化目标，确定各种资不同的任务，按照既定的优化目标，确定各种资源利用的时间问题源利用的时间问题工厂：对每个工人和工作地安排每天的生产任工厂：对每个工人和工作地安排每天的生产任务，规定开始时间和完成时间务，规定开始时间和完成时间医院：安排病人手术医院：安排病人手术安排手术室、配备手安排手术室、配备手术器械、手术医师和护士术器械、手术医师和护士学校：安排上课时间表，使学生能按规定的时学校：安排上课时间表，使学生能按规定的时间到规定的教室听事先安排的教师讲课间到规定的教室听事先安排的教师讲课项目计划管理：作业计划项目计划管理：作业计划生生生生 产产产产 排排排排 序序序序：通通 过过 排排 序序 方方 法法 编编 制制 生生 产产 计计 划划，提提 高高 生生 产效率产效率5.1排序的基本概念排序的基本概念 作业计划与排序是一回事么？作业计划与排序是一回事么？作业计划是安排零部件（作业、活动）的出产数量、设备作业计划是安排零部件（作业、活动）的出产数量、设备及人工使用、投入时间及出产时间。及人工使用、投入时间及出产时间。排序，给出零部件在一台或一组设备上加工的先后顺序的排序，给出零部件在一台或一组设备上加工的先后顺序的工作。工作。编制作业计划与排序的概念和目的都是不同的。但是，编编制作业计划与排序的概念和目的都是不同的。但是，编制作业计划的主要工作之一就是要确定出最佳的作业顺序。制作业计划的主要工作之一就是要确定出最佳的作业顺序。根据排序规则对每一个根据排序规则对每一个到到达的工件安排作业顺序达的工件安排作业顺序工作地工作地工件排工件排队等待队等待加工加工来自上游来自上游工作地的工作地的工件工件加工完毕的加工完毕的工件流向下工件流向下一工作地一工作地排序的概念排序的概念生产作业排序就是指对于等候某个设备或工作中心加工的多个生产作业排序就是指对于等候某个设备或工作中心加工的多个任务，确定这些任务加工的先后次序。任务，确定这些任务加工的先后次序。目的：提高设备或工作中心的效率、减少在制品占用量、缩短目的：提高设备或工作中心的效率、减少在制品占用量、缩短生产周期、保证按期交货生产周期、保证按期交货作业排序（作业排序（sequencing）的目标）的目标作业排序是解决各个生产层次中生产任务的加工顺序问作业排序是解决各个生产层次中生产任务的加工顺序问题，既包括哪个生产任务先投产，哪个生产任务后投入，题，既包括哪个生产任务先投产，哪个生产任务后投入，还包括在同一设备上不同工件的加工顺序。还包括在同一设备上不同工件的加工顺序。作业排序（作业排序（sequencing）：确定工件在设备上的加工顺序。：确定工件在设备上的加工顺序。作业计划（作业计划（scheduling）：不仅包括确定工件的加工顺序，还）：不仅包括确定工件的加工顺序，还 包括确定设备加工每个工件的开始时间和结束时间。包括确定设备加工每个工件的开始时间和结束时间。排序的目标排序的目标：如何在尽可能满足各种约束条件的情况下，如何在尽可能满足各种约束条件的情况下，给出一个令人满意的排序方案。给出一个令人满意的排序方案。一、有关的名词术语一、有关的名词术语排序排序(Sequencing)(Sequencing)：确定零件在机器上的加工顺序：确定零件在机器上的加工顺序编制作业计划编制作业计划(Scheduling)(Scheduling)：加工制造发生之前的活动（火车时刻表）。：加工制造发生之前的活动（火车时刻表）。包括确定加工顺序、加工任务的分配和加工每个零件的开始和完成时间包括确定加工顺序、加工任务的分配和加工每个零件的开始和完成时间 调度：作业计划编制后实施生产控制所采取的一切行动（火车运行的安调度：作业计划编制后实施生产控制所采取的一切行动（火车运行的安排，发生晚点后的处理）排，发生晚点后的处理）派工（派工（Dispatching Dispatching）：在作业计划制定以后，按照作业计划的要）：在作业计划制定以后，按照作业计划的要求，将具体生产任务通过工票或施工单的形式下达到具体的机床和工求，将具体生产任务通过工票或施工单的形式下达到具体的机床和工人人赶工（赶工（Expediting Expediting）：在实际进度已落后于计划进度时采取的行动）：在实际进度已落后于计划进度时采取的行动控制（控制（Controlling Controlling）：）：机器：表示机器：表示“服务者服务者”，可以是工厂里的各种机床，也可以是维修工人；，可以是工厂里的各种机床，也可以是维修工人；可以是轮船要停靠的码头，也可以是电子的计算机中央处理单元、存贮可以是轮船要停靠的码头，也可以是电子的计算机中央处理单元、存贮器和输入、输出单元器和输入、输出单元零件：代表零件：代表“服务对象服务对象”。可以是单个零件，也可以是一批相同的零件。可以是单个零件，也可以是一批相同的零件加工路线：零件加工经过不同机器构成的路线。（某零件要经过车、铣、加工路线：零件加工经过不同机器构成的路线。（某零件要经过车、铣、占、磨的路线加工，我们可以用占、磨的路线加工，我们可以用M1,M2,M3,M4M1,M2,M3,M4来表示）来表示）加工顺序：表示每台机器加工加工顺序：表示每台机器加工n n个零件的先后顺序，是排序要解决的问题个零件的先后顺序，是排序要解决的问题4 4参数表示法参数表示法R.W.Conway等人在等人在Theory of Scheduling中提出的表示中提出的表示方法，该方法只用方法，该方法只用4 4个参数就可以表示大多数不同的排序问个参数就可以表示大多数不同的排序问题。即：题。即：n/m/A/Bn/m/A/Bn n 零件数零件数m m 机器数机器数A A 作业类型作业类型在在A A的位置若标以的位置若标以“F”“F”，则代表流水作业排序问题，则代表流水作业排序问题若标以若标以“P”“P”，则表示流水作业排列排序问题，则表示流水作业排列排序问题若标以若标以“G”“G”，则表示一般单件作业排序问题，则表示一般单件作业排序问题当当m m1 1，则，则A A处为空白，因为对于单台机器的排序问题处为空白，因为对于单台机器的排序问题来说，无所谓加工路线问题来说，无所谓加工路线问题BB目标函数，通常是使其值最小目标函数，通常是使其值最小例：例：二、二、排序常用的符号排序常用的符号 Ji-工件工件i，i=1,2,.n di-工件工件i的交货期的交货期 Pi-工件工件i的加工时间的加工时间,pij-工件工件i在机器在机器j上的上的加工时间加工时间,j=1,mWi-工件工件i在系统内的等待时间在系统内的等待时间,wij-工件工件i在在机器机器j前的等待时间前的等待时间,j=1,m Ci-工件工件i的完成时间的完成时间,在工件都已到达的情况下在工件都已到达的情况下,Ci=Pi+Wi Fi-工件工件i的流程时间的流程时间，在工件都已到达的情况下在工件都已到达的情况下,Fi=Pi+Wi Li-工件工件i的延误时间的延误时间,Li=Ci-di,Li0 延误延误 Ti-工件工件i的延期量的延期量,Ti=max0,Li Ei-工件工件i提前完成的时间提前完成的时间作业排序的基本分析作业排序的基本分析 1、作业排序的一般假设：、作业排序的一般假设：（1 1）一台设备不得同时加工两个或两个以上的任）一台设备不得同时加工两个或两个以上的任务；务；（2 2）一个任务不能同时在几台设备上加工；）一个任务不能同时在几台设备上加工；（3 3）每个任务必须按照工艺顺序进行加工。）每个任务必须按照工艺顺序进行加工。2、作业排序所需的有关生产信息：、作业排序所需的有关生产信息：任务任务Ji在第在第j个工序个工序Oij（j=1,2,，Ni，i=1,2,，M）在相应的设备上）在相应的设备上Mij（i,j=1,2,N）上所需要的加工时间为）上所需要的加工时间为tij，Ji的可能开始时刻为的可能开始时刻为ri和应完工的和应完工的交货期交货期di。3、作业排序的一般结论：、作业排序的一般结论：平均流程时间的最优排序方案对于平均完工时间、平均延迟以及平均等待平均流程时间的最优排序方案对于平均完工时间、平均延迟以及平均等待时间也是最优的。但是这一结论对于时间也是最优的。但是这一结论对于Fmax和其他最大值目标是不成立的。和其他最大值目标是不成立的。排排排排序序序序问问问问题题题题分分分分类类类类按机器按机器按机器按机器单台机器排序问题单台机器排序问题单台机器排序问题单台机器排序问题多台机器排序问题多台机器排序问题多台机器排序问题多台机器排序问题单件作业排序问题单件作业排序问题单件作业排序问题单件作业排序问题流水线作业排序问题流水线作业排序问题流水线作业排序问题流水线作业排序问题按零件到达车间的情况按零件到达车间的情况按零件到达车间的情况按零件到达车间的情况静态的排序问题静态的排序问题静态的排序问题静态的排序问题动态的排序问题动态的排序问题动态的排序问题动态的排序问题按目标函数的性质分类按目标函数的性质分类按目标函数的性质分类按目标函数的性质分类按参数按参数按参数按参数确定型排序问题确定型排序问题确定型排序问题确定型排序问题随机型排序问题随机型排序问题随机型排序问题随机型排序问题三、排序问题的分类三、排序问题的分类 单台机器的排序问题单台机器的排序问题 n个工件全部经由一台机器处理 J1J2J3Jn机器机器到达系统工到达系统工件的集合件的集合离开系统离开系统（机器）（机器）为实现任务总等待时间最短的目标，保证尽可能多的对象早日加工出来，加速资金周转，只需根据最短加工时间准则对加工对象排序即可。n n项任务在两台机器的排序问题项任务在两台机器的排序问题 n n个工件都必须经过机器个工件都必须经过机器1 1和机器和机器2 2的加的加工，即工艺路线是一致的。工，即工艺路线是一致的。机器机器1 1到达系统工到达系统工件的集合件的集合离开系统离开系统（机器）（机器）J J1 1J J2 2J J3 3J Jn n机器机器2 211.2 流水作业排序问题流水作业排序问题流水线是流水车间流水线是流水车间(Flow shop)(Flow shop)典型的典型的代表，每个零件的加工路线都一致。代表，每个零件的加工路线都一致。只要加工路线一致：只要加工路线一致：M M1 1，M M2 2,M M3 3，.，M Mm m,不要求每个零件都经过每台机器加工不要求每个零件都经过每台机器加工流水线加工方式流水线加工方式一、最长流程时间一、最长流程时间F Fmaxmax的计算的计算最长流程时间又称作加工周期最长流程时间又称作加工周期（1）问题的描述和表示）问题的描述和表示描描述述：n个个不不同同零零件件要要按按相相同同的的加加工工路路线线经经过过m台台机机器器加加工工，目目标标是是使使这这批批零零件件的的加加工工周周期期最最短短（加加工工路路线线确确定定，对对不不同同的的零零件件，根据目标求各个零件的加工次序）根据目标求各个零件的加工次序）表示表示（2）求解加工周期）求解加工周期 加工周期是指第一个零件在第一台机器上开始加工周期是指第一个零件在第一台机器上开始加工到最后一个零件在最后一台机器上完成加工加工到最后一个零件在最后一台机器上完成加工为止，所需要的时间为止，所需要的时间假设，假设，n个零件的加工顺序为个零件的加工顺序为S=(S1,S2,Sn)Si为排在为排在i位加工的零件代号位加工的零件代号 CkSi表示零件表示零件Si在机器在机器Mk上的完工时间上的完工时间 PSik表示零件表示零件Si在在Mk上的加工时间上的加工时间 k=1,2,3,m，i=1,2,3,n总加工周期的计算方法总加工周期的计算方法工件在两台设备上的加工时间工件在两台设备上的加工时间工件编号工件编号 J1 J2 J3 J4 J5设备设备A 3 6 7 1 5设备设备B 2 8 6 4 3例例:在设备在设备A和和B上安排上安排5个工件的加工任务，每项任务的作业时间如个工件的加工任务，每项任务的作业时间如下表所示。求下表所示。求:该顺序的总加工周期该顺序的总加工周期Fmax。图解法：图解法：30AB0表格法表格法工件编号工件编号 J1 J2 J3 J4 J5设备设备A 33 69 716 117 522设备设备B25 817 623 427 330Fmax=306/4/p/F6/4/p/Fmaxmax问题，当按顺序问题，当按顺序S S(6,1,5,2,4,3)6,1,5,2,4,3)加工时，求加工时，求F Fmaxmax.加工周期为加工周期为4646（1）描述和表示）描述和表示描描述述：n个个零零件件经经过过2台台机机器器加加工工，使使加加工工周期最短的流水作业排序问题周期最短的流水作业排序问题表示表示（2）求解方法）求解方法 Johnson算法算法二、二、2台机器的排序问题求解算法台机器的排序问题求解算法n/2/F/Fn/2/F/Fmaxmax问题的最优算法问题的最优算法JohnsonJohnson算法：算法：(1)列出所有工件在两台设备上的作业时间。列出所有工件在两台设备上的作业时间。(2)找出作业时间最小者。找出作业时间最小者。(3)如如果果该该最最小小值值是是在在设设备备1上上，将将对对应应的的工工件件排排在在前前面面，如如果果该该最最小小值值是是在在设设备备2上上，则则将将对对应应的的工工件排在后面。件排在后面。(4)排除已安排好的工件，在剩余的工件中重复步骤排除已安排好的工件，在剩余的工件中重复步骤(2)和和(3)，直到所有工件都安排完毕。，直到所有工件都安排完毕。例：某一班组有例：某一班组有A、B两台设备，要完成两台设备，要完成5个工件的加工任务。个工件的加工任务。每个工件在设备上的加工时间如下表所示。求总加工周期每个工件在设备上的加工时间如下表所示。求总加工周期最短的作业顺序。最短的作业顺序。工件在两台设备上的加工时间工件在两台设备上的加工时间工件编号工件编号 J1 J2 J3 J4 J5设备设备A 3 6 7 1 5设备设备B 2 8 6 4 3 求最优顺序求最优顺序算法步骤的改进算法步骤的改进把把JohnsonJohnson算算法法作作些些改改变变，改改变变后后的的算算法法按按以以下步骤进行：下步骤进行：将将所所有有a ai ibbi i的的零零件件按按a ai i值值不不减减的的顺顺序序排排成成一个序列一个序列A A。将将所所有有a ai ib bi i的的零零件件按按b bi i值值不不增增的的顺顺序序排排成成一个序列一个序列B B。将将A A放到放到B B之前，就构成了最优加工顺序之前，就构成了最优加工顺序 序列序列A A为为(2(2，5 5，6 6，1)1)，序列，序列B B为为(4(4，3)3)，构成最优顺序为，构成最优顺序为(2(2，5 5，6 6，1 1，4 4，3)3)，与，与JohnsonJohnson算法结果一致。算法结果一致。JohnsonJohnson法法则则只只是是一一个个充充分分条条件件，不不是是必必要要条条件件。不不符符合合这这个个法法则则的的加加工工顺顺序序，也也可可能能是是最最优优顺顺序序。如如对对例例11-211-2顺顺序序(2(2，5 5，6 6，4 4，1 1，3)3)不不符符合合JohnsonJohnson法法则则，但它也是一个最优顺序但它也是一个最优顺序对对于于3 3台台机机器器的的流流水水车车间间排排序序问问题题，只只有有几种特殊类型的问题找到了有效算法。几种特殊类型的问题找到了有效算法。对对于于一一般般的的流流水水车车间间排排列列排排序序问问题题，可可以用分支定界法。以用分支定界法。一一般般的的流流水水车车间间排排列列排排序序问问题题如如想想求求得得精精确确解解可可用用分分支支界界定定法法，但但计计算算量量比比较较大大，以以至至于于计计算算机机也也无无法法求求解解，因此常用一些启发式算法求近似解因此常用一些启发式算法求近似解（一）（一）Palmer法法按零件的按零件的斜度指标斜度指标排列零件的启发式算法排列零件的启发式算法零件的斜度指标零件的斜度指标三、一般三、一般n/m/P/Fmax问题的启发式算法问题的启发式算法 按按照照各各零零件件i不不增增的的顺顺序序排排列列零零件件，可可得得出出令令人人满满意意的的顺顺序序，如如果果排排列列的的结结果果有有多多个个，可可以以通通过过计计算算Fmax，取取其其中最优中最优Fmax对应的排序作为排序结果。对应的排序作为排序结果。例，有一个例，有一个4/3/F/F4/3/F/Fmaxmax问题，其加工时间如下表所问题，其加工时间如下表所 示，试用示，试用PalmerPalmer法求解法求解 Plamer法法解：计算解：计算i i 按照按照PalmerPalmer计算公式计算公式 步骤步骤1 计算计算 ,找出其中最大者，定义为关键工件找出其中最大者，定义为关键工件JC。步骤步骤2 除除JC外，将满足外，将满足pi1pim的工件，按的工件，按tim值的大小，从值的大小，从大到小排在大到小排在JC的后面。的后面。步骤步骤4 如有多个方案，可再加比较，从中选优。如有多个方案，可再加比较，从中选优。（二）关键工件法（二）关键工件法关键工件法举例关键工件法举例J1J2J3J4J5J6机器机器1pi15541210机器机器2pi25553610机器机器3pi3833474机器机器4pi4282156机器机器5pi5 5212810总和总和252315112840找出关键工件：工作负荷最大的找出关键工件：工作负荷最大的40，对应的是工件，对应的是工件6，所以，所以JC=J6确定排在关键工件前面的工件：满足步骤确定排在关键工件前面的工件：满足步骤2条件的有条件的有J4,J5,J1，所以有，所以有J4 J5 J1-J6 确定排在关键工件后面的工件：满足步骤确定排在关键工件后面的工件：满足步骤3条件的有条件的有J2,J3,所以有所以有 J6 J2 J3最后有：最后有：J4 J5 J1 J6 J2 J3 关键零件法求近优解举例关键零件法求近优解举例第三节第三节 单件作业计划问题单件作业计划问题一、任务分配问题一、任务分配问题二、单间作业排序问题二、单间作业排序问题三、优先派工法则三、优先派工法则一、任务分配问题一、任务分配问题把零件分配给工人或机器加工，将区域把零件分配给工人或机器加工，将区域分配给销售人员，将出故障的机器分配分配给销售人员，将出故障的机器分配给维修小组等，都是任务分配问题。给维修小组等，都是任务分配问题。求解任务分配问题的目标是使任务与资求解任务分配问题的目标是使任务与资源得到最佳匹配。源得到最佳匹配。匈牙利算法匈牙利算法1、将每行的元素减去行中的最小元素，如果某列中没、将每行的元素减去行中的最小元素，如果某列中没有出现有出现0元素，再将该列元素减去列中的最小元素。元素，再将该列元素减去列中的最小元素。2、测试是否已达到最佳分配组合。求出能够穿越所有、测试是否已达到最佳分配组合。求出能够穿越所有0的最小线数，如果此数等于矩阵的阶，直接进入第的最小线数，如果此数等于矩阵的阶，直接进入第4步。否则继续第步。否则继续第3步。步。3、将没有被直线覆盖的元素减去其中的最小元素，并、将没有被直线覆盖的元素减去其中的最小元素，并将各直线交点上的元素加上该最小元素。然后返回第将各直线交点上的元素加上该最小元素。然后返回第2步。步。4、进行分配：从、进行分配：从0元素最少的行或列开始，选择一个元素最少的行或列开始，选择一个0，然后划去同行和同列的其他，然后划去同行和同列的其他0。如此反复进行，直到。如此反复进行，直到所有所有0元素都被选择或划去为止。元素都被选择或划去为止。例：根据给定数据，求解各项作业与机器的最佳分配。例：根据给定数据，求解各项作业与机器的最佳分配。机器ABCD工作18624工作2671110工作33576工作4510129解：解：1、行作业与列作业：保证每行每列都有、行作业与列作业：保证每行每列都有0存在。存在。机器ABCD工作16300工作20052工作30141工作404722、用最少的直线划去所有、用最少的直线划去所有0元素。元素。机器ABCD工作16300工作20052工作30141工作404723、将剩余元素减去其中的最小元素、将剩余元素减去其中的最小元素1，并将各，并将各直线交点的元素加上直线交点的元素加上1。机器ABCD工作17400工作20041工作30130工作40461机器ABCD工作17400工作20041工作30130工作404614、用最少的直线划去所有、用最少的直线划去所有0元素。元素。5、分配、分配机器ABCD工作17400工作20041工作30130工作40461所选所选0元素的数目等于元素的数目等于4，故试分配成功。分配方案如下：，故试分配成功。分配方案如下：分配 成本1-C 22-B 73-D 64-A 5 20排序排序尽管载荷决策确定了用于特定作业加工的机器或加工尽管载荷决策确定了用于特定作业加工的机器或加工中心，但却没有说明作业在加工中心等候处理的加工中心，但却没有说明作业在加工中心等候处理的加工顺序。顺序。作业排序关心的就是确定作业处理顺序问题。排序决作业排序关心的就是确定作业处理顺序问题。排序决策不仅决定作业在各加工中心的加工顺序，还决定其策不仅决定作业在各加工中心的加工顺序，还决定其在加工中心内部各工作地的加工顺序。在加工中心内部各工作地的加工顺序。三、优先派工法则三、优先派工法则FCFS(先来先服务)：作业按照到达机器或加工中心的顺序进行加工处理SPT(最短加工时间)：作业顺序取决于它在机器或加工中心的加工时间，最短的先处理EDD(最早预定时间)：根据预定日期处理作业，最早的先处理LPT(最长加工时间)：优先选择加工时间最长的工件9.4生产作业控制生产作业控制 1）实实行生行生产产作作业业控制的原因和条件控制的原因和条件（1 1）原因）原因加工加工时间时间估估计计不准确不准确随机因素的影响随机因素的影响加工路加工路线线的多的多样样化化企企业环业环境境动态动态性性（2 2）条件）条件控制控制标标准：生准：生产计产计划和生划和生产产作作业计业计划划控制信息：控制信息：实际实际生生产进产进度和度和计计划的偏离信息划的偏离信息控制行控制行动动：通：通过过生生产调产调度度纠纠正偏差正偏差2）不同生）不同生产类产类型生型生产产控制的特点控制的特点 三、三、“漏斗漏斗”模型模型输入输入/输出控制输出控制任务任务库存库存(小时小时)输入输入小时小时到达的工件到达的工件库存水平库存水平完成的任务完成的任务输出输出小时小时输入曲线输入曲线输出曲线输出曲线参参考考时时间间段段内内的的输输入入参参考考时时间间段段内内的的输输出出期期末末库库存存期期初初库库存存参考时间段参考时间段时间时间工作量工作量