生产作业计划与排序

第六章生产作业计划与排序一、基本概念二、最长流程时间三、n/2/F/Fmax问题的算法四、n/m/P/Fmax问题的启发式算法五、单件车间排序问题一、基本概念1、排序排序就是要将不同的工作任务安排一个执行的顺序，使预定的目标最优化。实际上就是要解决如何按时间的先后，将有限的人力、物力资源分配给不同工作任务，使预定目标最优化的问题。排序的作用实例1：油漆生产顺序某企业生产白、灰、红、蓝四种油漆，每次生产前都有清洗容器的调整准备时间。按怎样的顺序，总的调整准备时间最少？实例2：复印排序问题有四人同时到达复印室，每人的复印量不同，如何安排顺序，使得他们的平均等待时间和平均流程时间最小？方案1：白-灰-红-蓝T-setup=12

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

按最短工时优先原则（SPT）,结果最优。一、基本概念排序中常用的几个概念工件（Job）：服务对象；机器（Machine、Processor）：服务者。如：n个零件在机器上加工，则零件是工件，设备是机器；工人维修设备，出故障的设备是工件，工人是机器。一、基本概念

作业排序也就是要确定工件在机器上的加工顺序，可用一组工件代号的一种排列来表示。如，用（1，6，5，4，3，2）表示加工顺序：J1—J6—J5—J4—J3—J2。一、基本概念2、作业计划（Scheduling）作业计划与排序不是一回事，它不仅要确定工件的加工顺序，而且还要确定每台机器加工每个工件的开工时间和完工时间。如果按最早可能开（完）工时间来编排作业计划，则排序完后，作业计划也就确定了。一、基本概念3、排序问题的分类与表示1）单台机器与多台机器的排序问题。2）流水车间与单件车间排序问题。排序问题的分类单机排序和多机排序：按设备的种类和数量：单目标排序和多目标排序：按目标函数的性质流水型与非流水型排序：按工件加工路线的特征（加工路线是否相同）

同顺序排列（P）

一般流水型(F):流水车间(Flow-shop)

非流水型(G):单件车间(Job-shop)一、、基基本本概概念念流水水车车间间排排序序问问题题的的基基本本特特征征：：每个个工工件件的的加加工工路路线线都都一一样样。。如如车车——铣铣——磨磨。。这这里里指指的的是是工工件件的的加加工工流流向向一一致致，，并并不不要要求求每每个个工工件件必必须须在在每每台台机机器器上上加加工工。。如如有有的的工工件件为为车车——磨磨，，有有的的为为铣铣——磨磨。。不仅仅加加工工路路线线一一致致，，而而且且所所有有工工件件在在各各台台机机器器上上的的加加工工顺顺序序也也一一样样，，这这种种排排序序称称为为排排列列排排序序（（同同顺顺序序排排序序））。。如如工工件件排排序序为为：：J1——J3——J2，，则则表表示示所所有有机机器器都都是是先先加加工工J1，，然然后后加加工工J3，，最最后后加加工工J2。。一、、基基本本概概念念单件件车车间间排排序序问问题题的的基基本本特特征征：：每个个工工件件都都有有其其独独特特的的加加工工路路线线，，工工件件没没有有一一定定的的流流向向。。一、、基基本本概概念念3））表表示示方方法法一般般正正规规的的表表示示方方法法为为：：n/m/A/Bn：：工工件件数数；；m：：机机器器数数；；A：：车车间间类类型型（（F、、P、、G））；；同顺顺序序排排列列（（P））一般般流流水水型型(F):流流水水车车间间(Flow-shop)非流流水水型型(G):单单件件车车间间(Job-shop)B：：目目标标函函数数加工工周周期期交货货期期总费费用用一、、基基本本概概念念4））一一般般来来说说，，排排列列排排序序问问题题的的最最优优解解不不一一定定是是相相应应流流水水车车间间排排序序问问题题的的最最优优解解，，但但一一般般是是比比较较好好的的解解。。而而对对于于仅仅有有2台台或或3台台机机器器的的情情况况，，则则排排列列排排序序问问题题的的最最优优解解一一定定是是相相应应流流水水车车间间排排序序问问题题的的最最优优解解。。符号号说说明明Ji------工工件件iMj------机机器器jpij------工工件件i在在机机器器j上上的的加加工工时时间间,Pi------工工件件i总总的的加加工工时时间间Pi=pijri------工工件件i的的到到达达时时间间di------工工件件i的的完完工工期期限限wij-----工工件件i在在第第j道道工工序序的的等等待待时时间间Wi------工工件件i总总的的等等待待时时间间Wi=wijCi------工工件件i的的完完工工时时间间Ci=ri+Wi+PiFi------工工件件i的的流流程程时时间间Fi=Ci－ri=Wi+PiLi------工件i的延延迟时间Li=Ci－di一、基本概念念4、排序问题题的假设条件件一个工件不能能同时在几台台不同的机器器上加工。工件在加工过过程中采取平平行移动方式式。不允许中断。。每道工序只在在一台机器上上完成。每台机器同时时只能加工一一个工件。工件数、机器器数和加工时时间已知，加加工时间与加加工顺序无关关。二、最长流程程时间最长流程时间间（加工周期期）：从第一一个工件在第第一台机器上上加工起到最最后一个工件件在最后一台台机器上加工工完毕为止所所经过的时间间。假定所有工件件的到达时间间都为0，则则Fmax等等于排在末位位加工的工件件在车间的停停留时间。二、最长流程程时间计算Fmax的几个假定定条件：机器M1不会会发生空闲；；对其它机器，，能对某一工工件加工必须须具备2个条条件：机器必必须完成排前前一位的工件件的加工；要要加工的工件件的上道工序序已经完工。二、最长流程程时间二、最长流程程时间ipi1pi2pi3pi4615243255144544453258217533674261012131671115202733121722303542132125323846三、n/2/F/Fmax问问题的的算法法Johnson算法法：假定：：ai为工件件Ji在机器器M1上的的加工工时间间，bi为工件件Ji在机器器M2上的的加工工时间间，每每个工工件按按M1—M2的的路线线加工工。三、n/2/F/Fmax问问题的的算法法Johnson算法法的步步骤：：从加工工时间间矩阵阵中找找出最最短的的加工工时间间。若最短短时间间出现现在M1上，则则对应应的工工件尽尽可能能往前前排。。若最短短时间间出现现在M2上，则则对应应的工工件尽尽可能能往后后排。。若最短短时间间有多多个，，则任任选一一个。。划去已已排序序的工工件。。若所有有工件件都已已排序序，则则停止止，否否则重重复上上述步步骤。。n/2/F/Fmax流水型型排序序（1））按约约翰逊逊-贝贝尔曼曼规则则排序序，得得到2--6--3--5--4--1（2））列表表计算算流程程时间间四、一一般n/m/P/Fmax问题题的启启发式式算法法对于一一般的的n/m/P/Fmax问题题，可可以用用分支支定界界法求求得最最优解解，但但计算算量很很大。。实际际中，，可以以用启启发式式算法法求近近优解解。四、一一般n/m/P/Fmax问题题的启启发式式算法法1、Palmer法法计算工工件斜斜度指指标i：：m:机机器数数pik：工件件i在在机器器k上上的加加工时时间。。M=3i=-pi1+pi3M=4i=-1.5pi1-0.5pi2+0.5pi3+1.5pi4排序方方法:按按i从大到到小的的顺序序排列列。按排序序的顺顺序计计算Fmax四、一一般n/m/P/Fmax问题题的启启发式式算法法2、关关键工工件法法：计算Pi=Pij，找出出Pi最长的的工件件，将将之作作为关关键工工件C。对其余余工件件，若若Pi1≤Pim，则按按Pi1由小到到大排排成序序列SA。若Pi1>Pim，则按按Pim由大到到小排排成序序列SB。顺序（（SA，C，，SB）即为为近优优解。。四、一一般n/m/P/Fmax问题题的启启发式式算法法得到的的加工工顺序序为(1，2，3，4)四、一一般n/m/P/Fmax问题题的启启发式式算法法3、CDS法：CDS法是是Johnson算算法的的扩展展方法法，从从M-1个个排序序中找找出近近优解解。四、一一般n/m/P/Fmax问题题的启启发式式算法法L＝1，按按Johnson算算法得得到加加工顺顺序(1，，2，，3，，4)，Fmax＝28L＝2，，按Johnson算算法得到到加工顺顺序(2，3，，1，4)，Fmax＝29取顺序(1，2，3，，4为最最优顺序序。问题描述述流水(i,j)(工件件，工序序)单件(i,j,k)(工工件，工工序，机机器)加工描述述矩阵和和加工时时间矩阵阵五、单件件车间排排序问题题（n/m/G/Fmax）五、单件件车间排排序问题题（n/m/G/Fmax）1、问题描述述(i，j，k)：表示示工件i的第j道工序序是在机机器k上上进行。。加工描述述矩阵D：每一一行描述述一个工工件的加加工，每每一列的的工序序序号相同同。D=1,1,11,2,31,3,22,1,32,2,12,3,2五、单件件车间排排序问题题（n/m/G/Fmax）加工时间间矩阵T：与D相对应应。D=1,1,11,2,31,3,22,1,32,2,12,3,2T=463574五、单件件车间排排序问题题（n/m/G/Fmax）加工顺序序矩阵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,3五、单件件车间排排序问题题（n/m/G/Fmax）用方块图图表示：：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,2M1M2M3五、单件件车间排排序问题题（n/m/G/Fmax）2、能动作业业计划的的构成各工序都都按最早早可能开开(完)工时间间安排且且任何一一台机器器的每段段空闲时时间都不不足以加加工一道道可加工工工序。。符号说明明：{Ot}第t步可以以排序的的工序的的集合{St}t步步之前已已排序的的工序构构成的部部分作业业计划Tk{Ot}中工序序Ok的最早可可能开工工时间T’k{Ot}中工序序Ok的最早可可能完工工时间五、单件件车间排排序问题题（n/m/G/Fmax）能动作业业计划的的构成步步骤：①设t＝1，{St}为空，，{Ot}为各工工件第一一道工序序的集合合。②求最小的的最早完完工时间间T*=min{T’k},并找到出现现T*的机器M*，若有多多台，任任选一台台。③从{Ot}中跳出出满足以以下两条条件的工工序Oj需要机器器M*加工；Tj<T*④将确定定的Oj放入{St}，从{Ot}中消去去Oj并并将Oj的紧后后工序放放入{Ot}中中，使t=t+1。⑤若还有有未安排排的工序序，转步步骤②；；否则，，停止。。一个实例例：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,2813得到加工工顺序矩矩阵：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,2M1M2M323773813五、单件车间间排序问题（（n/m/G/Fmax）3、无延迟作业计计划的构成没有任何延迟迟出现的能动动作业计划。。所谓“延迟迟”，指有工工件等待加工工时，机器出出现空闲，即即使这段空闲闲时间不足以以完成一道工工序。构成步骤：五、单件车间间排序问题（（n/m/G/Fmax）无延迟作业计计划的构成步步骤：①设t＝1，{St}为空，{Ot}为各工件第第一道工序的的集合。②求最小的最早早完工时间T*=min{Tk},并找到出现T*的机器M*，若有多台，，任选一台。。③从{Ot}中跳出满足足以下两条件件的工序Oj需要机器M*加工；Tj=T*④将确定的Oj放入{St}，从{Ot}中消消去Oj并将将Oj的紧后后工序放入{Ot}中，，使t=t+1。⑤若还有未安安排的工序，，转步骤②；；否则，停止止。一个实例：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,212130M33M17M2得到加工顺顺