《《精编》制造业流水作业计划》由会员分享，可在线阅读，更多相关《《精编》制造业流水作业计划（27页珍藏版）》请在金锄头文库上搜索。
1、制造业生产作业计划 华中科技大学管理学院陈荣秋 生产任务的最终落实 MRP确定各车间的零部件投入出产计划 将全厂性的产品出产计划变成了各车间的生产任务 各车间要将车间的生产任务变成各个班组 各个工作地和各个工人的任务 才算落到实处 将任务安排到工作地 牵涉到任务分配和作业排序问题 编制作业计划要解决的问题 工厂里要对每个工人和工作地安排每天的生产任务 规定开始时间和完成时间 医院要安排病人手术 为此要安排手术室 配备手术器械 手术医师和护士 学校要安排上课时间表 使学生能按规定的时间到规定的教室听事先安排的教师讲课 项目计划管理 也是一个作业计划问题 英文Scheduling可以译成编制作业计
2、划或安排日程计划 时间表 编制作业计划实质上是要将资源分配给不同的任务 按照既定的优化目标 确定各种资源利用的时间问题 有关的名词术语 排序 Sequencing 是确定零件在机器上的加工顺序 编制作业计划 Scheduling 则不仅包括确定加工顺序 而且还包括加工任务的分配和加工每个零件的开始时间和完成时间 调度 是作业计划编制后实施生产控制所采取的一切行动 编制作业计划 是加工制造发生之前的活动 火车时刻表是作业计划 火车时刻表制定后 对火车运行的安排 包括发生晚点后的处理 都属于调度 名词术语 续 派工 Dispatching 是在作业计划制定以后 按照作业计划的要求 将具体生产任务通
3、过工票或施工单的形式下达到具体的机床和工人 属于通常所说的 调度 范围 赶工 Expediting 是在实际进度已落后于计划进度时采取的行动 也属于通常所说的 调度 范围 机器 可以是工厂里的各种机床 也可以是维修工人 可以是轮船要停靠的码头 也可以是电子的计算机中央处理单元 存贮器和输入 输出单元 表示 服务者 名词术语 续 零件 则代表 服务对象 零件可以是单个零件 也可以是一批相同的零件 加工路线 是零件加工经过不同机器构成的路线 比如 某零件要经过车 铣 占 磨的路线加工 我们可以用M1 M2 M3 M4来表示 加工顺序 则表示每台机器加工n个零件的先后顺序 是排序要解决的问题 4参数
4、表示法 n m A B 其中 n 零件数 m 机器数 A 作业类型 在A的位置若标以 F 则代表流水作业排序问题 若标以 P 则表示流水作业排列排序问题 若标以 G 则表示一般单件作业排序问题 当m 1 则A处为空白B 目标函数 通常是使其值最小 流水作业计划问题 流水线是流水车间 Flowshop 典型的代表 每个零件的加工路线都一致 只要加工路线一致 M1 M2 M3 Mm 不要求每个零件都经过每台机器加工 最长流程时间Fmax的计算 最长流程时间又称作加工周期6 4 p Fmax问题 当按顺序S 6 1 5 2 4 3 加工时 求Fmax 加工周期为46 n 2 F Fmax问题的最优算
5、法 Johnson算法 从加工时间矩阵中找出最短的加工时间 若最短的加工时间出现在M1上 则对应的零件尽可能往前排 若最短加工时间出现在M2上 则对应零件尽可能往后排 然后 从加工时间矩阵中划去已排序零件的加工时间 若最短加工时间有多个 则任挑一个 若所有零件都已排序 停止 否则 转步骤 求最优顺序 算法步骤的改进 把Johnson算法作些改变 改变后的算法按以下步骤进行 将所有ai bi的零件按ai值不减的顺序排成一个序列A 将所有ai bi的零件按bi值不增的顺序排成一个序列B 将A放到B之前 就构成了最优加工顺序 序列A为 2 5 6 1 序列B为 4 3 构成最优顺序为 2 5 6 1
6、 4 3 与Johnson算法结果一致 Johnson法则只是一个充分条件 不是必要条件 不符合这个法则的加工顺序 也可能是最优顺序 如对例11 2顺序 2 5 6 4 1 3 不符合Johnson法则 但它也是一个最优顺序对于3台机器的流水车间排序问题 只有几种特殊类型的问题找到了有效算法 对于一般的流水车间排列排序问题 可以用分支定界法 求一般n m P Fmax问题近优解 Nearoptimalsolution 的启发式算法 关键零件法CDS法 关键零件法求近优解举例 CDS法 Campbell Dudek Smith三人提出了一个启发式算法 简称CDS法 他们把Johnson算法用于一
7、般的n m P Fmax问题 得到 1 个加工顺序 取其中优者 当 1时 按Johnson算法得到加工顺序 1 2 3 4 当 2时 得到加工顺序 2 3 1 4 对于顺序 2 3 1 4 相应的Fmax 29 所以 取顺序 1 2 3 4 我们已经知道 这就是最优顺序 单件作业排序问题 加工描述矩阵和加工时间矩阵 无延迟作业计划 non delayschedule 的构成 我们称每安排一道工序称作一 步 设 St t步之前已排序工序构成的部分作业计划 Ot 第t步可以排序的工序的集合 Tk Ot 中工序Ok的最早可能开工时间 Tk Ot 中工序Ok的最早可能完工时间 无延迟作业计划的构成步骤
8、 设t 1 S1 为空集 O1 为各工件第一道工序的集合 求T min Tk 并求出T 出现的机器M 如果M 有多台 则任选一台 从 Ot 中挑出满足以下两个条件的工序Oj 需要机器M 加工 且Tj T 将确定的工序Oj放入 St 从 Ot 中消去Oj 并将Oj的紧后工序放入 Ot 使t t 1 若还有未安排的工序 转步骤 否则 停止 优先派工法则 在介绍无延迟作业计划的构成步骤时 其中第 步的两个条件一般都有多个工序可以满足 按什么样的准则来选择可安排的工序 对作业计划的优劣有很大影响 为了得到所希望的作业计划 人们提出了很多优先调度法则 按优先调度法则挑选工序比随意挑选一道工序的方法更能符
9、合计划编制者的要求 同时又不必列出所有可能的作业计划 从而计算量小 迄今 人们已提出了100多个优先调度法则 其中主要的有下8个 SPT ShortestProcessingTime 法则优先选择加工时间最短的工序 FCFS FirstComeFirstServed 法则优先选择最早进入可排工序集合的工件 优先派工法则 续 EDD EarliestDueDate 法则优先选择完工期限紧的工件 MWKR MostWorkRemaining 法则优先选择余下加工时间最长的工件 LWKR LeastWorkRemaining 法则优先选择余下加工时间最短的工件 MOPNR MostOperation
10、sRemaining 法则优先选择余下工序数最多的工件 SCR SmallestCriticalRatio 法则优先选择临界比最小的工件 临界比为工件允许停留时间与工件余下加工时间之比 RANDOM法则随机地挑一个工件 随机抽样法 用穷举法或分支定界法求一般单件车间排序问题的最优解时 实际上比较了全部能动作业计划 采用优先调度法则求近优解时 只选择了一种作业计划 随机抽样法介于这两个极端之间 它从全部无延迟作业计划之中抽样 得出多个作业计划 从中选优 应用随机抽样法时 实际上是对同一个问题多次运用RANDOM法则来决定要挑选的工序 从而得到多个作业计划 概率调度法 随机抽样法是从k个可供选择的工序以等概率方式挑选 每个工序被挑选的概率为1 k 这种方法没有考虑不同工序的特点 有一定盲目性 例如 在构在无延迟作业计划的第 步有3道工序 A B和C可挑选 这3道工序所需的时间分别为3 4和7 如果按RANDOM法则 每道工序挑选上的概率都是1 3 如果按SPT法则 则只能挑选工序A 现按目标函数的要求 选择了SPT法则 按概率调度法 将这3道工序按加工时间从小到大排列 然后给每道工序从大到小分配一个被挑选的概率 比如A B和C的挑选概率分别为6 14 5 14和3 14
