制造业作业计划要素.ppt

* 解： T顺= ==4*(10+4+8+12+6)=160 T平= T平顺= =(10+4+8+12+6)+3*12=76 =160-3*(4+4+8+6)=94 11.3 单件作业排序问题 11.3.1 问题的描述 11.3.2 两种作业计划的构成 11.3.3 求解一般n/m/G/Fmax问题的启发式方法 * 11.3 单件作业排序问题 每个工件都有其独特的加工路线，工件没有一定的流向 用加工描述矩阵描述所有工件的加工要求。矩阵的行表示不同的工件；列表示不同的工序；每个元素用一个(i,j,k)三元组表示工件i的第j道工序在机器k上加工 一般n/m/G/Fmax问题无有效算法，通常应用一些启发式算法 * 11.3.1 问题的描述 * D= 1,1,1 1,2,3 1,3,2 2,1,3 2,2,1 2,3,2 T= 2 4 1 3 4 5 加工描述矩阵D和加工时间矩阵T对应 11.3.2 单件作业排序问题 半能动作业计划 各工序都按最早可能开（完）工时间安排的作业计划 能动作业计划 任何一台机器的每段空闲时间都不足以加工一道可加工工序的半能动作业计划，称为能动作业计划 无延迟作业计划 没有任何延迟出现的能动作业计划 延迟指有工件等待加工时，机器出现空闲 * 11.3.2 两种作业计划的构成 * 符号说明： 每安排一道工序称为一“步” {St}—t步之前已排序工序构成的部分作业计划 {Ot}—第t步可排序的工序集合 Tk—{Ot}中工序Ok最早可能开工的时间 Tk’—{Ot}中工序Ok最早可能完工的时间 * 能动作业计划的构成 STEP 1：令t=1，{S1}为空集，{O1}为各工件第一道工序的集合； STEP2：求T*=min{Tk’},并求出T*出现的机器M*。若M*有多台，可按后述启发式规则选择其中的一台； STEP3：从{Ot}中挑出满足以下两个条件的工序Oj：需要机器M*加工，且TjT*； STEP4：将确定的工序Oj放入{St}，从{Ot}中消去Oj，并将Oj的紧后工序放入{Ot}，令t=t+1； STEP5：若{Ot}为空集，停止；否则转到STEP2。 11.3.2 两种作业计划的构成 11.3.2 能动作业计划编制举例 * 11.3.2 能动作业计划编制举例 * 11.3.2 能动作业计划的甘特图 * 2,3,2 1,1,1 2,2,1 1,3,2 2,1,3 1,2,3 3 7 7 8 13 2 3 7 0 时间 机器 M1 M2 M3 11.3.2 能动作业计划的甘特图二 * 2,3,2 1,1,1 2,2,1 1,3,2 1,2,3 2,1,3 2 6 9 7 12 13 2 3 7 0 时间 机器 M1 M2 M3 例题的另一种能动作业计划 11.3.2能动作业计划的甘特图 采用上述方法可找出所有的能动作业计划。 * 无延迟作业计划的构成 STEP 1：令t=1，{S1}为空集，{O1}为各工件第一道工序的集合； STEP2：求T*=min{Tk},并求出T*出现的机器M*。若M*有多台，可按后述启发式规则选择其中的一台； STEP3：从{Ot}中挑出满足以下两个条件的工序Oj：需要机器M*加工，且Tj=T*； STEP4：将确定的工序Oj放入{St}，从{Ot}中消去Oj，并将Oj的紧后工序放入{Ot}，令t=t+1； STEP5：若{Ot}为空集，停止；否则转到STEP2。 * 11.3.2 两种作业计划的构成（续） 11.3.2 无延迟作业计划的构成 * 11.3.2 无延迟作业计划的甘特图 * 2,3,2 1,1,1 2,2,1 2,1,3 1,2,3 3 7 7 12 13 2 3 7 0 时间 机器 M1 M2 M3 1,3,2 11.3.2 无延迟作业计划的甘特图 同能动作业计划的生成一样，采用上述方法可找出所有的无延迟作业计划。 * 11.3.3 三类启发式算法 （1）优先调度法则 构成两种作业计划的第（3）步一般都有多道工序可以满足，按不同的优先调度法则来选择工序，可以得出满足不同目标函数的作业计划 计算量小 已