·企业管理与信息化·颜家颂伍晓宇模具生产车间调度算法研究与实现 模具生产车间调度算法研究与实现 颜家颂,伍晓宇 (深圳大学工程技术学院,广东深圳518060)) 摘要:针对模具加工的特点,分析了其车间调度中的各种实际情况和约束关系,针对不同类型设 备推导出了相应的调度公式。引入了“工时虚增值”的概念,并在此基础上提出和实现了相关的 优先权值调度算法。实践证明,该算法具有良好的可行性和实际可靠性。 关键词:生产车间;调度;优先权值;交货期 中图分类号:TP391 文献标识码:A 文章编号:1672-1616(2006)05-0013-04 随着现代生产朝着“品种多样、批量变小、注重 套模具通常由大量零部件构成,不妨把加工 交货期”的方向发展,制造系统的生产调度问题越某个零件称之为一个任务,记为T,则车间若干零 来越受到重视2。以模具生产为代表的多品种、件的加工组成一个任务集T1,T2,…,Tm};某个 单件、小批量生产的企业,用Job-Shop模型作为任务加工过程称之为一个作业,记为J,一个作业 其车间管理的一种重要模式,其计划与调度问题已由若千道工序组成J=1 经成为人们研究的热点。古典的车间调度摸型将 按照上述规则,设车间m台处理机H={P1, Job-Shop问题抽象为一个踅化的模型,即m台P2,…,Pn},n个作业J=J1,J2,…,Jn},各作业 机器、n个作业的调度,已被证实是NP-难问题,在每台处理机上都需要加工,作业J在处理机P 一些启发式算法成为具有吸引力的备选方法近年上的加工工序记为,其计划工时为P(2 来,针对Job-Shp模型的概率的局部搜索方法的 计划工时P由式(1)计算如下 发展引起了人们用局部概率搜索方法求解作业车 (B:-Mi).x 间调度问题的兴趣,如模拟退回法(SA)、禁忌搜索 H 法(TS)遗传算法(GA)等。但是在实际生产式中:B1为零件的预算费用M为零件i的材料 中的车间调度必须着重考虑几个重要的事实:(1)费用;m为零件i在加工第j道工序时的工种费用 物料到达的先后顺序是制约调度顺序的重要因素,系数,n∈(0,1),由企业根据其实际情况预先设 因此必须能及时生成动态的车间调度列表;(2)在定,例如,设定某零件的所有工种中,CNC工种占 进行车间调度时,必须考虑企业自身的作息时间、该零件总加工费用的30%;0为零件在加工第j 工序中途的插入等实际状况;(3)车间不同类型机道工序时由物料类型产生的工种费用系数,∈ 器的工作方式等实际情况也作为必须考虑的因素(0,1),根据零件的物料类型依经验值设定,例如 等 某零件CNC工种的费用制定以后,模腔加工占 针对上述生产调度中的实际因素,本文以模具CNC工种费用的30%;x为由零件i的物料特征 生产调度为对象,阐述了一种主要针对多品种、单产生的系数,x∈(0,1],由实际情况设定,如上 件、小批量生产企业的车间实时调度模型及其算步中的模腔费用依具体零件特征进一步分解,例如 法,并在笔者参与开发的E-poms网络协同制造最大件占50%,其余分解为另外50%;H为零件 平台上实现 在加工第j道工序时,加工该工序的设备的工作费 率,例如某数控机床的工作费率为200元/h 1车间调度模型的建立 b.建立调度规则。 a建立车间调度工序队列及计划工时 车间调度中,依次按照模具、任务、工序的优先 收稿日期:2005-12-27 基金项目:国家自然科学基金资助项目(50245025) 作者简介:颜家颂(1982-),男,湖北洪湖人,深圳大学在读硕士研究生,主要研究方向为网络协同制造技术 s1994-2008ChinaAcademicJournalElectronicPublishingHouseAllrightsreservedhttp:// uninet· 企业管理与信息化 · 颜家颂 伍晓宇 模具生产 车间调度算法研究与实现 模具 生 产 车 间调度算法研究与 实现 颜 家颂 , 伍 晓宇 深圳 大学 工程技术学院 , 广东 深圳 摘要 针对模具加 工 的特点 , 分析 了其 车间调 度 中的 各种 实际 情 况 和 约 束关 系 , 针 对 不 同类 型 设 备推 导 出 了相应 的调 度公式 。 引入 了 “ 工 时虚增 值 ” 的概念 , 并在此基础 上提 出和 实现 了相 关 的 优 先权值调度算法 。 实践证 明 , 该算法具有 良好的 可行性和 实际 可 靠性 。 关键词 生产 车间 调 度 优 先权值 交货期 中图分类号 文献标识码 文章编 号 一 一 一 随着现代生产朝着 “ 品种多样 、 批量变小 、 注重 交货期 ” 的方 向发 展 , 制造 系统 的生 产调 度 问题越 来越受到重视 〔’ , 〕 。 以模具生产 为代表 的多品种 、 单件 、 小批量生 产 的企业 , 用 一 模 型作 为 其车间管理的一种重要模式 , 其计划与调度 问题 已 经成为人们研究 的热点 。 古典 的车间调 度模型将 一 叩 问题抽象为一个理想化的模型 , 即 台 机器 、 个作业的调度 , 已被证实是 一 难 问题 , 一些启发式算法成为具有吸引力的备选方法 , 近年 来 , 针对 一 模型 的概率的局部搜索方法 的 发展引起 了人们用 局 部概率搜索方法求解作业 车 间调度问题的兴趣 , 如模拟退 回法 、 禁忌搜索 法 、 遗 传算法 等 。 但是 , 在 实 际 生 产 中的车间调度必须着重考虑几个重要 的事实 物料到达 的先后顺序是制约调度顺序的重要 因素 , 因此必须能及时生成动态 的 车 间调 度列 表 在 进行车间调度 时 , 必须考虑企业 自身的作息 时 间 、 工序 中途的插人等实际状况 车间不 同类 型机 器的工作方式等实际情况也作为必须考虑 的 因素 等 。 针对上述生产调度 中的实际 因素 , 本文 以模具 生产调度为对象 , 阐述 了一种 主要针对 多 品种 、 单 件 、 小批量 生 产企 业 的 车 间实 时 调 度 模 型 及 其算 法 , 并在笔者参与开发 的 一 网络协 同制造 平台上实现 。 一套模具通常由大量零部件构成 , 不妨把加工 某个零件称之为一个任务 , 记为 , 则车间若干零 件的加 工 组成一 个任务 集 , , … , 某个 任务加工过程称之为一 个作业 , 记 为 , 一个作业 由若干道工序组成 , , , … , 。 按照上述规则 , 设车间 台处理机 尸 , 尸 , … , 尸翩 , 个作业 , , … , 。 , 各作业 在每台处理机上 都需 要加工 , 作业 、 在处理机 上 的加工工序记为 , 其计划工 时为 尸梦 。 计划工时 尸 由式 计算如下 尸 、 一 鱼二澳 卫追羞 伪 车间调度模型 的建立 建立车间调度工序队列及计划工时 。 式 中 乓 为零件 的预算费用 从 为零件 的材料 费用 乳 为零件 在加工第 道工序时的工种 费用 系数 , 乳 任 , , 由企业根据其实际情况预先设 定 , 例如 , 设定某 零件 的所有工 种 中 , 工种 占 该零件总加工费用 的 为零件 ￡在加工第 道工序时 由物料类 型产生 的工种 费用 系数 , 凡 任 , , 根据零件的物料类型依经验值设定 , 例如 , 某零 件 工 种 的 费用 制 定 以后 , 模 腔 加 工 占 工种费用 的 为 由零件 的物料特征 产生 的系数 , ‘ 任 , 」 , 由实际情况设定 , 如上一 步 中的模腔费用依具体零件特征进一步分解 , 例如 最大件 占 , 其余分解为另外 乓 为零件 在加工第 道工序时 , 加工该工序的设备的工作费 率 , 例如某数控机床的工作费率为 元 小 。 建立调度规则 。 车间调度 中 , 依次按照模具 、 任务 、 工序的优先 收稿 日期 一 一 基金项 目 国家 自然科学基金资助项 目 作者简介 颜家颂 一 , 男 , 湖北洪湖人 , 深圳 大学在读硕士研究生 , 主要研究方向为网络协 同制造技术