生产作业计划与控制课件

生产作业计划与控制2022/10/29生产作业计划与控制生产作业计划与控制2022/10/22生产作业计划与控制1第九章生产作业计划第一节流水线生产作、业计划的期量标准第二节流水线生产作业计划的编制第二节周期性生产类型作业计划的期量标准第四节周期性生产类型作业计划编制第五节流程式吁：产作业计划案例第六节关于作业计划的进一步讨论2022/10/29生产作业计划与控制2第九章生产作业计划第一节流水线生产作、业计划的期量标生产作业计划与控制单件作业排序问题4排序问题的基本概念1单台设备的排序问题2

35流水型作业排序问题生产作业控制2022/10/29生产作业计划与控制3生产作业计划与控制单件作业排序问题4排序问题的基本概念1单台第一节排序问题的基本概念1、排序的概念与作用作业排序：生产作业排序就是指对于等候某个设备或工作中心加工的多个任务，确定这些任务加工的先后次序。生产作业计划：不仅包括确定零件的加工顺序，而且还包括确定设备加工每一个零件的开始时间和完工时间。作用：提高设备或工作中心的效率减少在制品占用量缩短生产周期保证按期交货2022/10/29生产作业计划与控制4第一节排序问题的基本概念1、排序的概念与作用2022/排序问题分类按机器数量单台机器排序问题多台机器排序问题流水作业排序问题单件作业排序问题按零件到达车间的情况静态的排序问题动态的排序问题按目标函数的性质分类按参数确定型排序问题随机型排序问题2、排序问题的分类单目标排序多目标排序2022/10/29生产作业计划与控制5排序问题分类按机器数量单台机器排序问题流水作业排序问题按零件排序的目标函数（1）流程时间：任务在车间的停留时间Fi总流程时间：∑Fi最大流程时间：Fmax=max｛Fi｝平均流程时间：∑Fi/n（2）等待时间总等待时间平均等待时间（3）延期量：交货期拖延的时间（D）最大延期量:Dmax=max｛Di｝总延期量：∑Di（4）加工周期已知条件零件加工工艺过程作业时间ti交货期Ci时间

J1J2J3J4C1C2C3C4t1t2t3t4F1F2F3F42022/10/29生产作业计划与控制6排序的目标函数（1）流程时间：任务在车间的停留时间Fi已知条3、排序问题的表示法

n/m/A/B其中：n——零件数m——设备数A——车间类型流水作业排序——F单件作业排序——G当m=1时，A处为空白，因为对于单台设备的排序问题，无所谓加工路线问题，也谈不上流水型或单件作业．B——目标函数

例：5个工件经过4台设备加工，目标是使加工周期最短的流水型作业排序可以表示为：5/4/F/Fmax2022/10/29生产作业计划与控制73、排序问题的表示法例：5个工件经过4台设备加工，目标是使加1、单台设备排序问题的特点

无论n个零件加工任务作何种排序，n项任务中的最大流程时间(加工周期)总是一个固定值．第二节单台设备加工排序问题

零件号①②③④⑤作业时间48259加工周期=4+8+2+5+9=28目标函数？2022/10/29生产作业计划与控制81、单台设备排序问题的特点第二节单台设备加工排序问题

零件1)目标:使平均流程时间最短或平均等待时间最短2)方法：按任务所需时间长短，从短到长顺序排列。例：

零件号①②③④⑤⑥⑦作业时间1.750.250.701.302.251.00.75排序：②一③一⑦一⑥一④一①一⑤

2、SPT法（最短等待时间）2022/10/29生产作业计划与控制91)目标:使平均流程时间最短或平均等待时间最短零件号例题:已知条件如表所示,求平均流程时间,平均等待时间，最大交货延期．

零件号①②③④⑤⑥作业时间482593预定交货期2423863213解：列表如下

加工顺序123456零件号③⑥①④②⑤作业时间234589流程时间259142231等待时间02591422

预定交货期8132462332交货延期0008002022/10/29生产作业计划与控制10例题:已知条件如表所示,求平均流程时间,平均等待时间，最大交答：最大流程时间：31最大等待时间：22平均流程时间=(2+5+9+14+22+31)／6＝13.83平均等待时间=(0+2+5+9+1+14+22)/6=8.67最大交货延期：8总交货延期：(0+0+0+8+0+0)=8缺点：可能发生交货延期；优点：平均流程时间短加工顺序123456零件号③⑥①④②⑤作业时间234589流程时间259142231等待时间02591422

预定交货期8132462332交货延期0008002022/10/29生产作业计划与控制11答：最大流程时间：31最大等待时间：22加1)目标：最大交货延期时间最小。2)方法：按预定交货期(生产任务规定完成时刻)的先后，从先到后按次序排列，即按预定交货期非减的次序排序．3、EDD法（最早交期(EDD)排队策略）

零件号①②③④⑤⑥作业时间482593预定交货期2423863213排序：④一③一⑥一②一①一⑤

例题1:已知条件如表所示,用EDD法排序，并求平均流程时间,平均等待时间，最大交货延期．

2022/10/29生产作业计划与控制121)目标：最大交货延期时间最小。3、EDD法（最早交期(E答：最大流程时间：31最大等待时间：22平均流程时间=(5+7+10+18+22+31)／6＝15.5平均等待时间=(0+5+7+10+18+22)/6=10.33最大交货延期：0总交货延期：(0+0+0+0+0+0)=0缺点：平均流程时间较长优点：最大交货延期最小加工顺序123456零件号④③⑥②①⑤作业时间523849流程时间5710182231等待时间057101822

预定交货期6813232432交货延期0000002022/10/29生产作业计划与控制13答：最大流程时间：31最大等待时间：22加课堂练习：用SPT法和EDD法对下列问题排序，并求最大流程时间、平均流程时间、最大交货延期和总交货延期。

零件号①②③④⑤⑥作业时间81256410预定交货期3513421925102022/10/29生产作业计划与控制14课堂练习：

零件号①②③④⑤⑥作业时间812564第三节流水型作业排序问题流水型作业排序问题的特点:零件的加工路线相同两台设备的流水型排序问题三台设备的流水型排序问题m台设备的流水型排序问题车床1到达系统工件的集合离开系统（机器）J1J2J3Jn铣床2磨床m2022/10/29生产作业计划与控制15第三节流水型作业排序问题流水型作业排序问题的特点:零件1、两台设备流水型排序问题及解法2)目标：使完成任务的最大流程时间最短3)方法：约翰逊法设ti1和ti2分别是零件i在第一台设备和第二台设备上的加工时间。首先：以零件编号为行，以设备编号为列，建立加工时间矩阵。其次：从加工时间矩阵中找出最短的加工时间。第三：若最短的加工时间出现在第一台设备上，则对应的零件尽可能往前排，若最短的时间出现在第二台设备上，则对应的零件尽可能往后排．若最短的加工时间有多个，任选一个。最后：若所有工件都已排序，停止，否则，转步骤“第三”。设备零件①②③④⑤(1)车床ti1681237(2)铣床ti21195341）问题：n个零件在两台设备上加工，它们的工艺顺序相同2022/10/29生产作业计划与控制161、两台设备流水型排序问题及解法2)目标：使完成任务的最大流4)例1：已知如表，求加工周期．解：首先进行排序

方案一：④一①一②一③一⑤方案二；①一②一③一⑤一④有两个方案．设备零件①②③④⑤(1)车床ti1681237(2)铣床ti21195342022/10/29生产作业计划与控制174)例1：解：首先进行排序设备零件①②③④⑤(1)车其次计算加工周期:设备零件①②③④⑤(1)车床681237(2)铣床119534Fi1计算的根据：一个零件在设备(1)上加工必须等到它前面的零件在设备(1)上加工完成之后才能进行。加工顺序④①②③⑤(1)(2)ti1ti2Fi1Fi233681274591133629179640342920故:从表中可以看出，最大流程时间(零件的总加工周期）为40Fi2计算的根据：一个零件在设备(2)上加工必须等到该零件在设备(1)上加工完并且设备(2)加工完前一个零件之后才能开始2022/10/29生产作业计划与控制18其次计算加设备零件①②③④⑤(1)车床681237(2)铣床加工顺序①②④③⑤(1)(2)ti1ti2Fi1Fi26118312745896362917141743393426设备零件①②③④⑤(1)车床ti1681237(2)铣床ti2119584排序方案1（按照ti2

从大到小）：①一②一④一③一⑤例2：对下列问题排序，使完成任务的最大流程时间最短.排序方案2（按照约翰逊法）：④一①一②一③一⑤加工顺序④①②③⑤(1)(2)ti1ti2Fi1Fi23868127459113362917911403631222022/10/29生产作业计划与控制19加工顺序①②④③⑤(1)(2)ti1ti2Fi1Fi2611约翰逊法算法步骤的改进把Johnson算法作些改变，改变后的算法按以下步骤进行：（1）将所有ai≤bi的零件按ai值不减的顺序排成一个序列A。（2）将所有ai＞bi的零件按bi值不增的顺序排成一个序列B。（3）将A放到B之前，就构成了最优加工顺序设备零件①②③④⑤(1)车床681237(2)铣床119534（1）ai≤bi的零件为①②④，按ai值不减的顺序列得：序列A：④-①-②解：（2）ai＞bi的零件为③⑤，按bi值不增的顺序排列得：序列B：③-⑤（3）将A放到B之前得到：④-①-②-③-⑤2022/10/29生产作业计划与控制20约翰逊法算法步骤的改进把Johnson算法作些改变，改变后的约翰逊法约翰逊法，又名约翰逊规则，是作业排序中的一种排序方法。这种方法适用的条件是：n个工件经过二、三台设备（有限台设备）加工，所有工件在有限设备上加工的次序相同。2022/10/29生产作业计划与控制21约翰逊法约翰逊法，又名约翰逊规则，是作业排序中的一种排序方法4)使用条件：①minti1≥maxti2:即各零件在第一台设备上的最短加工时间大于或等于各零件在第二台设备上的最长加工时间。

或：②minti3≥maxti2：即各零件在第三台设备上的最短加工时间大于或等于各零件在第二台设备上的最长加工时间设备零件①②③④A车床158612B铣床3156C磨床410572、三台设备流水型排序问题及解法1）问题：n种零件在三台设备上加工，其工艺顺序均相同。2)目标：加工周期最短，即最大流程时间最小。3)方法：约翰逊扩展法2022/10/29生产作业计划与控制224)使用条件：①minti1≥maxti2:即各零件在第一第一步：检查各零件在设备(1)、(2)、(3)的加工时间是否满足使用条件的其中一个，若满足，进行第二步；第二步：将第一台设备和第二台设备加工时间按零件依次相加，令tG=ti1+ti2第三步：将第三台设备和第二台设备加工时间按零件依次相加，令tH=ti3+ti2第四步：将得到的tG和tH看作两台假想设备G和H的加工时间第五步；按两台设备的流水型排序问题及解法得出最优排序此排序就是三台设备的流水型排序的最优解。设备零件①②③④A车床158612B铣床3156C磨床410575）步骤2022/10/29生产作业计划与控制23设备零件①②③④A车床158612B铣床3156按约翰逊法：可得最优解为：②一④一③一①设备零件①②③④A车床158612B铣床3156C磨床41057设备零件①②③④G1891118H71110136)例题：已知如表，求加工周期。解：判定是否满足使用条件：minti1=6maxti2=6满足：

minti1≥maxti2可得右下表：2022/10/29生产作业计划与控制24按约翰逊法：设备零件①②③④A车床158612计算加工周期：设备零件①②③④A车床158612B铣床3156C磨床41057最优排序为：②一④一③一①

加工顺序②④③①(1)(2)（3）84126209443126ti1ti2Fi1Fi2ti3Fi3811261535610754193338482022/10/29生产作业计划与控制25计算加工周期：设备零件①②③④A车床158612课堂练习：

对下列流水型问题排序，使完成任务的最大流程时间最短，并求最短加工周期。(1)(2)设备零件①②③④⑤(1)车床ti1108642(2)铣床ti213579设备零件①②③④⑤⑥(1)车床ti1734897(2)铣床ti285510122022/10/29生产作业计划与控制26课堂练习：对下列流水型问题排序，使完成任3、m台设备的流水型排序问题及解法问题：n种零件在m台设备上加工，其工艺顺序相同．式中：

λi表示i零件的斜度指标m为设备数tik为i零件在k设备上的加工时间k=1,2……,m设备零件①②③④(1)1263(2)8429(3)4582（1）零件的斜率指标法(palmer)第一步：求各零件的斜度指标2022/10/29生产作业计划与控制273、m台设备的流水型排序问题及解法问题：n种零件在m台设备上

则:λ1=-t11+t13=-1+4=3

λ2=-t21+t23=-2+5=3λ3=-t31+t33=-6+8=2λ4=-t41+t43=-3+2=-1设备零件①②③④(1)1263(2)8429(3)4582k=1,2……,m解：对于本例λi第二步：按不增的顺序排列零件，即得满意解故排序：①一②一③一④或②一①一③一④=-ti1+ti32022/10/29生产作业计划与控制28

（2）关键零件法

第一步：计算各零件的总加工时间ti，找出加工时间最长的零件③,将其作为关键零件。第二步：除③之外，将满足ti1＜

tim的零件，按ti1的值从小到大把对应的零件排在③之前.第三步：除③之外，将满足ti1＞tim的零件，按tim的值从大到小把对应的零件排在③之后.第四步：满足ti1=

tim的零件，既可放在③的紧前，又可放在③的紧后.第五步：如果得到多个排序方案，选优即可设备零件①②③④(1)1263(2)8429(3)4582ti13111614tik为i零件在k设备上的加工时间,m为设备数.2022/10/29生产作业计划与控制29（2）关键零件法设备零件①②③④(1)1263(2)84例：已知如下表．求使加工周期最短的排序方案

设备零件①②③④(1)1263(2)8429(3)4582ti13111614解：计算此例中ti=ti1+

ti2+ti3总加工时间最长的为③零件，故关键零件选择③ti1＜

ti3的零件为①②，①②按ti1的值从小到大排在③之前，即为①一②一③ti1＞ti3的零件为④，④排在③之后，即为③一④

故排序为①一②一③一④

2022/10/29生产作业计划与控制30例：已知如下表．求使加工周期最短的排序方案设备零件①②③④（3）CDS法第一步:当L=1,2,·

·

·

·

·,m-1时,分别计算加工时间:设备零件①②③④(1)1263(2)8429(3)4582∑tikk=1L∑tikk=m+1-Lm和第二步:对于每个L,用上述两组数据构成一个两台设备的流水型排序问题,并用约翰逊法进行排序。第三步:对所得（m-1）个排序比较选优。i①②③④L=1ti11263ti34582L=2ti1+

ti296812ti2+

ti312910112022/10/29生产作业计划与控制31（3）CDS法第一步:当L=1,2,·····i1234L=1ti11263ti34582L=2ti1+

ti296812ti2+

ti31291011当L=1时，排序为①一②一③一④

Fmax=28加工顺序①②③④(1)(2)（3）112939241513ti1ti2Fi1Fi2ti3Fi3182639244582131826282022/10/29生产作业计划与控制32i1234L=1ti11263ti34582L=2ti1+加工顺序②③①④(1)(2)（3）212986271810ti1ti2Fi1Fi2ti3Fi324613982584211192329当L=2时，排序为②一③一①一④

Fmax=29故按CDS法排序结果为：①一②一③一④

Fmax=28

i1234L=1ti11263ti34582L=2ti1+

ti296812ti2+

ti312910112022/10/29生产作业计划与控制33加工顺序②③①④(1)(2)（3）212986271810

设备零件①②③④⑤（1）48259（2）23641（3）57384（4）621678课堂练习：

分别用零件的斜率指标法、关键零件法、CDS法对下列流水型问题排序，并求加工周期。2022/10/29生产作业计划与控制34

设备零件①②③④⑤（1）48259（4、实际应用例题例：东风汽车维修和上漆公司正在争取一份名为“风暴"的合同，这个合同的一个主要要求就是迅速交货，即如果能够将5辆需要维修和喷漆的车在24小时内整修并重新喷漆，这份合同就成交．下面是东风汽车维修和上漆公司对这5辆车进行整修和上漆分别所需的作业时间．问东风汽车维修和上漆公司能否取得这份名为"风暴”的合同．工艺要求在喷漆之前必须先进行整修．汽车整修时间(小时)喷漆时间(小时)A63B04C52D86E212022/10/29生产作业计划与控制354、实际应用例题汽车整修时间(小时)喷漆时间(小时)A63B铣床到达系统工件的集合离开系统（机器）J1J2Jk..Jn车床磨床车床离开系统（机器）磨床铣床JiJk单件作业排序问题的特征：零件的加工路线不同第四节单件作业排序问题1、问题的描述2、排序方法3、优选调度法则2022/10/29生产作业计划与控制36铣床到达系统工件的集合离开系统J1车床磨床车床离开系统磨床铣1、问题的描述(1)对于流水型作业排序问题，第K道工序永远在MK上加工，没有必要将工序号与机器号分开.(2)对于单件作业排序问题，要描述一道工序，必须将工件号、工序号和机器号结合在一起。试说明事件(3，4，1)和事件(2，3，3)的含义(3)上图中每个方框表示一个事件。事件的表达方式为：(i，j，k)，i表示工件号，j表示工序号，k表示完成i工件的第j道工序的机器代号。J1,1,铣床J1,2,车床J1,m，磨床J1Jk,1,车床离开系统（机器）Jk,2,磨床Jk,m,铣床Jk离开系统（机器）2022/10/29生产作业计划与控制371、问题的描述试说明事件(3，4，1)和事件(2，3，3)(5)用加工描述矩阵D来描述所有工件的加工每一行描述一个工件的加工，故每一行的工件号相同，每一列的工序号相同．

(6)加工时间矩阵242354T＝1,1,11,2,31,3,22,1,32,2,12,3,2D＝2022/10/29生产作业计划与控制38(5)用加工描述矩阵D来描述所有工件的加工每单件作业计划种类:

半能动作业计划（Semi-activeschedule）

各工序都按最早可能开（完）工时间安排的作业计划。能动作业计划（Activeschedule）

任何一台机器的每段空闲时间都不足以加工一道可加工工序的半能动作业计划。无延迟作业计划（Non-delayschedu1e）

没有任何延迟出现的能动作业计划。“延迟”：

有工件等待加工时，机器出现空闲，即使这段空闲时间不足于完成一道工序。2两种单件作业排序方法2022/10/29生产作业计划与控制39单件作业计划种类:2两种单件作业排序方法2022/10/2两种单件作业排序方法例：加工描述矩阵和加工时间矩阵如下，分别按下列两种方法进行作业排序．

(1)最小最早完工时间法（能动作业计划）(2)最小最早开工时间法（无延迟作业计划）1,1,11,2,31,3,22,1,32,2,12,3,2D＝242354T＝2022/10/29生产作业计划与控制402两种单件作业排序方法(1)最小最早完工时间法（能动作业(l)最小最早完工时间法

1,1,11,2,31,3,22,1,32,2,12,3,2D＝242354T＝序列可排事件最早可能开工时间最早可能完工时间最小最早可能完工时间所需机器排定事件1234561,3,2M2141412

1,3,22,3,2M29912781,3,22,3,22,2,1M1898731,3,22,2,11,2,3M3778331,2,32,2,12,1,3M3363201,2,32,1,31,1,1M1223001,1,12,1,3排定事件条件2022/10/29生产作业计划与控制41(l)最小最早完工时间法1,1,11,2,3最小最早完工时间法选择排定事件的条件：（1）属于可排事件（2）符合所需机器（3）最早可能开工时间小于最小最早可能完工时间返回2022/10/29生产作业计划与控制42最小最早完工时间法选择排定事件的条件：返回2022/10/2按此方法编制出的作业计划叫做：能动作业计划

1,1,11,2,31,3,22,1,32,2,12,3,2D＝

242354T＝排定事件1,1,12,1,31,2,32,2,12,3,21,3,2时间机器机器1机器2机器31,1,12,1,31,2,32,2,12,3,21,3,20032378121482022/10/29生产作业计划与控制43按此方法编制出的作业计划叫做：能动作业计划1,1,1(2)最小最早开工时间法

1,1,11,2,31,3,22,1,32,2,12,3,2D＝242354T＝序列可排事件最早可能开工时间最早可能完工时间最小最早可能开工时间所需机器排定事件1234562,3,2M29139

2,3,21,3,2M27912781,3,22,3,22,2,1M1398731,3,22,2,11,2,3M3M13378331,2,32,2,12,1,3M3063201,2,32,1,31,1,1M1M30023001,1,12,1,3排定事件条件2022/10/29生产作业计划与控制44(2)最小最早开工时间法1,1,11,2,3最小最早开工时间法选择排定事件的条件：（1）属于可排事件（2）符合所需机器（3）最早可能开工时间等于最小最早可能开工时间返回2022/10/29生产作业计划与控制45最小最早开工时间法选择排定事件的条件：返回2022/10/2时间机器机器1机器2机器3

1,1,11,2,31,3,22,1,32,2,12,3,2D＝

242354T＝排定事件1,1,12,1,31,2,32,2,11,3,22,3,2按此方法编制出的作业计划叫做：无延迟作业计划

1,1,12,1,31,2,32,2,12,3,21,3,2003237891372022/10/29生产作业计划与控制46时间机器机器1机器2机器31,1,11,2,33优选调度法则SPT：优先选择加工时间最短的事件．PCFS：优先选择最早进入可排事件集合的事件．EDD：优先选择完工期限紧的事件．MWKR：优先选择余下加工时间最长的事件．LWKR：优先选择余下加工时间最小的事件．MOPNR：优先选择余下工序数最多的事件．RANDOM：随机地挑选一个．2022/10/29生产作业计划与控制473优选调度法则2022/10/22生产作业计划与控制47演讲完毕，谢谢听讲!再见，seeyouagain3rew2022/10/29生产作业计划与控制演讲完毕，谢谢听讲!再见，seeyouagain3rew48生产作业计划与控制2022/10/29生产作业计划与控制生产作业计划与控制2022/10/22生产作业计划与控制49第九章生产作业计划第一节流水线生产作、业计划的期量标准第二节流水线生产作业计划的编制第二节周期性生产类型作业计划的期量标准第四节周期性生产类型作业计划编制第五节流程式吁：产作业计划案例第六节关于作业计划的进一步讨论2022/10/29生产作业计划与控制50第九章生产作业计划第一节流水线生产作、业计划的期量标生产作业计划与控制单件作业排序问题4排序问题的基本概念1单台设备的排序问题2

35流水型作业排序问题生产作业控制2022/10/29生产作业计划与控制51生产作业计划与控制单件作业排序问题4排序问题的基本概念1单台第一节排序问题的基本概念1、排序的概念与作用作业排序：生产作业排序就是指对于等候某个设备或工作中心加工的多个任务，确定这些任务加工的先后次序。生产作业计划：不仅包括确定零件的加工顺序，而且还包括确定设备加工每一个零件的开始时间和完工时间。作用：提高设备或工作中心的效率减少在制品占用量缩短生产周期保证按期交货2022/10/29生产作业计划与控制52第一节排序问题的基本概念1、排序的概念与作用2022/排序问题分类按机器数量单台机器排序问题多台机器排序问题流水作业排序问题单件作业排序问题按零件到达车间的情况静态的排序问题动态的排序问题按目标函数的性质分类按参数确定型排序问题随机型排序问题2、排序问题的分类单目标排序多目标排序2022/10/29生产作业计划与控制53排序问题分类按机器数量单台机器排序问题流水作业排序问题按零件排序的目标函数（1）流程时间：任务在车间的停留时间Fi总流程时间：∑Fi最大流程时间：Fmax=max｛Fi｝平均流程时间：∑Fi/n（2）等待时间总等待时间平均等待时间（3）延期量：交货期拖延的时间（D）最大延期量:Dmax=max｛Di｝总延期量：∑Di（4）加工周期已知条件零件加工工艺过程作业时间ti交货期Ci时间

J1J2J3J4C1C2C3C4t1t2t3t4F1F2F3F42022/10/29生产作业计划与控制54排序的目标函数（1）流程时间：任务在车间的停留时间Fi已知条3、排序问题的表示法

n/m/A/B其中：n——零件数m——设备数A——车间类型流水作业排序——F单件作业排序——G当m=1时，A处为空白，因为对于单台设备的排序问题，无所谓加工路线问题，也谈不上流水型或单件作业．B——目标函数

例：5个工件经过4台设备加工，目标是使加工周期最短的流水型作业排序可以表示为：5/4/F/Fmax2022/10/29生产作业计划与控制553、排序问题的表示法例：5个工件经过4台设备加工，目标是使加1、单台设备排序问题的特点

无论n个零件加工任务作何种排序，n项任务中的最大流程时间(加工周期)总是一个固定值．第二节单台设备加工排序问题

零件号①②③④⑤作业时间48259加工周期=4+8+2+5+9=28目标函数？2022/10/29生产作业计划与控制561、单台设备排序问题的特点第二节单台设备加工排序问题

零件1)目标:使平均流程时间最短或平均等待时间最短2)方法：按任务所需时间长短，从短到长顺序排列。例：

零件号①②③④⑤⑥⑦作业时间1.750.250.701.302.251.00.75排序：②一③一⑦一⑥一④一①一⑤

2、SPT法（最短等待时间）2022/10/29生产作业计划与控制571)目标:使平均流程时间最短或平均等待时间最短零件号例题:已知条件如表所示,求平均流程时间,平均等待时间，最大交货延期．

零件号①②③④⑤⑥作业时间482593预定交货期2423863213解：列表如下

加工顺序123456零件号③⑥①④②⑤作业时间234589流程时间259142231等待时间02591422

预定交货期8132462332交货延期0008002022/10/29生产作业计划与控制58例题:已知条件如表所示,求平均流程时间,平均等待时间，最大交答：最大流程时间：31最大等待时间：22平均流程时间=(2+5+9+14+22+31)／6＝13.83平均等待时间=(0+2+5+9+1+14+22)/6=8.67最大交货延期：8总交货延期：(0+0+0+8+0+0)=8缺点：可能发生交货延期；优点：平均流程时间短加工顺序123456零件号③⑥①④②⑤作业时间234589流程时间259142231等待时间02591422

预定交货期8132462332交货延期0008002022/10/29生产作业计划与控制59答：最大流程时间：31最大等待时间：22加1)目标：最大交货延期时间最小。2)方法：按预定交货期(生产任务规定完成时刻)的先后，从先到后按次序排列，即按预定交货期非减的次序排序．3、EDD法（最早交期(EDD)排队策略）

零件号①②③④⑤⑥作业时间482593预定交货期2423863213排序：④一③一⑥一②一①一⑤

例题1:已知条件如表所示,用EDD法排序，并求平均流程时间,平均等待时间，最大交货延期．

2022/10/29生产作业计划与控制601)目标：最大交货延期时间最小。3、EDD法（最早交期(E答：最大流程时间：31最大等待时间：22平均流程时间=(5+7+10+18+22+31)／6＝15.5平均等待时间=(0+5+7+10+18+22)/6=10.33最大交货延期：0总交货延期：(0+0+0+0+0+0)=0缺点：平均流程时间较长优点：最大交货延期最小加工顺序123456零件号④③⑥②①⑤作业时间523849流程时间5710182231等待时间057101822

预定交货期6813232432交货延期0000002022/10/29生产作业计划与控制61答：最大流程时间：31最大等待时间：22加课堂练习：用SPT法和EDD法对下列问题排序，并求最大流程时间、平均流程时间、最大交货延期和总交货延期。

零件号①②③④⑤⑥作业时间81256410预定交货期3513421925102022/10/29生产作业计划与控制62课堂练习：

零件号①②③④⑤⑥作业时间812564第三节流水型作业排序问题流水型作业排序问题的特点:零件的加工路线相同两台设备的流水型排序问题三台设备的流水型排序问题m台设备的流水型排序问题车床1到达系统工件的集合离开系统（机器）J1J2J3Jn铣床2磨床m2022/10/29生产作业计划与控制63第三节流水型作业排序问题流水型作业排序问题的特点:零件1、两台设备流水型排序问题及解法2)目标：使完成任务的最大流程时间最短3)方法：约翰逊法设ti1和ti2分别是零件i在第一台设备和第二台设备上的加工时间。首先：以零件编号为行，以设备编号为列，建立加工时间矩阵。其次：从加工时间矩阵中找出最短的加工时间。第三：若最短的加工时间出现在第一台设备上，则对应的零件尽可能往前排，若最短的时间出现在第二台设备上，则对应的零件尽可能往后排．若最短的加工时间有多个，任选一个。最后：若所有工件都已排序，停止，否则，转步骤“第三”。设备零件①②③④⑤(1)车床ti1681237(2)铣床ti21195341）问题：n个零件在两台设备上加工，它们的工艺顺序相同2022/10/29生产作业计划与控制641、两台设备流水型排序问题及解法2)目标：使完成任务的最大流4)例1：已知如表，求加工周期．解：首先进行排序

方案一：④一①一②一③一⑤方案二；①一②一③一⑤一④有两个方案．设备零件①②③④⑤(1)车床ti1681237(2)铣床ti21195342022/10/29生产作业计划与控制654)例1：解：首先进行排序设备零件①②③④⑤(1)车其次计算加工周期:设备零件①②③④⑤(1)车床681237(2)铣床119534Fi1计算的根据：一个零件在设备(1)上加工必须等到它前面的零件在设备(1)上加工完成之后才能进行。加工顺序④①②③⑤(1)(2)ti1ti2Fi1Fi233681274591133629179640342920故:从表中可以看出，最大流程时间(零件的总加工周期）为40Fi2计算的根据：一个零件在设备(2)上加工必须等到该零件在设备(1)上加工完并且设备(2)加工完前一个零件之后才能开始2022/10/29生产作业计划与控制66其次计算加设备零件①②③④⑤(1)车床681237(2)铣床加工顺序①②④③⑤(1)(2)ti1ti2Fi1Fi26118312745896362917141743393426设备零件①②③④⑤(1)车床ti1681237(2)铣床ti2119584排序方案1（按照ti2

从大到小）：①一②一④一③一⑤例2：对下列问题排序，使完成任务的最大流程时间最短.排序方案2（按照约翰逊法）：④一①一②一③一⑤加工顺序④①②③⑤(1)(2)ti1ti2Fi1Fi23868127459113362917911403631222022/10/29生产作业计划与控制67加工顺序①②④③⑤(1)(2)ti1ti2Fi1Fi2611约翰逊法算法步骤的改进把Johnson算法作些改变，改变后的算法按以下步骤进行：（1）将所有ai≤bi的零件按ai值不减的顺序排成一个序列A。（2）将所有ai＞bi的零件按bi值不增的顺序排成一个序列B。（3）将A放到B之前，就构成了最优加工顺序设备零件①②③④⑤(1)车床681237(2)铣床119534（1）ai≤bi的零件为①②④，按ai值不减的顺序列得：序列A：④-①-②解：（2）ai＞bi的零件为③⑤，按bi值不增的顺序排列得：序列B：③-⑤（3）将A放到B之前得到：④-①-②-③-⑤2022/10/29生产作业计划与控制68约翰逊法算法步骤的改进把Johnson算法作些改变，改变后的约翰逊法约翰逊法，又名约翰逊规则，是作业排序中的一种排序方法。这种方法适用的条件是：n个工件经过二、三台设备（有限台设备）加工，所有工件在有限设备上加工的次序相同。2022/10/29生产作业计划与控制69约翰逊法约翰逊法，又名约翰逊规则，是作业排序中的一种排序方法4)使用条件：①minti1≥maxti2:即各零件在第一台设备上的最短加工时间大于或等于各零件在第二台设备上的最长加工时间。

或：②minti3≥maxti2：即各零件在第三台设备上的最短加工时间大于或等于各零件在第二台设备上的最长加工时间设备零件①②③④A车床158612B铣床3156C磨床410572、三台设备流水型排序问题及解法1）问题：n种零件在三台设备上加工，其工艺顺序均相同。2)目标：加工周期最短，即最大流程时间最小。3)方法：约翰逊扩展法2022/10/29生产作业计划与控制704)使用条件：①minti1≥maxti2:即各零件在第一第一步：检查各零件在设备(1)、(2)、(3)的加工时间是否满足使用条件的其中一个，若满足，进行第二步；第二步：将第一台设备和第二台设备加工时间按零件依次相加，令tG=ti1+ti2第三步：将第三台设备和第二台设备加工时间按零件依次相加，令tH=ti3+ti2第四步：将得到的tG和tH看作两台假想设备G和H的加工时间第五步；按两台设备的流水型排序问题及解法得出最优排序此排序就是三台设备的流水型排序的最优解。设备零件①②③④A车床158612B铣床3156C磨床410575）步骤2022/10/29生产作业计划与控制71设备零件①②③④A车床158612B铣床3156按约翰逊法：可得最优解为：②一④一③一①设备零件①②③④A车床158612B铣床3156C磨床41057设备零件①②③④G1891118H71110136)例题：已知如表，求加工周期。解：判定是否满足使用条件：minti1=6maxti2=6满足：

minti1≥maxti2可得右下表：2022/10/29生产作业计划与控制72按约翰逊法：设备零件①②③④A车床158612计算加工周期：设备零件①②③④A车床158612B铣床3156C磨床41057最优排序为：②一④一③一①

加工顺序②④③①(1)(2)（3）84126209443126ti1ti2Fi1Fi2ti3Fi3811261535610754193338482022/10/29生产作业计划与控制73计算加工周期：设备零件①②③④A车床158612课堂练习：

对下列流水型问题排序，使完成任务的最大流程时间最短，并求最短加工周期。(1)(2)设备零件①②③④⑤(1)车床ti1108642(2)铣床ti213579设备零件①②③④⑤⑥(1)车床ti1734897(2)铣床ti285510122022/10/29生产作业计划与控制74课堂练习：对下列流水型问题排序，使完成任3、m台设备的流水型排序问题及解法问题：n种零件在m台设备上加工，其工艺顺序相同．式中：

λi表示i零件的斜度指标m为设备数tik为i零件在k设备上的加工时间k=1,2……,m设备零件①②③④(1)1263(2)8429(3)4582（1）零件的斜率指标法(palmer)第一步：求各零件的斜度指标2022/10/29生产作业计划与控制753、m台设备的流水型排序问题及解法问题：n种零件在m台设备上

则:λ1=-t11+t13=-1+4=3

λ2=-t21+t23=-2+5=3λ3=-t31+t33=-6+8=2λ4=-t41+t43=-3+2=-1设备零件①②③④(1)1263(2)8429(3)4582k=1,2……,m解：对于本例λi第二步：按不增的顺序排列零件，即得满意解故排序：①一②一③一④或②一①一③一④=-ti1+ti32022/10/29生产作业计划与控制76

（2）关键零件法

第一步：计算各零件的总加工时间ti，找出加工时间最长的零件③,将其作为关键零件。第二步：除③之外，将满足ti1＜

tim的零件，按ti1的值从小到大把对应的零件排在③之前.第三步：除③之外，将满足ti1＞tim的零件，按tim的值从大到小把对应的零件排在③之后.第四步：满足ti1=

tim的零件，既可放在③的紧前，又可放在③的紧后.第五步：如果得到多个排序方案，选优即可设备零件①②③④(1)1263(2)8429(3)4582ti13111614tik为i零件在k设备上的加工时间,m为设备数.2022/10/29生产作业计划与控制77（2）关键零件法设备零件①②③④(1)1263(2)84例：已知如下表．求使加工周期最短的排序方案

设备零件①②③④(1)1263(2)8429(3)4582ti13111614解：计算此例中ti=ti1+

ti2+ti3总加工时间最长的为③零件，故关键零件选择③ti1＜

ti3的零件为①②，①②按ti1的值从小到大排在③之前，即为①一②一③ti1＞ti3的零件为④，④排在③之后，即为③一④

故排序为①一②一③一④

2022/10/29生产作业计划与控制78例：已知如下表．求使加工周期最短的排序方案设备零件①②③④（3）CDS法第一步:当L=1,2,·

·

·

·

·,m-1时,分别计算加工时间:设备零件①②③④(1)1263(2)8429(3)4582∑tikk=1L∑tikk=m+1-Lm和第二步:对于每个L,用上述两组数据构成一个两台设备的流水型排序问题,并用约翰逊法进行排序。第三步:对所得（m-1）个排序比较选优。i①②③④L=1ti11263ti34582L=2ti1+

ti296812ti2+

ti312910112022/10/29生产作业计划与控制79（3）CDS法第一步:当L=1,2,·····i1234L=1ti11263ti34582L=2ti1+

ti296812ti2+

ti31291011当L=1时，排序为①一②一③一④

Fmax=28加工顺序①②③④(1)(2)（3）112939241513ti1ti2Fi1Fi2ti3Fi3182639244582131826282022/10/29生产作业计划与控制80i1234L=1ti11263ti34582L=2ti1+加工顺序②③①④(1)(2)（3）212986271810ti1ti2Fi1Fi2ti3Fi324613982584211192329当L=2时，排序为②一③一①一④

Fmax=29故按CDS法排序结果为：①一②一③一④

Fmax=28

i1234L=1ti11263ti34582L=2ti1+

ti296812ti2+

ti312910112022/10/29生产作业计划与控制81加工顺序②③①④(1)(2)（3）212986271810

设备零件①②③④⑤（1）48259（2）23641（3）57384（4）621678课堂练习：

分别用零件的斜率指标法、关键零件法、CDS法对下列流水型问题排序，并求加工周期。2022/10/29生产作业计划与控制82

设备零件①②③④⑤（1）48259（4、实际应用例题例：东风汽车维修和上漆公司正在争取一份名为“风暴"的合同，这个合同的一个主要要求就是迅速交货，即如果能够将5辆需要维修和喷漆的车在24小时内整修并重新喷漆，这份合同就成交．下面是东风汽车维修和上漆公司对这5辆车进行整修和上漆分别所需的作业时间．问东风汽车维修和上漆公司能否取得这份名为"风暴”的合同．工艺要求在喷漆之前必须先进行整修．汽车整修时间(小时)喷漆时间(小时)A63B04C52D86E212022/10/29生产作业计划与控制834、实际应用例题汽车整修时间(小时)喷漆时间(小时)A63B铣床到达系统工件的集合离开系统（机器）J1J2Jk..Jn车床磨床车床离开系统（机器）磨床铣床JiJk单件作业排序问题的特征：零件的加工路线不同第四节单件作业排序问题1、问题的描述2、排序方法3、优选调度法则2022/10/29生产作业计划与控制84铣床到达系统工件的集合离开系统J1车床磨床车床离开系统磨床铣1、问题的描述(1)对于流水型作业排序问题，第K道工序永远在MK上加工，没有必要将工序号与机器号分开.(2)对于单件作业排序问题，要描述一道工序，必须将工件号、工序号和机器号结合在一起。试说明事件(3，4，1)和事件(2，3，3)的含义(3)上图中每个方框表示一个事件。事件的表达方式为：(i，j，k)，i表示工件号，j表示工序号，k表示完成i工件的第j道工序的机器代号。J1,1,铣床J1,2,车床J1,m，磨床J1Jk,1,车床离开系统（机器）Jk,2,磨床Jk,m,铣床Jk离开系统（机器）2022/10/29生产作业计划与控制851、问题的描述试说明事件(3，4，1)和事件