第章_制造业作业计划与控制.ppt

本章内容 第一节 排序问题的基本概念 第二节 流水作业排序问题 第三节 单件作业排序问题 第一节 排序问题的基本概念 编制作业计划要解决的问题 编制作业计划实质上是要将资源分配给不同的任务，按照既定的优化目标，确定各种资源利用的时间问题。 由于每台机器都可能被分配了多项任务，而这些任务受到加工路线的约束，就带来了零件在机器上加工的顺序问题。 有关的名词术语 排序(Sequencing) 编制作业计划 派工(Dispatching) 控制(Controlling) 赶工(Expediting) “调度”是作业计划编制后实施生产控制所采取的一切行动，“编制作业计划”是加工制造发生之前的活动 “机器”，可以是工厂里的各种机床，也可以是维修工人；可以是轮船要停靠的码头，也可以是电子的计算机中央处理单元、存贮器和输入、输出单元。一句话，表示“服务者” “零件”代表“服务对象”。零件可以是单个零件，也可以是一批相同的零件 “加工路线”是零件加工的工艺过程决定的，它是零件加工在技术上的约束 “加工顺序”则表示每台机器加工n个零件的先后顺序，是排序和编制作业计划要解决的问题 二、假设条件与符号说明 一个工件不能同时在几台不同的机器上面加工 工件在加工过程中采取平行移动的方式 不允许中断 每道工序只在一台机器上面完成 工件数,机器数和加工时间已知,加工时间与加工顺序无关 每台机器同时只能加工一个工件 符号说明 Ji表示工件：i=1,2,…,n Mj表示机器：j=1,2,…,m Pij表示Ji在Mj上的加工时间 Fi表示Ji的流程时间，即工件在车间的实际停留时间 Fmax表示最长流程时间，Fmax= max｛Fi｝ 三. 排序问题的分类和表示法 按加工路线的特征 单件作业排序问题——工件加工路线不同 流水作业排序问题——工件加工路线相同 4参数表示法 n/m/A/B n工件数; m机器数; A车间类型； P——流水作业排序时间; G——一般单件作业排序时间； B为目标函数; 第二节 流水作业排序问题 流水车间(Flow shop):工件的加工路线都一致，典型的如流水线 一、最长流程时间的计算 二、两台机器排序问题的最优算法 三、多台机器排序问题的启发式算法 一、最长流程时间的计算 目标函数Fmax最短；n/m/p/ Fmax问题 从第一个工件在第一台机器开始加工时算起，到最后一个工件在最后一台机器上完成时为止所经过的时间 假设：所有工件的到达时间都为零 例11.1 按顺序S=(6,1,5,2,4,3) 加工求Fmax 按顺序S=(6,1,5,2,4,3)列出加工时间矩阵 按顺序S=(6,1,5,2,4,3)列出加工时间矩阵 按顺序S=(6,1,5,2,4,3)列出加工时间矩阵 按顺序S=(6,1,5,2,4,3)列出加工时间矩阵 按顺序S=(6,1,5,2,4,3)列出加工时间矩阵 按顺序S=(6,1,5,2,4,3)列出加工时间矩阵 按顺序S=(6,1,5,2,4,3)列出加工时间矩阵 按顺序S=(6,1,5,2,4,3)列出加工时间矩阵 课堂练习： 已知加工时间矩阵： 二、 两台机器排序问题的 最优算法 约翰森法则 如果Min(ai, bj) Min (aj, bi),则工件i应该排在工件j之前。 约翰森算法 （1）从加工时间矩阵中找出最短加工时间； （2）若最短加工时间出现在机器M1 上，则对应工件应该尽可能往前排；若最短加工时间出现在机器M2 上，则对应工件应该尽可能往后排。 然后从加工时间矩阵中划去已排序工件的加工时间。若最短加工时间有多个，则任挑一个。 （3）若所有工件都已排序，停止。否则，转步骤（1）。 举例 Johnson算法的改进 1. 将所有ai ≤ bi的工件按ai值不减的顺序排成一个序列A； 2. 将ai＞bi的工件按bi值不增的顺序排成一个序列B； 3. 将A放到B之前，就构成了一个最优加工顺序。 举例 课后习题1 课后习题1 三、多台机器排序问题 关键工件法 1. 计算每个工件的总加工时间，将加工时间最长的工件作为关键工件C； 2. 对于余下的工件，若pi1≤pim则按pi1不减的顺序排成一个序列Sa ,若pi1pim 则按pim不增的顺序排成一个序列Sb; 3. 顺序（Sa,C,Sb）即为所求顺序。 举例 四、相同零件不同移动方式下  加工周期的计算 当n个零件相同，则无排序问题。但不同移动方式下的加工周期不同 三种典型的移动方式 顺序移动方式：一批零件全部加工完成后，整批移动到下道工序加工 平行移动方式：单个零件加工完成后，立即移动到下道工序加工 平行顺序移动方式：两者混合 顺序移动方式 设零件批量为n（件），工序数目为m，一批零件不计算工序间运输时间，只考