生产作业计划与排序(ppt 46页).ppt

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

2、平均流程时间最小？,方案1：白-灰-红-蓝 T-setup=12方案2：蓝-红-灰-白 T-setup=20,按最短工时优先原则（SPT）,结果最优。,一、基本概念,排序中常用的几个概念 工件（Job）：服务对象； 机器（Machine、Processor）：服务者。,如： n个零件在机器上加工，则零件是工件，设备是机器； 工人维修设备，出故障的设备是工件，工人是机器。,一、基本概念,作业排序也就是要确定工件在机器上的加工顺序，可用一组工件代号的一种排列来表示。 如，用（1，6，5，4，3，2）表示加工顺序：J1J6J5J4J3J2。,一、基本概念,2、作业计划（Scheduling） 作业计

3、划与排序不是一回事，它不仅要确定工件的加工顺序，而且还要确定每台机器加工每个工件的开工时间和完工时间。 如果按最早可能开（完）工时间来编排作业计划，则排序完后，作业计划也就确定了。,一、基本概念,3、排序问题的分类与表示 1）单台机器与多台机器的排序问题。 2）流水车间与单件车间排序问题。,排序问题的分类,单机排序和多机排序：按设备的种类和数量： 单目标排序和多目标排序：按目标函数的性质 流水型与非流水型排序：按工件加工路线的特征（加工路线是否相同） 同顺序排列（P） 一般流水型(F):流水车间(Flow-shop) 非流水型(G):单件车间(Job-shop),一、基本概念,流水车间排序问题

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

5、Flow-shop) 非流水型(G):单件车间(Job-shop) B：目标函数 加工周期 交货期 总费用,一、基本概念,4）一般来说，排列排序问题的最优解不一定是相应流水车间排序问题的最优解，但一般是比较好的解。而对于仅有2台或3台机器的情况，则排列排序问题的最优解一定是相应流水车间排序问题的最优解。,符号说明,Ji -工件i Mj -机器j pij -工件i在机器j上的加工时间, Pi -工件i总的加工时间 Pi = pij ri -工件i的到达时间 di -工件i的完工期限,wij -工件i在第j道工序的等待时间 Wi -工件i总的等待时间 Wi = wij Ci -工件i的完工时间 C

6、i = ri +Wi+Pi Fi -工件i的流程时间 Fi = Ciri= Wi+Pi Li -工件i的延迟时间 Li = Cidi,一、基本概念,4、排序问题的假设条件 一个工件不能同时在几台不同的机器上加工。 工件在加工过程中采取平行移动方式。 不允许中断。 每道工序只在一台机器上完成。 每台机器同时只能加工一个工件。 工件数、机器数和加工时间已知，加工时间与加工顺序无关。,二、最长流程时间,最长流程时间（加工周期）：从第一个工件在第一台机器上加工起到最后一个工件在最后一台机器上加工完毕为止所经过的时间。 假定所有工件的到达时间都为0，则Fmax等于排在末位加工的工件在车间的停留时间。,二

7、、最长流程时间,计算Fmax的几个假定条件： 机器M1不会发生空闲； 对其它机器，能对某一工件加工必须具备2个条件：机器必须完成排前一位的工件的加工；要加工的工件的上道工序已经完工。,二、最长流程时间,二、最长流程时间,i,pi1,pi2,pi3,pi4,6,1,5,2,4,3,2,5,5,1,4,4,5,4,4,4,5,3,2,5,8,2,1,7,5,3,3,6,7,4,2,6,10,12,13,16,7,11,15,20,27,33,12,17,22,30,35,42,13,21,25,32,38,46,三、n/2/F/Fmax问题的算法,Johnson算法： 假定：ai为工件Ji在机器M

8、1上的加工时间，bi为工件Ji在机器M2上的加工时间，每个工件按M1M2的路线加工。,三、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问题，可以用分

9、支定界法求得最优解，但计算量很大。实际中，可以用启发式算法求近优解。,四、一般n/m/P/ Fmax问题的启发式算法,1、Palmer法 计算工件斜度指标i ： m : 机器数 pik ：工件i在机器k上的加工时间。 M=3 i=-pi1 +pi3 M=4 i=-1.5pi1-0.5pi2 +0.5pi3+1.5pi4 排序方法: 按i从大到小的顺序排列。 按排序的顺序计算Fmax,四、一般n/m/P/ Fmax问题的启发式算法,2、关键工件法： 计算Pi= Pij ，找出Pi最长的工件，将之作为关键工件C。 对其余工件，若Pi1Pim ，则按Pi1由小到大排成序列SA。若Pi1 Pim ，则

10、按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问题的启发式算法,L1，按Johnson算法得到加工顺序(1，2，3，4)，Fmax28 L2，按Johnson算法得到加工顺序(2，3，1，4)， Fmax29 取顺序(1，2，3，4为最优顺序。,问题描述 流水 (i,j) (工件，工序) 单件 (i,j,k) (工件，工序，机

11、器) 加工描述矩阵和加工时间矩阵,五、单件车间排序问题（n/m/G/Fmax）,五、单件车间排序问题（n/m/G/Fmax）,1、问题描述 (i，j，k)：表示工件i的第j道工序是在机器k上进行。 加工描述矩阵D：每一行描述一个工件的加工，每一列的工序序号相同。,五、单件车间排序问题（n/m/G/Fmax）,加工时间矩阵T：与D相对应。,五、单件车间排序问题（n/m/G/Fmax）,加工顺序矩阵S：每一行与机器相对应，每一列与工件相对应。,S=,1,1,1 2,2,1,1,3,2 2,3,2,2,1,3 1,2,3,五、单件车间排序问题（n/m/G/Fmax）,用方块图表示：,五、单件车间排序

12、问题（n/m/G/Fmax）,2、能动作业计划的构成 各工序都按最早可能开(完)工时间安排且任何一台机器的每段空闲时间都不足以加工一道可加工工序。 符号说明： Ot 第t步可以排序的工序的集合 St t步之前已排序的工序构成的部分作业计划 Tk Ot中工序Ok的最早可能开工时间 Tk Ot中工序Ok的最早可能完工时间,五、单件车间排序问题（n/m/G/Fmax）,能动作业计划的构成步骤： 设t1，St为空，Ot为各工件第一道工序的集合。 求最小的最早完工时间 T*= minTk ,并找到出现T*的机器M*，若有多台，任选一台。 从Ot中跳出满足以下两条件的工序Oj 需要机器M*加工； Tj T

13、* 将确定的Oj放入St，从Ot中消去Oj并将Oj的紧后工序放入Ot中，使t=t+1。 若还有未安排的工序，转步骤；否则，停止。,一个实例：,i,1,Ot,Tk,Tk,T*,M*,Oj,1,1,1,0,2,2,M1,1,1,1,2,1,3,0,3,2,1,2,3,2,6,3,M3,2,1,3,2,1,3,0,3,3,1,2,3,3,7,7,M3,1,2,3,2,2,1,3,7,4,1,3,2,7,8,7,M1,2,2,1,2,2,1,3,7,5,1,3,2,7,8,8,M2,1,3,2,2,3,2,7,12,6,13,M2,2,3,2,2,3,2,8,13,得到加工顺序矩阵：,1,1,1,2,

14、1,3,1,2,3,2,2,1,1,3,2,2,3,2,M1,M2,M3,2,3,7,7,3,8,13,五、单件车间排序问题（n/m/G/Fmax）,3、无延迟作业计划的构成 没有任何延迟出现的能动作业计划。所谓“延迟”，指有工件等待加工时，机器出现空闲，即使这段空闲时间不足以完成一道工序。 构成步骤：,五、单件车间排序问题（n/m/G/Fmax）,无延迟作业计划的构成步骤： 设t1，St为空，Ot为各工件第一道工序的集合。 求最小的最早完工时间 T*= minTk ,并找到出现T*的机器M*，若有多台，任选一台。 从Ot中跳出满足以下两条件的工序Oj 需要机器M*加工； Tj = T* 将确

15、定的Oj放入St，从Ot中消去Oj并将Oj的紧后工序放入Ot中，使t=t+1。 若还有未安排的工序，转步骤；否则，停止。,一个实例：,i,1,Ot,Tk,Tk,T*,M*,Oj,1,1,1,0,2,0,M1,1,1,1,2,1,3,0,3,2,1,2,3,2,6,0,M3,2,1,3,2,1,3,0,3,3,1,2,3,3,7,3,M3,1,2,3,2,2,1,3,7,4,1,3,2,7,8,3,M1,2,2,1,2,2,1,3,7,5,1,3,2,7,8,7,M2,2,3,2,2,3,2,7,12,6,12,M2,1,3,2,2,3,2,12,13,0,M3,3,M1,7,M2,得到加工顺序

16、矩阵：,1,1,1,2,1,3,1,2,3,2,2,1,1,3,2,2,3,2,M1,M2,M3,2,3,7,7,3,12,13,4、启发式算法： 能动作业计划和无延迟作业计划尽管不一定是最优作业计划，但一般是较好的作业计划，特别是无延迟作业计划能提供令人满意的解。 一般能动作业计划和无延迟作业计划都有多个，可用启发式方法从中选择结果较好的作业计划。 一般来说，以构成无延迟作业计划的步骤为基础的启发式算法比以构成能动作业计划的步骤为基础的启发算法的效果要好。,五、单件车间排序问题（n/m/G/Fmax）,优选调度法则： SPT(Shortest Processing Time)法则：优先选择加工时间最短的工序。 FCFS(First Come First Served)法则：优先选择最早进入可排工序集