生产作业计划与排序课件

07 七月 2024生产作业计划与排序生产作业计划与排序一、基本概念1、排序、排序排序就是要将不同的工作任务安排一个执行排序就是要将不同的工作任务安排一个执行的顺序，使预定的目标最优化。的顺序，使预定的目标最优化。实际上就是要解决如何按时间的先后，将有实际上就是要解决如何按时间的先后，将有限的人力、物力资源分配给不同工作任务，限的人力、物力资源分配给不同工作任务，使预定目标最优化的问题。使预定目标最优化的问题。排序的作用排序的作用实例实例1：油漆生产顺序：油漆生产顺序 某企业生产白、灰、红、蓝四种油漆，某企业生产白、灰、红、蓝四种油漆，每次生产前都有清洗容器的调整准备时每次生产前都有清洗容器的调整准备时间。按怎样的顺序，总的调整准备时间间。按怎样的顺序，总的调整准备时间最少？最少？实例实例2：复印排序问题：复印排序问题 有四人同时到达复印室，每人的复印量有四人同时到达复印室，每人的复印量不同，如何安排顺序，使得他们的平均不同，如何安排顺序，使得他们的平均等待时间和平均流程时间最小？等待时间和平均流程时间最小？方案方案1：白：白-灰灰-红红-蓝蓝 T-setup=12方案方案2：蓝：蓝-红红-灰灰-白白 T-setup=20按最短工时优先原则（SPT）,结果最优。一、基本概念排序中常用的几个概念排序中常用的几个概念工件（工件（Job）：服务对象；）：服务对象；机器（机器（Machine、Processor）：服务者。）：服务者。如：如：n个个零零件件在在机机器器上上加加工工，则则零零件件是是工工件件，设设备备是机器；是机器；工工人人维维修修设设备备，出出故故障障的的设设备备是是工工件件，工工人人是机器。是机器。一、基本概念 作业排序也就是要确定工件在机器上的加工作业排序也就是要确定工件在机器上的加工顺序，可用一组工件代号的一种排列来表示。顺序，可用一组工件代号的一种排列来表示。如，用（如，用（1，6，5，4，3，2）表示加工顺序：）表示加工顺序：J1J6J5J4J3J2。一、基本概念2、作业计划（、作业计划（Scheduling）作作业业计计划划与与排排序序不不是是一一回回事事，它它不不仅仅要要确确定定工工件件的的加加工工顺顺序序，而而且且还还要要确确定定每每台台机机器器加加工每个工件的开工时间和完工时间。工每个工件的开工时间和完工时间。如如果果按按最最早早可可能能开开（完完）工工时时间间来来编编排排作作业业计划，则排序完后，作业计划也就确定了。计划，则排序完后，作业计划也就确定了。一、基本概念3、排序问题的分类与表示、排序问题的分类与表示1）单台机器与多台机器的排序问题。2）流水车间与单件车间排序问题。排序问题的分类排序问题的分类单机排序和多机排序：按设备的种类和单机排序和多机排序：按设备的种类和数量：数量：单目标排序和多目标排序：按目标函数单目标排序和多目标排序：按目标函数的性质的性质流水型与非流水型排序：按工件加工路流水型与非流水型排序：按工件加工路线的特征（加工路线是否相同）线的特征（加工路线是否相同）同顺序排列（同顺序排列（P P）一般流水型一般流水型(F):(F):流水车间流水车间(Flow-shop)(Flow-shop)非流水型非流水型(G):(G):单件车间单件车间(Job-shop)(Job-shop)一、基本概念流水车间排序问题的基本特征：流水车间排序问题的基本特征：每个工件的加工路线都一样。如车铣磨。这里指的是工件的加工流向一致，并不要求每个工件必须在每台机器上加工。如有的工件为车磨，有的为铣磨。不仅加工路线一致，而且所有工件在各台机器上的加工顺序也一样，这种排序称为排列排序（同顺序排序）。如工件排序为：J1J3J2，则表示所有机器都是先加工J1，然后加工J3，最后加工J2。一、基本概念单件车间排序问题的基本特征：单件车间排序问题的基本特征：每个工件都有其独特的加工路线，工件没有一定的流向。一、基本概念一、基本概念3）表示方法）表示方法 一般正规的表示方法为：一般正规的表示方法为：n/m/A/B n：工件数；：工件数；m：机器数；：机器数；A：车间类型（：车间类型（F、P、G）；）；同顺序排列（同顺序排列（P P）一般流水型一般流水型(F):(F):流水车间流水车间(Flow-shop)(Flow-shop)非流水型非流水型(G):(G):单件车间单件车间(Job-shop)(Job-shop)B：目标函数：目标函数 加工周期加工周期 交货期交货期 总费用总费用一、基本概念4）一一般般来来说说，排排列列排排序序问问题题的的最最优优解解不不一一定定是是相相应应流流水水车车间间排排序序问问题题的的最最优优解解，但但一一般般是是比比较较好好的的解解。而而对对于于仅仅有有2台台或或3台台机机器器的的情情况况，则则排排列列排排序序问问题题的的最最优优解解一一定定是是相相应应流水车间排序问题的最优解。流水车间排序问题的最优解。符号说明符号说明J Ji i-工件工件i i M Mj j-机器机器j j p pijij-工件工件i i在机器在机器j j上的加工时间上的加工时间,P Pi i-工件工件i i总的加工时间总的加工时间 P Pi i=p pijij r ri i-工件工件i i的到达时间的到达时间 d di i-工件工件i i的完工期限的完工期限 w wijij-工件工件i i在第在第j j道工序的等待时间道工序的等待时间W Wi i-工件工件i i总的等待时间总的等待时间 W Wi i=w wijijC Ci i-工件工件i i的完工时间的完工时间 C Ci i=r=ri i+W+Wi i+P+Pi iF Fi i-工件工件i i的流程时间的流程时间 F Fi i=C=Ci ir ri i=W=Wi i+P+Pi iL Li i-工件工件i i的延迟时间的延迟时间 L Li i=C=Ci id di i 一、基本概念4、排序问题的假设条件、排序问题的假设条件一个工件不能同时在几台不同的机器上加工。一个工件不能同时在几台不同的机器上加工。工件在加工过程中采取平行移动方式。工件在加工过程中采取平行移动方式。不允许中断。不允许中断。每道工序只在一台机器上完成。每道工序只在一台机器上完成。每台机器同时只能加工一个工件。每台机器同时只能加工一个工件。工件数、机器数和加工时间已知，加工时间与加工工件数、机器数和加工时间已知，加工时间与加工顺序无关。顺序无关。二、最长流程时间二、最长流程时间最长流程时间（加工周期）：从第一个工件最长流程时间（加工周期）：从第一个工件在第一台机器上加工起到最后一个工件在最在第一台机器上加工起到最后一个工件在最后一台机器上加工完毕为止所经过的时间。后一台机器上加工完毕为止所经过的时间。假定所有工件的到达时间都为假定所有工件的到达时间都为0，则，则Fmax等等于排在末位加工的工件在车间的停留时间。于排在末位加工的工件在车间的停留时间。二、最长流程时间计算计算Fmax的几个假定条件：的几个假定条件：机器机器M1不会发生空闲；不会发生空闲；对对其其它它机机器器，能能对对某某一一工工件件加加工工必必须须具具备备2个个条条件件：机机器器必必须须完完成成排排前前一一位位的的工工件件的的加加工工；要加工的工件的上道工序已经完工要加工的工件的上道工序已经完工。二、最长流程时间二、最长流程时间三、n/2/F/Fmax问题的算法Johnson算法：算法：假定：假定：ai为工件为工件Ji在机器在机器M1上的加工时间，上的加工时间，bi为工件为工件Ji在机器在机器M2上的加工时间，每上的加工时间，每个工件按个工件按M1M2的路线加工。的路线加工。三、n/2/F/Fmax问题的算法Johnson算法的步骤：算法的步骤：从加工时间矩阵中找出最短的加工时间。从加工时间矩阵中找出最短的加工时间。若最短时间出现在若最短时间出现在M1上，则对应的工件尽可能上，则对应的工件尽可能往前排。往前排。若最短时间出现在若最短时间出现在M2上，则对应的工件尽可能上，则对应的工件尽可能往后排。往后排。若最短时间有多个，则任选一个。若最短时间有多个，则任选一个。划去已排序的工件。划去已排序的工件。若所有工件都已排序，则停止，否则重复上述若所有工件都已排序，则停止，否则重复上述步骤。步骤。n/2/F/Fmax流水型排序 （1 1）按按约约翰翰逊逊-贝贝尔尔曼曼规规则则排排序序，得得到到2-2-6-3-5-4-16-3-5-4-1（2 2）列表计算流程时间）列表计算流程时间四、一般n/m/P/Fmax问题的启发式算法 对对于于一一般般的的n/m/P/Fmax问问题题，可可以以用用分分支支定定界界法法求求得得最最优优解解，但但计计算算量量很很大大。实实际际中，可以用启发式算法求近优解。中，可以用启发式算法求近优解。四、一般n/m/P/Fmax问题的启发式算法1 1、PalmerPalmer法法计算工件斜度指标计算工件斜度指标 i i：m:m:机器数机器数 p pikik ：工件：工件i i在机器在机器k k上的加工时间。上的加工时间。M=3 M=3 i i=-p=-pi1 i1+p+pi3i3 M=4 M=4 i i=-1.5p=-1.5pi1i1-0.5p-0.5pi2 i2+0.5p+0.5pi3i3+1.5p+1.5pi4i4排序方法排序方法:按按 i i从大到小的顺序排列。从大到小的顺序排列。按排序的顺序计算按排序的顺序计算FmaxFmax四、一般n/m/P/Fmax问题的启发式算法2 2、关键工件法、关键工件法：计计算算Pi=Pij，找找出出Pi最最长长的的工工件件，将将之之作作为为关键工件关键工件C。对对其其余余工工件件，若若Pi1Pim，则则按按Pi1由由小小到到大大排排成成序序列列SA。若若Pi1 Pim，则则按按Pim由由大大到到小小排排成成序列序列SB。顺序（顺序（SA，C，SB）即为近优解。）即为近优解。四、一般n/m/P/Fmax问题的启发式算法四、一般n/m/P/Fmax问题的启发式算法3 3、CDS法法：CDS法是Johnson算法的扩展方法，从M-1个排序中找出近优解。四、一般n/m/P/Fmax问题的启发式算法L1，按Johnson算法得到加工顺序(1，2，3，4)，Fmax28L2，按Johnson算法得到加工顺序(2，3，1，4)，Fmax29取顺序(1，2，3，4为最优顺序。问题描述问题描述 流水流水(i,j)(i,j)(工件，工序工件，工序)单件单件(i,j,k)(i,j,k)(工件，工序，机器工件，工序，机器)加工描述矩阵和加工时间矩阵加工描述矩阵和加工时间矩阵 五、单件车间排序问题（n/m/G/Fmax）五、单件车间排序问题（n/m/G/Fmax）1 1、问题描述问题描述(i，j，k)：表示工件i的第j道工序是在机器k上进行。加工描述矩阵D：每一行描述一个工件的加工，每一列的工序序号相同。五、单件车间排序问题（n/m/G/Fmax）加工时间矩阵T：与D相对应。五、单件车间排序问题（n/m/G/Fmax）加工顺序矩阵S：每一行与机器相对应，每一列与工件相对应。五、单件车间排序问题（n/m/G/Fmax）用方块图表示：五、单件车间排序问题（n/m/G/Fmax）2 2、能动作业计划的构成能动作业计划的构成各工序都按最早可能开各工序都按最早可能开(完完)工时间安排且任何工时间安排且任何一台机器的每段空闲时间都不足以加工一道可一台机器的每段空闲时间都不足以加工一道可加工工序。加工工序。符号说明：符号说明：Ot 第第t步可以排序的工序的集合步可以排序的工序的集合St t步之前已排序的工序构成的部分作业计步之前已排序的工序构成的部分作业计划划Tk Ot中工序中工序Ok的最早可能开工时间的最早可能开工时间Tk Ot中工序中工序Ok的最早可能完工时间的最早可能完工时间五、单件车间排序问题（n/m/G/Fmax）能动作业计划的构成步骤：能动作业计划的构成步骤：设设t1，SSt t 为空，为空，OOt t 为各工件第一道工序的集合。为各工件第一道工序的集合。求最小的最早完工时间求最小的最早完工时间 T T*=minT=minTk k,并并找到出现找到出现T T*的机器的机器M M*，若有多台，任选一台。，若有多台，任选一台。从从OOt t 中跳出满足以下两条件的工序中跳出满足以下两条件的工序O Oj j 需要机器需要机器M M*加工；加工；T Tj j T T*将确定的将确定的OjOj放入放入StSt，从，从OtOt中消去中消去OjOj并将并将OjOj的紧后的紧后工序放入工序放入OtOt中，使中，使t=t+1t=t+1。若还有未安排的工序，转步骤若还有未安排的工序，转步骤；否则，停止。；否则，停止。一个实例：一个实例：得到加工顺序矩阵：得到加工顺序矩阵：五、单件车间排序问题（n/m/G/Fmax）3 3、无延迟作业计划的构成无延迟作业计划的构成没有任何延迟出现的能动作业计划。所谓没有任何延迟出现的能动作业计划。所谓“延迟延迟”，指，指有工件等待加工时，机器出现空闲，即使这段空闲时有工件等待加工时，机器出现空闲，即使这段空闲时间不足以完成一道工序。间不足以完成一道工序。构成步骤：构成步骤：五、单件车间排序问题（n/m/G/Fmax）无延迟作业计划的构成步骤：无延迟作业计划的构成步骤：设设t1，SSt t 为空，为空，OOt t 为各工件第一道工序的集合。为各工件第一道工序的集合。求最小的最早完工时间求最小的最早完工时间 T T*=minT=minTk k,并并找到出现找到出现T T*的机器的机器M M*，若有多台，任选一台。，若有多台，任选一台。从从OOt t 中跳出满足以下两条件的工序中跳出满足以下两条件的工序O Oj j 需要机器需要机器M M*加工；加工；T Tj j=T=T*将确定的将确定的OjOj放入放入StSt，从，从OtOt中消去中消去OjOj并将并将OjOj的紧后的紧后工序放入工序放入OtOt中，使中，使t=t+1t=t+1。若还有未安排的工序，转步骤若还有未安排的工序，转步骤；否则，停止。；否则，停止。一个实例：一个实例：得到加工顺序矩阵：得到加工顺序矩阵：