制造业作业生产计划.pptVIP

第十一章 制造业作业计划与控制 §11.1 排序问题的基本概念 §11.2 流水作业排序问题 §11.3 单件作业排序问题 §11.4 生产作业控制 流水作业排序问题的基本特征是每个工件的加工线路都一致。 加工线路一致，是指工件的流向一致，并不是指每个工件必须经过加工线路上的每台机器加工。 本节要讨论的是所有工件在各台机器上的加工顺序相同的情况，就是排列排序问题n/m/P/B。 Johnson算法的变形 步骤： 将所有ai≤bi的工件按照ai值不减（递升）的顺序排列成一个序列A； 将所有ai＞bi的工件按bi值不增（递减）的顺序排列成一个序列B； 将A放到B之前，就构成了最优加工顺序。 n / m / P / Fmax问题的启发式算法 启发式算法（试探法）是一种能在可接受的费用内寻找最好的解的技术，但不一定能保证所得解的可行性和最优性，甚至在多数情况下，无法阐述所得解同最优解的近似程度 。 启发式算法是解决NP问题（不确定性问题）的重要方法，由于其计算量都比较大，所以随着计算机技术的发展，启发式算法取得了巨大的成就。 常见的启发式算法有贪婪法、局部有哪些信誉好的足球投注网站法、退火算法、蚁群算法等。  经典算法与启发式算法 驾驶汽车到达某人的家，写成算法是这样的：沿长张高速公路北行至太子庙；从西北出口出来后往山上开4.5公里；在一个杂货店旁边的红绿灯路口右转，接着在第一个路口左转；从左边褐色大房子的车道进去，就是桃源路714?号。 用启发式方法来描述则可能是这样：找出上一次我们寄给你的信，照着信上面的寄出地址开车到这个镇；到了之后你问一下我们的房子在哪里。这里每个人都认识我们——肯定有人会很愿意帮助你的；如果你找不到人，那就找个公共电话亭给我们打电话，我们会出来接你。  本次课小结 相关名次术语（排序、编制作业计划、 派工、赶工、加工线路、加工顺序） 最长流程时间的计算 n/2/F/Fmax问题的最优算法（ Johson算法） 二、三种作业计划 半能动作业计划（Semi-active schedule） 各工序都按最早可能开（完）工时间安排的作业计划 能动作业计划（Active schedule） 任何一台机器的每段空闲时间都不足以加工一道可加工工序的半能动作业计划 无延迟作业计划（Non-delay schedu1e） 没有任何延迟出现的能动作业计划 “延迟”：有工件等待加工时，机器出现空闲，即使这段空闲时间不足以完成一道工序 能动作业计划与无延迟作业计划的生成 符号说明 将每安排一道工序称作一“步”，设： ｛St｝—第t 步之前已排序工序构成的部分作业计划 ｛Ot｝—第t 步可以排序的工序的集合 Tk—｛Ot｝中Ok的最早可能开工时间 T’k—｛Ot｝中Ok的最早可能完工时间 P269 例11.4 有一个2/3/G/Fmax问题，其加工描述矩阵D和加工时间矩阵T已知，求一个能动作业计划。 三、三类启发式算法 优先调度法则 随机抽样法 概率调度法 1.优先调度法则 SPT（Shortest processing time）法则 优先选择加工时间最短的工序 可使工件的平均流程时间最短，从而减少在制品量 FCFS（First come first served）法则 优先选择最早进入可排工序集合的工件 来自排队论，对工件较公平 EDD（Earliest due date）法则 优先选择完工期限紧的工件 可使工件最大延误时间最小 MWKR（Most work remaining）法则 优先选择余下加工时间最长的工件 不同工作量的工件的完工时间尽量接近 1.优先调度法则（续） LWKR（Least work remaining）法则 优先选择余下加工时间最短的工件 使工作量小的工件尽快完成 MOPNR（Most operations remaining）法则 优先选择余下工序数最多的工件 与MWKR法则类似，只不过考虑工件在不同机器上的转运排队时间是主要的 SCR（Smallest critical ratio）法则 优先选择临界比最小的工件（临界比：工件允许停留时间与工件余下加工时间之比） 保证工件延误最少 RANDOM法则 随机地挑一个工件 2.随机抽样法 随机抽样法 ?实际上是对同一个问题多次运用RANDOM法则来决定要挑选的工序，从而得到多个作业计划 ?这种方法不一定能得到最优作业计划，但可以得到较满意的作业计划 效果与样本大小有关。样本越大，获取较好解的可能性越大 从无延迟作业计划母体中抽样所得到的结果比从能动作业计划母体中抽样所得到的结果要好 3. 概率调度法 给不同的工序按某一优先调度法则分配不同的挑选概率，可以得到多个作业计划供比较。 例如，在构成无延迟作业计划的第（3）步 ? 有3道工序，A、B和C