生产作业计划与排序.pptx

《生产作业计划与排序.pptx》由会员分享，可在线阅读，更多相关《生产作业计划与排序.pptx（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、排序的作用实例1：油漆生产顺序 某企业生产白、灰、红、蓝四种油漆，每次生产前都有清洗容器的调整准备时间。按怎样的顺序，总的调整准备时间最少？实例2：复印排序问题 有四人同时到达复印室，每人的复印量不同，如何安排顺序，使得他们的平均等待时间和平均流程时间最小？第1页/共45页方案1：白-灰-红-蓝 T-setup=12方案2：蓝-红-灰-白 T-setup=20第2页/共45页按最短工时优先原则（SPT）,结果最优。第3页/共45页一、基本概念排序中常用的几个概念工件（Job）：服务对象；机器（Machine、Processor）：服务者。如：如：n个零件在机器上加工，则零件是工件，设备是机器；

2、个零件在机器上加工，则零件是工件，设备是机器；工人维修设备，出故障的设备是工件，工人是机器。工人维修设备，出故障的设备是工件，工人是机器。第4页/共45页一、基本概念 作业排序也就是要确定工件在机器上的加工顺序，可用一组工件代号的一种排列来表示。如，用（1，6，5，4，3，2）表示加工顺序：J1J6J5J4J3J2。第5页/共45页一、基本概念2 2、作业计划（、作业计划（SchedulingScheduling）作业计划与排序不是一回事，它不仅要确定工件的加工顺序，而且还要确定每台机器加工每个工件的开工时间和完工时间。如果按最早可能开（完）工时间来编排作业计划，则排序完后，作业计划也就确定了

3、。第6页/共45页一、基本概念3 3、排序问题的分类与表示、排序问题的分类与表示1）单台机器与多台机器的排序问题。2）流水车间与单件车间排序问题。第7页/共45页排序问题的分类单机排序和多机排序：按设备的种类和数量：单目标排序和多目标排序：按目标函数的性质流水型与非流水型排序：按工件加工路线的特征（加工路线是否相同）同顺序排列（P P）一般流水型(F):(F):流水车间(Flow-shop)(Flow-shop)非流水型(G):(G):单件车间(Job-shop)(Job-shop)第8页/共45页一、基本概念流水车间排序问题的基本特征：每个工件的加工路线都一样。如车铣磨。这里指的是工件的加工

4、流向一致，并不要求每个工件必须在每台机器上加工。如有的工件为车磨，有的为铣磨。不仅加工路线一致，而且所有工件在各台机器上的加工顺序也一样，这种排序称为排列排序（同顺序排序）。如工件排序为：J1J3J2，则表示所有机器都是先加工J1，然后加工J3，最后加工J2。第9页/共45页一、基本概念单件车间排序问题的基本特征：每个工件都有其独特的加工路线，工件没有一定的流向。第10页/共45页一、基本概念3）表示方法 一般正规的表示方法为：n/m/A/B n：工件数；m：机器数；A：车间类型（F、P、G）；同顺序排列（P P）一般流水型(F):(F):流水车间(Flow-shop)(Flow-shop)非

5、流水型(G):(G):单件车间(Job-shop)(Job-shop)B：目标函数 加工周期 交货期 总费用第11页/共45页一、基本概念4）一般来说，排列排序问题的最优解不一定是相应流水车间排序问题的最优解，但一般是比较好的解。而对于仅有2台或3台机器的情况，则排列排序问题的最优解一定是相应流水车间排序问题的最优解。第12页/共45页符号说明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的完工期限 第13页/

6、共45页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 第14页/共45页一、基本概念4 4、排序问题的假设条件、排序问题的假设条件一个工件不能同时在几台不同的机器上加工。工件在加工过程中采取平行移动方式。不允许中断。每道工序只在一台机器上完成。每台机器同时只能

7、加工一个工件。工件数、机器数和加工时间已知，加工时间与加工顺序无关。第15页/共45页二、最长流程时间最长流程时间（加工周期）：从第一个工件在第一台机器上加工起到最后一个工件在最后一台机器上加工完毕为止所经过的时间。假定所有工件的到达时间都为0，则Fmax等于排在末位加工的工件在车间的停留时间。第16页/共45页二、最长流程时间计算Fmax的几个假定条件：机器M1不会发生空闲；对其它机器，能对某一工件加工必须具备2个条件：机器必须完成排前一位的工件的加工；要加工的工件的上道工序已经完工。第17页/共45页二、最长流程时间第18页/共45页二、最长流程时间ipi1pi2pi3pi46152432

8、55144544453258217533674261012131671115202733121722303542132125323846第19页/共45页三、n/2/F/Fmax问题的算法JohnsonJohnson算法：算法：假定：ai为工件Ji在机器M1上的加工时间，bi为工件Ji在机器M2上的加工时间，每个工件按M1M2的路线加工。第20页/共45页三、n/2/F/Fmax问题的算法JohnsonJohnson算法的步骤：算法的步骤：从加工时间矩阵中找出最短的加工时间。若最短时间出现在M1上，则对应的工件尽可能往前排。若最短时间出现在M2上，则对应的工件尽可能往后排。若最短时间有多个，则

9、任选一个。划去已排序的工件。若所有工件都已排序，则停止，否则重复上述步骤。第21页/共45页n/2/F/Fn/2/F/Fmaxmax流水型排序 第22页/共45页（1 1）按约翰逊-贝尔曼规则排序，得到2-6-3-5-4-12-6-3-5-4-1（2 2）列表计算流程时间第23页/共45页四、一般n/m/P/Fmax问题的启发式算法 对于一般的n/m/P/Fmax问题，可以用分支定界法求得最优解，但计算量很大。实际中，可以用启发式算法求近优解。第24页/共45页四、一般n/m/P/Fmax问题的启发式算法1 1、PalmerPalmer法计算工件斜度指标 i i：m:m:机器数 p pikik

10、 ：工件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第25页/共45页四、一般n/m/P/Fmax问题的启发式算法2 2、关键工件法：计算Pi=Pij，找出Pi最长的工件，将之作为关键工件C。对其余工件，若Pi1Pim，则按Pi1由小到大排成序列SA。若Pi1 Pim，则按Pim由大到小排成序列SB。顺序（SA，C，SB）即为近优解。第

11、26页/共45页四、一般n/m/P/Fmax问题的启发式算法得到的加工顺序为得到的加工顺序为(1，2，3，4)第27页/共45页四、一般n/m/P/Fmax问题的启发式算法3 3、CDS法：CDS法是Johnson算法的扩展方法，从M-1个排序中找出近优解。第28页/共45页四、一般n/m/P/Fmax问题的启发式算法L1，按Johnson算法得到加工顺序(1，2，3，4)，Fmax28L2，按Johnson算法得到加工顺序(2，3，1，4)，Fmax29取顺序(1，2，3，4为最优顺序。第29页/共45页问题描述 流水 (i,j)(i,j)(工件，工序)单件 (i,j,k)(i,j,k)(工

12、件，工序，机器)加工描述矩阵和加工时间矩阵 五、单件车间排序问题（n/m/G/Fmax）第30页/共45页五、单件车间排序问题（n/m/G/Fmax）1 1、问题描述(i，j，k)：表示工件i的第j道工序是在机器k上进行。加工描述矩阵D：每一行描述一个工件的加工，每一列的工序序号相同。D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2第31页/共45页五、单件车间排序问题（n/m/G/Fmax）加工时间矩阵T：与D相对应。D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2T=4 6 35 7 4第32页/共45页五、单件车间排序问题（n/m/G/Fm

13、ax）加工顺序矩阵S：每一行与机器相对应，每一列与工件相对应。D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2S=1,1,1 2,2,11,3,2 2,3,22,1,3 1,2,3第33页/共45页五、单件车间排序问题（n/m/G/Fmax）用方块图表示：D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2S=1,1,1 2,2,11,3,2 2,3,22,1,3 1,2,3T=4 6 35 7 41,1,12,1,31,2,32,2,11,3,22,3,2M1M2M3第34页/共45页五、单件车间排序问题（n/m/G/Fmax）2 2、能动作业计划

14、的构成各工序都按最早可能开(完)工时间安排且任何一台机器的每段空闲时间都不足以加工一道可加工工序。符号说明：Ot 第t步可以排序的工序的集合St t步之前已排序的工序构成的部分作业计划Tk Ot中工序Ok的最早可能开工时间Tk Ot中工序Ok的最早可能完工时间第35页/共45页五、单件车间排序问题（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

15、 Tj j T T*将确定的OjOj放入StSt，从OtOt中消去OjOj并将OjOj的紧后工序放入OtOt中，使t=t+1t=t+1。若还有未安排的工序，转步骤；否则，停止。第36页/共45页一个实例：D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2T=2 4 13 4 5i i1 1OOt t T Tk kT Tk kT*T*M*M*OjOj1,1,11,1,10 02 22 2M1M11,1,11,1,12,1,32,1,30 03 32 21,2,31,2,32 26 63 3M3M32,1,32,1,32,1,32,1,30 03 33 31,2,31,2,3

16、3 37 77 7M3M31,2,31,2,32,2,12,2,13 37 74 41,3,21,3,27 78 87 7M1M12,2,12,2,12,2,12,2,13 37 75 51,3,21,3,27 78 88 8M2M21,3,21,3,22,3,22,3,27 712126 61313M2M22,3,22,3,22,3,22,3,28 81313第37页/共45页得到加工顺序矩阵：S=1,1,1 2,2,11,3,2 2,3,22,1,3 1,2,31,1,12,1,31,2,32,2,11,3,22,3,2M1M2M32 23 37 77 73 38 81313第38页/共4

17、5页五、单件车间排序问题（n/m/G/Fmax）3 3、无延迟作业计划的构成没有任何延迟出现的能动作业计划。所谓“延迟”，指有工件等待加工时，机器出现空闲，即使这段空闲时间不足以完成一道工序。构成步骤：第39页/共45页五、单件车间排序问题（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，从Ot

18、Ot中消去OjOj并将OjOj的紧后工序放入OtOt中，使t=t+1t=t+1。若还有未安排的工序，转步骤；否则，停止。第40页/共45页一个实例：D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2T=2 4 13 4 5i i1 1OOt t TkTkT Tk kT*T*M*M*OjOj1,1,11,1,10 02 20 0M1M11,1,11,1,12,1,32,1,30 03 32 21,2,31,2,32 26 60 0M3M32,1,32,1,32,1,32,1,30 03 33 31,2,31,2,33 37 73 3M3M31,2,31,2,32,2,12,

19、2,13 37 74 41,3,21,3,27 78 83 3M1M12,2,12,2,12,2,12,2,13 37 75 51,3,21,3,27 78 87 7M2M22,3,22,3,22,3,22,3,27 712126 61212M2M21,3,21,3,22,3,22,3,2121213130 0M3M33 3M1M17 7M2M2第41页/共45页得到加工顺序矩阵：S=1,1,1 2,2,12,3,2 1,3,22,1,3 1,2,31,1,12,1,31,2,32,2,11,3,22,3,2M1M2M32 23 37 77 73 312121313第42页/共45页4 4、启

20、发式算法：能动作业计划和无延迟作业计划尽管不一定是最优作业计划，但一般是较好的作业计划，特别是无延迟作业计划能提供令人满意的解。一般能动作业计划和无延迟作业计划都有多个，可用启发式方法从中选择结果较好的作业计划。一般来说，以构成无延迟作业计划的步骤为基础的启发式算法比以构成能动作业计划的步骤为基础的启发算法的效果要好。五、单件车间排序问题（n/m/G/Fmax）第43页/共45页优选调度法则：SPT(Shortest Processing Time)法则：优先选择加工时间最短的工序。FCFS(First Come First Served)法则：优先选择最早进入可排工序集合的工件。EDD(Earliest Due Date)法则：优先选择完工期限紧的工件。MWKR(Most Work Remaining)法则：优先选择余下加工时间最长的工件。LWKR(Least Work Remaining)法则：优先选择余下加工时间最短的工件。MOPNR(Most Operations Remaining)法则：优先选择余下工序数最多的工件。SCR(Smallest Critical Ratio)法则：优先选择临界比最小的工件。五、单件车间排序问题（n/m/G/Fmax）第44页/共45页感谢您的观看！第45页/共45页