第九章作业计划与排序.ppt

三 排序问题的描述 工序：一台工件在一台机器上连续加工的过程称为工序。 加工时间：n个工件在机器i上所需要的加工时间，用加工时间矩阵来表示：Pij中，i表示机器，j表示工件。工件Jj在机器i上所需加工时间。 排序问题的描述 最大完工时间或时间表长（Cmax）： 为完成的工件一组工作所需的全部时间，即最后一个被加工完的完工时间。 排序问题的表示方法 排序问题常用四个符号来描述: n/m/A/B 其中, n-----工件数； m-----机器数； B-----目标函数 例：n/3/P/Cmax：n个零件在3台机器上的排列排序问题，使最长加工时间Cmax最短 几种调度准则的比较 第三节 流水车间作业排序 流水车间作业排序是每个工件的加工路线都是一样的 ，称为同序作业排序。但对于同一台机器而言，各工件在其上的加工顺序可能不同。 流水作业排序的特征：流水作业排序问题至少存在一个最优排序，在此最优排序中，最前面的两台机器上各作业的加工顺序相同，在其最后两台上各作业的加工顺序也相同。 第三节 流水车间作业排序 流水车间排列排序是指工件不仅加工路线相同，而且在全部机器上各工件的加工顺序相同。 排列排序中不一定含有最优排序。 例：N个工件在M台机器上加工，流水车间作业排序数为 ；排列排序数为 。 单件车间作业排序 加工描述矩阵： 两台机器的单件作业排序J2 Cmax Jackson算法：见书上 例：求排序问题，J2 Cmax，n=8， 第五节???车间生产控制 一：实行生产控制的原因 1.加工时间估计不正确。 2.随机因素的影响。 3.加工路线的多样性。 4.企业环境的多态性。 第五节???车间生产控制 二.车间生产控制的主要活动 订单审核/投放（下达指令） 包括出产期的设置 系统的订单数量对流程时间、WIP和生产周期有很大影响 作业计划的制定 决定订单流动的路线, 顺序和时间 数据收集/监控 跟踪流程的关键环节 实时动态跟踪 反馈控制 订单部署 调度控制模型 三.车间作业控制的主要功能 确定车间作业指令获取在制品占用信息将车间作业状况信息反馈给上级及有关部门提供实际产出信息提供成本核算所需要的车间生产和在制品信息提供人力、设备等的利用率、效率和生产率信息 四. 车间作业控制的主要工具 甘特图(Gantt Chart) 输入/输出控制(Input/Output Control) 派工单(Dispatching) 计算机辅助作业控制 “漏斗”模型——输入/输出控制 工作地的漏斗模型 漏斗模型的特点： 横坐标为时间，通常以工作日为单位；纵坐标为工作负荷，通常以小时表示。 输入曲线和输出曲线表示在一定观察期内任务到达的累积情况和任务完成的累积情况。 两条曲线上任一时刻的垂直方向的距离表示该时刻在制品占用量，两条曲线上任一时刻的水平方向的距离表示相应工作任务在该工作地停留的时间。（FIFO) 控制规则：书上 五 m(m?3)台机器排序问题的算法 一般采用启发式算法(Heuristics)解决这类问题。 关键工件法 步骤1 计算 ,找出其中最大者，定义为关键工件JC （JC :加工时间最大的工件）。 步骤2 除JC外，将满足pi1pim的工件，按ti1值的大小，从小到大排在JC的前面。 步骤3 除JC外，将满足pi1pim的工件，按tim值的大小，从大到小排在JC的后面。 步骤4 除JC外，将满足pi1=pim的工件，排在JC的前面或者后面。 步骤5 如有多个方案，可再加比较，从中选优。 Pij中i是工件序号，j是设备序号 关键工件法举例 J1 J2 J3 J4 J5 J6 机器1 pi1 5 5 4 1 2 10 机器2 pi2 5 5 5 3 6 10 机器3 pi3 8 3 3 4 7 4 机器4 pi4 2 8 2 1 5 6 机器5 pi5 5 2 1 2 8 10 总和 25 23 15 11 28 40 找出关键工件：工作负荷最大的40，对应的是工件6，所以JC=J6 确定排在关键工件前面的工件：满足步骤2条件的有J4, J5, 所以有J4 – J5 –J6 – 确定排在关键工件后面的工件：满足步骤3条件的有J2, J3, 所以有– J6 –