第八讲_制造业作业计划与控制2011-10-20(4)

2020 4 6 第八讲制造业作业计划与控制 1 第八讲制造业作业计划与控制 第一单元排序的基本概念一排序问题的概念二排序问题的分类三假设条件四排序问题的表示方法 第二单元流水线作业排序一最长流程时间Fmax的计算二约翰森算法三CDS法四启发式算法五批量生产排序 第三单元单元件作业排序一问题的描述二启发式算法 2020 4 6 第八讲制造业作业计划与控制 2 讲座大纲 第一单元排序的基本概念一排序问题的概念二排序问题的分类三假设条件四排序问题的表示方法第二单元流水线作业排序一最长流程时间Fmax的计算二约翰森算法 三CDS法四启发式算法五批量生产排序第三单元单元件作业排序一问题的描述二启发式算法 2020 4 6 第八讲制造业作业计划与控制 3 第一部分排序问题的基本概念 一排序问题基本概念1作业计划 确定各工件的加工顺序 加工时间 加工班组等的安排 2排序 确定加工件的加工顺序 2020 4 6 第八讲制造业作业计划与控制 4 二排序问题的分类 2020 4 6 第八讲制造业作业计划与控制 5 三假设条件 1一个工件不能同时在几台不同的机器上加工 2工件在加工过程中采用平行移动方式 即当上一道工序完成后 立即送到下一道工序上加工 3不允许中断 即一个工件开始加工 必须一直进行加工 不得中途停止插入其它工件 4每道工序只在一台机器上完成 5工件数 机器数和加工时间已知 加工时间与加工顺序无关 6每台机器同时只能加工一个工件 2020 4 6 第八讲制造业作业计划与控制 6 四排序问题的表示法 n m A Bn 为工件数 m 为机器数 A 为车间类型 其中 F 为流水线排序问题 不计算时间 P 为流水线排列排序问题 计算时间 G 为单件作业排序问题 B 为目标函数 通常是取其值最小 2020 4 6 第八讲制造业作业计划与控制 7 备注 机器 可以是工厂里的各种机床 也可以是维修工人 可以是轮船要停靠的码头 也可以是电子的计算机中央处理单元 存贮器和输入 输出单元 一句话 表示 服务者 零件 代表 服务对象 零件可以是单个零件 也可以是一批相同的零件 加工路线 是零件加工的工艺过程决定的 它是零件加工在技术上的约束 加工顺序 则表示每台机器加工n个零件的先后顺序 是排序和编制作业计划要解决的问题 2020 4 6 第八讲制造业作业计划与控制 8 第二单元流水线作业排序问题 流水线作业问题的基本特征是每个工件的加工路线都是一致的 它分为两种情况 一种是不同工件的流水线排序 一种是一批工件的排序 2020 4 6 第八讲制造业作业计划与控制 9 一最长流程时间Fmax的计算n m P Fmax 前提 1工件1 2 3 4 5的最佳加工顺序已排好 表中就最佳顺序 2每个工件在设备上的加工顺序已定 且相同 可选择是否加工 不可改变顺序 否则不可用此法计算最长流程时间 转入第三节 2020 4 6 第八讲制造业作业计划与控制 10 二作业排序问题的解决n 2 F Fmax问题 约翰森算法 步骤 1从加工时间矩阵找出最短的加工时间 2若最短的加工时间出现在M1上 则对应的工件尽可能往前排 若最短加工时间出现在M2上 则对应的工件尽可能往后排 然后 从加工时间矩阵中划去已排序工件的加工时间 若最短加工时间有多个 则任挑一个 3若所有工件都已排序 停止 否则转步骤1 2020 4 6 第八讲制造业作业计划与控制 11 Johnson算法的改进 1 将所有ai bi的工件按ai值不减的顺序排成一个序列A 2 将ai bi的工件按bi值不增的顺序排成一个序列B 3 将A放到B之前 就构成了一个最优加工顺序 工件号123456 ai518534 bi722474 2020 4 6 第八讲制造业作业计划与控制 12 三CDS法 康杜贝尔 杜得克 史密斯法三人提出了一个启发式算法 简称CDS法 这种算法可以把约翰森算法用于一般的n m P Fmax 举例 2020 4 6 第八讲制造业作业计划与控制 13 2020 4 6 第八讲制造业作业计划与控制 14 2020 4 6 第八讲制造业作业计划与控制 15 求L等于不同值时的最佳排序 用约翰森发求L 1时的最佳排序 得到最佳排序为 1 2 3 4用约翰森发求L 2时的最佳排序 得到最佳排序为 2 3 1 4 用最长流程时间Fmax计算方法求各最佳排序的Fmax排序为1 2 3 4时 Fmax 28排序为2 3 1 4时 Fmax 29 得出 最佳排序为 1 2 3 4 2020 4 6 第八讲制造业作业计划与控制 16 四一般n m P Fmax问题的启发式算法 一 帕尔玛法 Palmer法 2020 4 6 第八讲制造业作业计划与控制 17 解 计算 i 1 p11 p13 3 2 p21 p23 3 3 p31 p33 2 4 p41 p43 1按 i不增的顺序排列工件 得到最佳加工顺序 1 2 3 4 2 1 3 4 2020 4 6 第八讲制造业作业计划与控制 18 二 关键工件法 2020 4 6 第八讲制造业作业计划与控制 19 工件i1234 机器Pi12163机器Pi24829机器Pi35482 11131614 C 关键工件 Sa 2 1 Sb 4 所求顺序 2 1 3 4 2020 4 6 第八讲制造业作业计划与控制 20 四相同零件 不同移动方式下加工周期的计算 一 顺序移动方式顺序移动方式 一批零件在上道工序全部加工完后才整批转移到下道工序继续加工 T顺 n ti i 1 2 3 m 式中 n为零件加工批量 为第i工序的单件加工时间 m为零件加工的工序数 2020 4 6 第八讲制造业作业计划与控制 21 二 平行移动方式 平行移动方式 每个工件在前道工序加工完毕后 立即转移到后道工序去加工 形成前后工序交叉作业 T平 ti n 1 tL i 1 2 3 m 式中 tL为最长的单件工序时间 2020 4 6 第八讲制造业作业计划与控制 22 三 平行顺序移动方式 1当ti ti 1时 零件按平行移动方式转移 2当ti ti 1时 以i工序最后一个零件的完工时间为基准 往前推移 n 1 ti 1作为零件在i 1工序的开始加工时间 T平顺 n ti n 1 min tj tj 1 i 1 2 m j 1 2 m 1 2020 4 6 第八讲制造业作业计划与控制 23 第三单元单件作业排序问题 一问题的描述描述一道工序需要用3个参数 i j ki 代表工件代号 j 代表工序号 k 表示完成工件i的第j道工序的机器代号 2020 4 6 第八讲制造业作业计划与控制 24 二一般n m G Fmax问题的启发式算法 一 两种作业计划的构成半能动作业计划 各工序都按最早可能开 完 工时间安排的作业计划称为半能动作业计划 能动作业计划 任何一台机器的每段空闲时间都不足以加工一道可加工工序的半能动作业计划 成为能动作业计划 无延迟作业计划 是指没有任何延迟出现的能动作业计划 所谓延迟 指工件等待加工时 机器出现空闲 即使这段空闲不足以完成一道工序 2020 4 6 第八讲制造业作业计划与控制 25 二 能动作业计划的构成步骤 符号说明 每安排一道工序称为一 步 设 St 为t步之前已排序工序构成的部分作业计划 Ot 为第t步可以排序的工序的集合 Tk为 Ot 中工序Ok的最早可能开工时间 Tk 为中工序Ok的最早可能完工时间 2020 4 6 第八讲制造业作业计划与控制 26 能动作业计划构成步骤 1设t 1 S1 为空集 O1 为各工件第一道工序的集合 2求 O1 中各工件的最早开工时间Tk 最早完工时间Tk 3求T min Tk 并求出出现的机器M 如果机器M 有多台 则任选一台 4从 Ot 中挑出满足以下两个条件的工序 需要机器M 加工 且Tj T 5将确定的工序Oj放入 St 从 Ot 中消去Oj 并将该Oj的紧后工序放入 Ot 使t t 1 6若还有未安排的工序 转步骤2 否则停止 2020 4 6 第八讲制造业作业计划与控制 27 2020 4 6 第八讲制造业作业计划与控制 28 无延迟作业计划构成步骤 1设t 1 S1 为空集 O1 为各工件第一道工序的集合 2求 O1 中各工件的最早开工时间Tk 最早完工时间Tk 3求T min Tk 并求出出现的机器M 注意和能动作业计划的区别 如果机器M 有多台 则任选一台 4从 Ot 中挑出满足以下两个条件的工序 需要机器M 加工 且Tj T 注意和能动作业计划的区别 5将确定的工序Oj放入 St 从 Ot 中消去Oj 并将Oj的紧后工序放入 Ot 使t t 1 6若还有未安排的工序 转步骤2 否则停止 2020 4 6 第八讲制造