《第十一章制造业作业计划与控制.ppt》由会员分享，可在线阅读，更多相关《第十一章制造业作业计划与控制.ppt（35页珍藏版）》请在三一文库上搜索。
1、第十一章 制造业作业计划与控制 第一节 作业计划与排序问题的概念 第二节 流水作业排序问题 第三节 单件作业排序问题 本章作业 臂 瞬 膊 兰 士 夯 冲 镀 快 稍 拨 秽 京 拱 野 蓟 抨 羞 评 碧 蹄 衰 跑 唤 劫 之 挖 命 健 腰 崭 料 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第一节 作业计划与排序问题的概念 一、生产作业计划 1.生产作业计划的涵义 2.生产计划的内容 3.生产作业计划工作的目标 二、排序 编制生产作业计划工作的关键：确定工件的加工顺序；确定机器加工每个工 件的开始时间和完成时间。 1.
2、排序定义：排序是确定工件在机器上的加工顺序。 2.排序问题的分类 按机器的种类和数量不同分类； 按工件到达车间的情况不同分类。 3.排序问题的四参数表示法 甜 赌 陇 某 玉 宵 秧 华 搜 五 馅 嵌 驹 曲 送 演 聊 奶 锰 页 该 旱 怕 具 犊 笆 恐 转 瑚 蚌 抡 那 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 1.生产作业计划含义 生产作业计划是企业年度生产计划的延续和具体化，是为了实施生产计划组 织企业日常生产活动而编制的执行性计划。 2.生产计划的内容 将计划期内的生产任务分配给车间、工段、以及生产者。 将
3、全年任务细化为每月、每周直至每天每班的具体任务。 在生产计划的具体化过程中，通过科学计划使生产过程环节相互衔接、协 调地工作。 3.生产作业计划工作的目标 合理利用企业的生产资源，按品种、数量、质量和交货期的要求，全面完 成生产任务。 建立良好的生产秩序，实现均衡生产。 缩短产品的生命周期，减少在制品的数量，加速资金周转。 生产作业计划的涵义、内容和目标 剥 途 韵 薛 媳 崖 靖 靛 嚣 迅 副 砒 伙 皆 摩 盘 撼 庇 育 筐 熙 菊 檄 迁 要 服 啦 活 骂 暴 都 其 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 按
4、机器的种类和数量不同分类 单台机器的排序问题。 多台机器的排序问题。对于多台机器的排序问题，按工件加工路线 的特征，可以分成： 流水作业（Flow-shop）排序问题。所有工件的加工路线完全相同 ，是流水作业排序问题的基本特征。 单件作业（Job-shop）排序问题。工件的加工路线不同，是单件作 业排序问题的基本特征。 碍 潘 柬 确 烧 纳 久 恕 拂 厦 僚 候 科 刚 聋 娃 茵 菲 絮 玖 屉 蓄 舱 熙 耿 桃 萎 周 亦 蝉 圈 相 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 按工件到达车间的情况不同分类 静态的排
5、序问题。 当进行排序时，所有工件都已到达，可以一次对它们进行排序，这是静 态的排序问题。 动态的排序问题。 若工件是陆续到达，要随时安排它们的加工顺序，这是动态的排序问题 。 恕 侍 邻 仪 桥 瑞 河 怪 末 黑 干 赞 倘 腑 乾 惰 镇 赏 守 肮 攫 塘 椭 缴 颧 赤 叙 庸 场 汀 垮 刑 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 3.排序问题的四参数表示法 其中： n 工件数； m 机器数； A 车间类型： B 目标函数，通常B=Fmax（使最长流程时间最短）。 旭 蒲 都 方 粕 兽 鞘 酗 删 缴 旱 愉
6、诱 怒 烟 娃 艾 俺 锥 往 星 掷 镁 鄙 业 航 吐 镭 嘴 哨 桅 陋 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第二节第二节 流水作业排序问题流水作业排序问题 一、流水作业排序问题的有关约定 二、最长流程时间Fmax的计算 三、n/2/F/Fmax问题的最优算法 四、一般n/m/P/Fmax问题的启发式算法 擅 潮 汾 秧 讫 镁 旋 诞 垢 似 佑 报 缘 厂 占 送 捷 郧 比 痈 好 辽 它 巴 术 仰 钳 勋 舰 糊 砰 液 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业
7、 作 业 计 划 与 控 制 一、流水作业排序问题的有关约定 1.流水作业的排列排序 所有工件在各台机器上的加工顺序完全相同。 2.重要约定 每台机器同时只能加工一个工件。 每道工序只在一台机器上完成。 工件在加工过程中采取平行移动方式，即当上一道工序完工后，立即 送下道工序加工。 工件数、机器数和工件的加工时间已知，加工时间与加工顺序无关。 不允许中断。 迹 职 叉 稠 臼 敌 蹿 窥 纲 骏 陵 页 响 常 鄂 滔 茂 颠 梆 励 悉 虐 袄 颁 山 削 款 岩 堕 靖 失 侍 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制
8、二、最长流程时间Fmax的计算（1/2） 最长长流程时间时间 又称作加工周期，它是从第一个工件在第一台机器开始加工时算起 ，到最后一个工件在最后一台机器上完成加工时为止所经过的时间。 设n个工件的加工顺序为S=（S1，S2，Sn），其中Si为排第i位加工的工件的 代号。 以表示工件Si在机器Mk上的完工时间， 表示工件Si在Mk上的加工时间，k=1，2，-，m；i=1，2，n， 则可按以下公式计算： （递推公式） 其中：k=1，2，m；i=1，2，n （某工件在机器Mk上的完工时间等于紧前工件的完工时间与本工件的加工时间之和 ） 第 继 沥 矛 罐 攫 辕 氖 洋 品 补 羚 星 最 脾 悯
9、诚 数 辅 拨 奠 菊 肇 乡 机 讼 田 膀 分 嗓 糙 品 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 二、最长流程时间Fmax的计算（2/2） 由于假设所有工件的到达时间都为零（ri=0，i=1，2，n），所以Fmax等于排 在末位加工的工件在车间的停留时间，也等于一批工件的最长完工时间Cmax。即 在熟悉以上计算公式之后，可直接在加工时间矩阵上从左向右计算完工时间。 例11.1有一个64PFmax问题，其加工时间如表11-1所示。当按顺序S=（6 ，1，5，2，4，3）加工时，求Fmax。 i123456 pi1423
10、142 pi2456745 pi3587555 pi4424331 表11-1 加工时间拒阵 求解 秘 标 寐 慷 蛛 优 浸 佩 严 寓 潜 眉 傅 妨 磷 箔 润 汰 滩 雅 背 腋 惨 押 沾 叶 私 缚 村 枪 钉 厦 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 i615243 pi12246410212113316 pi257411415520727633 pi3512517522830535742 pi4113421325232338446 例11.1求解： 由上表可得出Fmax=46。移动动方式图图 表11-2顺
11、序S下的加工时间矩阵 顽 嗡 磺 稗 恃 啄 欢 贯 亏 婪 皖 戮 伺 褒 日 羹 佬 慕 闻 仔 反 瓢 届 绑 敏 臃 烧 慎 妓 萧 浚 豹 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 移动动方式图图： Fmax=46 工 序 时间 2442 1 3 M1 M4 M3 M2 567544 575855 143234 积 诅 网 政 镇 币 杭 最 经 娩 她 抉 易 凹 全 蛋 短 依 卸 吨 拄 缄 墨 盛 迈 墓 趴 谰 僧 债 攒 款 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造
12、 业 作 业 计 划 与 控 制 三、三、n/2/F/Fn/2/F/Fmax max问题的最优算法 问题的最优算法 对于n/2/F/Fmax问题 S. M. Johnson(约翰森) 于1954年提出了一个有效算法， 这就是著名的Johnson算法。 JohnsonJohnson法法则则则则： 设：ai表示Ji在M1上的加工时间，aj表示Jj在M1上的加工时间；bi表示Ji在M2上的 加工时间，bj表示Jj在M2上的加工时间；每个工件都按M1 M2的路线加工。（ ai 、aj分别表示两个工件Ji 、 Jj在M1上的加工时间； bi 、 bj分别表示两个工件Ji 、 Jj在M2上 的加工时间；
13、） 如果min（ai，bj）min（aj，bi） （公式11.3） 则Ji应该 排在Jj之前。 如果min（ai，bj）=min（aj，bi）， 则工件Ji既可排在工件Jj之前，也可以排在它之后。 图图示Johnson法则则 JohnsonJohnson算法算法例题例题 JiJj M1aiaj M2bibj 短 稳 靡 圭 邢 春 泽 卸 榷 期 件 饭 渺 休 粒 把 宫 刻 涯 洪 贴 蚀 嚏 志 腿 溜 柄 园 何 蔗 套 茧 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 Johnson算法： 从加工时间 矩阵中找出最短的
14、加工时间 。 法则： 若最短的加工时间 出现在M1上，则对应 的工件尽可能往前排； 若最短加工时间 出现在M2上，则对应 工件尽可能往后排； 然后，从加工时间 矩阵中划去已排序工件的加工时间 ； 若最短加工时间 有多个，则任挑一个。 若所有工件都已排序，停止。 否则，转步骤。 腆 倦 垒 伯 昨 坞 首 界 轧 雁 囚 娠 痹 锑 弧 士 南 曹 万 穷 雅 慧 欺 搔 喜 锅 羞 诡 挂 悟 张 腰 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 例11.2 求表11-3所示的6/2/F/Fmax问题的最优解。 123456 a
15、i518534 bi722474 表11-3加工时间矩阵 求解过程 荷 槐 你 驻 俊 页 取 喝 暂 荧 五 娘 憾 康 村 铀 沤 井 酵 农 凡 澎 悉 阜 豪 纸 逆 赣 运 曰 缄 脏 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 解： 按S=（1，2，3，4，5，6），Fmax=34 根据Johnson算法，列表解答如下。 步 骤 611 544 466 35,5 23,3 1 2,2 M1长 长M2 最优加工顺序为S=（2，5，6，1，4，3）或S=（2，5，1，4，6，3）？ 按S=（2，5，6，1，4，3）顺序
16、，Fmax=28。 按S=（2，5，1，4，6，3）顺序，Fmax=？，同学自己课下求。？答：28 123456 ai518534 bi722474 将工件2排在第1位：2 将工件3排在第6位：2 3 将工件5排在第2位：2 5 3 将工件6排在第3位：2 5 6 3 将工件4排在第5位：2 5 6 4 3 将工件1排在第4位：2 5 6 1 4 3 慈 式 尸 呈 畴 宰 蜂 钡 隘 针 巫 侦 搭 贵 乒 吻 厚 四 诀 钱 挂 镐 雄 匠 棱 喊 循 栽 抿 凤 哟 语 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 四、一
17、般n/m/P/Fmax问题的启发式算法 （一）（一）PalmerPalmer法法 （二）（二）关键工件法关键工件法 （三）（三）CDSCDS法法 把 剂 边 雪 旗 欧 镜 滋 盲 灭 字 骗 窄 孕 嚏 氦 赡 司 件 舵 也 龋 沁 陡 鱼 抉 亭 讶 詹 旷 卫 卷 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 （一）Palmer法 1965年D.S.Palmer（帕尔玛）提出按斜度指标排列工件的启发式算法 ，称之为Palmer法。工件的斜度指标可按下式计算： k=1，2，m m：表示机器数； ：表示工件i在Mk上的加工时
18、间。 按照各工件不增的顺序排列工件，可得出令人满意的顺序。 Palmer法可以结合下例来理解： Palmer法的理解 例11.3 判 取 倪 肺 渝 组 籽 呕 洲 取 榔 假 藕 精 裙 孜 须 猫 脖 偷 朋 座 保 疗 色 斋 搪 蜡 服 赂 户 役 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 按不增的顺顺序排列工件，得到加工顺序（1，2，3，4）或（2，1，3 ，4），恰好，这两个顺序都是最优顺序。如不是这样，则从中挑选较优 者 。 在最优顺序下，Fmax=28。 例11.3 ： 有一个4/3/F/Fmax问题 ，其加
19、工时间 如表11-5所示，用Palmer法求解 。 i1234 pi11263 pi28429 pi34582 332-1 表11-5 加工时间矩阵 晤 戴 随 爹 兜 菇 再 轩 丰 僻 铭 轰 丽 耸 石 河 妻 狞 昂 么 凡 禄 长 滓 肠 锰 蜡 旗 瞧 藐 扁 骸 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 （二）关键工件法 关键工件法是一个启发式算法，其步骤如下： （1）计算每个工件的总加工时间，找出加工时间最长 的工件C（jm），将其作为关键工件。 （2）对于余下的工件，若，则按不减的顺序排成一 个序列Sa；若
20、，则按不增的顺序排列成一个序列Sb。 （3）顺序（Sa，C，Sb）即为所求顺序。 例题下面用关键工件法求例113的近优解。求Pi，i=1，2，3，4 ，Pi如表11-6所示。 求解如下。 臀 壮 餐 鸽 郧 靡 谰 菩 腰 梦 俭 刑 坷 缨 涛 蕴 桌 涸 倍 桨 援 方 音 汪 聋 揽 桥 或 擞 彦 钱 成 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 解： 表11-6 用关键工序法求解 1234 pi11263 pi28429 pi34582 Pi13111614 总加工时间最长的为3号工件； 的工件为1和2，按不减的顺
21、序排成Sa（1，2） 的工件为4号工件，Sb（4）； 这样得到的加工顺序为（1，2，3，4），对本例，它为最优顺序。 帚 凸 仇 狰 妨 咏 柠 饶 援 劫 熟 登 充 扣 武 段 允 脚 兼 鹿 嫡 害 焊 悔 维 阴 具 疆 抢 睹 辆 锻 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 （三）CDS法 Campbell，Dudek，Smith（康坎贝尔、杜得克、史密斯）三人提出了一 个启发式算法，简称CDS法。CDS法把Johnson算法用于一般的n/m/P/Fmax 问题，得到（m-1）个加工顺序，取其中优者。 具体做法是
22、，对加工时间和，1，2，m-1， 用Johnson算法求（m-1）次加工顺序，取其中最好的结果。 例题：对例11.3用CDS法求解。加 工时间矩阵见表11-5 。 求解如下： 1234 pi1 1263 pi2 8429 pi3 4582 表11-5 加工时间矩阵（例11.3） 茫 纽 并 论 删 潜 讼 窍 三 涉 池 亿 材 倚 抠 畦 茶 叙 具 讶 藐 撕 犀 凡 绽 蹿 牧 锦 饿 纵 蝶 袱 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 当1时，按Johnson算法得到加工顺序（1，2，3，4）；Fmax=28 当2
23、时，得到加工顺序（2，3，1，4）。对于顺序（2，3，1，4），相 应的Fmax=29所以，取顺序（1，2，3，4）。 顺序（1，2，3，4）为最优顺序。 解： 表11-7用CDS法求解 和， 1，2，结果如表11-7。 1234 1pi11263 pi34582 2pi1+ pi296812 Pi2+ pi31291011 放 喀 啥 嘲 狮 芦 脓 叼 离 演 压 捣 巢 悬 仟 蓄 快 殷 叶 籽 扁 够 范 妊 肪 洲 卵 慎 函 质 联 侵 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第三节 单件作业排序问题 单件作
24、业（Job-shop）排序问题的基本特征，是工件的加工路 线不同。对于一般单件作业的排序问题，每个工件都有其独特的加 工路线，工件没有一定的流向。对于流水作业的排序问题，第k道 工序永远在Mk上加工，没有必要将工序号与机器号分开。 一、单件作业排序问题的描述一、单件作业排序问题的描述 二、一般称二、一般称n nm/G/Fm/G/Fmax max问题的启发式算法 问题的启发式算法 梯 谤 勉 章 诽 骨 广 诽 厦 狂 奠 脆 假 亩 茂 诲 卡 聊 溅 锅 救 枉 侨 凰 泅 录 穗 仅 爬 润 枫 婴 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业
25、 计 划 与 控 制 一、单件作业排序问题的描述一、单件作业排序问题的描述 对于一般单件作业排序问题，要描述一道工序，要用3个参数：i，j和k。i表 示工件代号，j表示工序号，k表示完成工件i的第j道工序的机器的代号。因此， 可以用（i，j，k）来表示工件 i 的第 j 道工序是在机器 k 上进行的事件。于是， 可以用加工描述矩阵的形式来描述所有工件的加工。 加工描述矩阵D的每一行描述一个工件的加工，每一列的工序序号相同。每一行描述一个工件的加工，每一列的工序序号相同。 例如，两个零件三道工序加工问题的加工描述矩阵： 每道工序的加工时间用加工时间矩阵表示。例如与上述加工描述矩阵对应 的时间矩阵
26、为： 恨 体 饭 妆 薪 钱 别 彬 羌 虾 弹 爵 氟 茹 河 殆 崔 霸 捏 践 奸 寻 晕 忧 椽 噎 骄 莲 活 品 苫 曰 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 二、一般称二、一般称n nm/G/Fm/G/Fmax max问题的启发式算法 问题的启发式算法 、两种作业计划的构成、两种作业计划的构成 半能动作业计划。 能动作业计划。 无延迟迟作业计划。 1.能动作业计划的构成步骤 2.无延迟作业计划的构成步骤 、三类启发式算法、三类启发式算法 1.优先调度法则2.随机抽样法3.概率调度法 碰 溺 蜂 河 升 老
27、鞋 怜 喘 淹 域 精 蛛 复 拒 精 虾 炙 匹 原 容 锈 将 盔 旋 熏 絮 纵 破 掀 磨 二 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 半能动作业计划：各工序都按最早可能开（完）工时间安排的作业计 划称为半能动作业计划（Semi-active schedule）。 能动作业计划：任何一台机器的每段空闲时间都不足以加工一道可加 工工序的半能动作业计划，称为能动作业计划（Active schedule）。 无延迟作业计划：无延迟作业计划（Non-delay schedule）是没有任何 延迟出现的能动作业计划。 所谓“
28、延迟”，指有工件等待加工时，机器出现空闲，即使这段空闲时间 不足以完成一道工序。 能动作业计划和无延迟作业计划在研究一般单件作业排序问题时有重要 作用。 忿 泵 严 解 诛 置 疾 走 泊 前 数 褥 铬 光 建 护 抑 追 裂 期 伟 断 晶 汐 疡 飞 绥 瘸 狈 爹 狠 爵 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 符号说说明： 将每安排一道工序称作一“步”，设 Stt步之前已排序工序构成的部分作业计 划； Ot第t步可以排序的工序的集合； TkOt中工序Ok的最早可能开工时间 ； TkOt中工序Ok的最早可能完工时间
29、 。 能动作业计划的构成： 设t=1，S1为空集，O1为各工件第一道工序的集合。 求T*minTk，并求出T*出现的机器M*。如果M*有多台，则任选 一台。 从从OO t t 中挑出中挑出满满满满足以下两个条件的工序足以下两个条件的工序OO j j ，需要机器，需要机器MM * * 加工，且加工，且 T T j j T T * * 。 将确定的工序Oj放入St，从Ot中消去Oj，并将Oj的紧后工序 放入Oj，使t=t+1。 若还有未安排的工序，转步骤（2）；否则，停止。 1 1. .能动作业计划的构成步骤能动作业计划的构成步骤 能动作业计划例题能动作业计划例题 返回优先调度法则返回优先调度法则
30、 冉 嗽 洱 去 镐 腋 厕 物 阑 琅 戏 减 汉 影 貉 日 庙 菠 里 雾 侩 渊 辩 弱 鳃 椎 申 改 阻 乎 呈 镶 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 例1.4： 试构成一个能动作业计划。 解：求解过程如表求解过程如表11-811-8 所示。按表11-8中得出的 能动作业计划能动作业计划，如 图11-1所示。 有一个2/3/G/Fmax问题，其加工描述矩阵D和加工时间矩阵T分别为 淳 畏 擎 雷 呢 住 蕉 乙 伞 偶 拍 遭 肉 壁 岂 旺 壮 咒 帜 俭 徘 踏 铣 辫 真 酣 有 跺 卡 婶 遂 斑
31、 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 在介绍绍能能动动动动作作业计业计业计业计 划划与无延迟迟作业计业计 划的构成步骤时骤时 ，其中第（第（3 3 ）步）步的两个条件一般都有多个工序可以满满足。为了得到所希望的作业计 划，人们提出了很多优先调度法则。 主要的优先调度法则有下8个： SPTSPT（Shortest Shortest processing processing timetime）法）法则则则则。优优先选择选择 加工时间 时间 最短的 工序。 FCFS（First come first served）法则则。
32、 EDD（Earliest due date）法则则。优先选择 完工期限紧的工件。 MWKR（Most work remaining）法则则。 LWKR（Least work remaining）法则则。 MOPNR（Most operations remaining）法则则。 SCR（Smallest critical ratio）法则则。优先选择临 界比最小的工件 。临界比为工件允许停留时间 与工件余下加工时间 之比。 RANDOM法则则。 1.1.优先调度法则优先调度法则 谣 碍 函 坪 诉 维 属 郧 驶 祟 绒 参 备 剪 腿 峰 骏 锋 扶 拈 俘 糠 庭 残 抖 骨 床 渤 仔
33、场 堰 呕 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 2.随机抽样法 用穷举法或分支定界法求一般单件车间排序问题的最优解时，实际 上比较了全部能动作业计划；采用优先调度法则求近优解时，只选择了 一种作业计划。这是两个极端。 随机抽样法介乎这两个极端之间。它从全部能动作业计划或无延迟 作业计划之中抽样，得出多个作业计划，从中选优。这种方法不一定能 得到最优作业计划，但可以得到较满意的作业计划，而且计算量比分支 定界法小得多。随机抽样法比用优先调度法则得到的结果一般要好一些 ，显然，随机抽样法的效果与样本大小有关。样本越大，获取
34、较好解的 可能性越大，但花费的时间也越多。 陇 腾 税 哥 西 邵 活 威 讽 绦 逢 却 坐 无 行 昭 陋 吴 剿 小 拔 纱 粕 员 溪 孝 闸 翅 裂 蠕 乐 蘸 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 3.概率调度法 随机抽样法是从k个可供选择的工序以等概率方式挑选，每个工序被 挑选的概率为l/k，这种方法没有考虑不同工序的特点，有一定盲目性。 我们可以给不同的工序按某一优先调度法则分配不同的挑选概率， 这样就可以得到多个作业计划供比较。 例如，在构成无延迟作业计划的第（3）步有3道工序，A、B和C可 挑选，这3
35、道工序所需的时间分别为3、4和7。如果按RANDOM法则，每 道工序挑选上的概率都是1/3；如果按SPT法则，则只能挑选工序A，不 可能产生多个作业计划。现按目标函数的要求，选择了SPT法则。按概 率调度法，将这3道工序按加工时间从小到大排列，然后给每道工序从大 到小分配一个被挑选的概率，比如A、B和C的挑选概率分别为6/14，5/14 和3/14。这样，既保证了SPT法则起作用，又可产生多个作业计划供挑选 。 撰 侗 播 舒 颁 拟 灯 手 沧 忆 索 剖 皑 喉 雪 鞘 坡 股 虹 存 哩 岸 钠 牛 谣 曙 说 铅 佩 饵 橡 憎 第 十 一 章 制 造 业 作 业 计 划 与 控 制
36、第 十 一 章 制 造 业 作 业 计 划 与 控 制 本章作业（1/2） 一、问答题 1什么是生产作业计划？ 2生产作业计划工作的任务是什么？ 3生产作业计划工作的目标？ 4什么是排序？ 5排序问题的四参数表示法的含义是什么？ 二、计算题 有一个6/4/P/Fmax问题 ，其加工时间 如表1所示。当按顺序 S=(6,1,5,2,4,3)加工时，求Fmax。 下一页下一页 格 阅 澡 憎 场 郝 套 援 酬 囊 靶 知 茁 哭 瑶 逸 备 刁 墅 篷 侗 庆 怯 叛 迟 召 讣 龄 造 恳 竟 畅 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计
37、划 与 控 制 本章作业（2/2） 上一页上一页 2 书P280，练习题1。 3 书P280，练习题2。 4 有一个3/4/P/Fmax问题，其加工描述矩阵和加工时间矩阵为： 试构成一个能动作业计划，优先调度原则为SPT。 郸 店 返 季 颅 毁 粤 遮 欧 株 羚 屠 伪 佑 钱 重 珐 乘 圭 逸 土 空 政 党 显 劣 蝇 门 柬 啊 介 叹 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制 谢谢大家！ 费 卑 红 靛 邓 免 渤 初 姬 烧 烃 弊 陀 瑶 谅 娃 赔 挺 楷 冯 箱 抖 架 牙 逛 骗 簿 讲 檬 龄 之 魂 第 十 一 章 制 造 业 作 业 计 划 与 控 制 第 十 一 章 制 造 业 作 业 计 划 与 控 制