非量产模式下基于约束加优先权值调度技术与算法—吴序一王志勇伍晓宇等 非量产模式下基于约束加优先权值调度技术与算法 吴序一13王志勇3伍晓宇!陈锦盛12 1.深圳大学,深圳,5180602.佛罗里达国际大学,迈阿密,美国,FL33174 3.深圳标准技术研究院,深圳518033 要:根据面向网络协同制造的需要及非量产的特点,对该生产模式进行一种新的调度目 标并行分解,提出了“先于完成”时间约束Cm1和“先于开始”时间约柬C-n、目标链接约束Cn 以及目标链G等概念定义。在此基础上分析了协作多目标时的物料资源竞争和设备资源 竟争,提出了基于约東的加优先权值调度算法,该算法能有效解决非量产模式下的排程调度 问题 关键词:非量产,目标约束,生产调度,网络协同制道 中图分类号:TP391.72 文章纲号:1004-132X(2008S1-0161-07 Scheduling Tecnology ad Algorithm Based on Priority Constraints in Job Shop Mode Wu Xuyi.3 Wang Zhiyong Wu Xiaoyu Chen Chinshen'2 Shenzhen University, Shenzhen, Guangdong, 518060 2. Florida International University, Miami, USA, FL33174 3. Shenzhen Institute of Standards and Technology, Shenzhen, Guangdong, 518033 Abstract: According to the special characteristics of job shop mode facing to network cooperative manufacture, the scheduled goal can be decomposed in a parallel way. and the definitions of"Finish No Late Than"time constraint Cnlt, the "Start No Late Than"time constraint Canlt, goal chain con straint Chain and goal chain Chain were proposed. Based on such constraints, competitions of material re sources and equipment resources when coordinating multiple goals were analyzed. And a simple algo rithm based on priority constraints was brought out. It can solve the Job Shop schedule problems effi Ciency Key words shop; goal constraint; scheduling; network cooperative manufacture 0引言 优先权值的算法,并在网络协同制造系统E 制造过程中对生产计划、生产调度的要求越 proms上进行了实现 来越高,由此产生了各类生产调度、生产计划排程 调度平台相关约束分析 系统。然而,在不同行业、不同制造背景下系统所 考虑的问题各异,以广东顺德某大型模具制造厂1.1目标任务分解 为例,其生产模式是按订单、小批量单件非量产模 在生产中为了完成模具产品的制造,通常将 式,对于模具的生产要求主要体现在需要将其做总任务分解为多级多子目标,通过各子目标间的 得又快又好,并按时交货,对于这种典型的非量相互协作满足各约束最终实现产品的制造。在传 产模式,主要考虑生产工序的各种时间约束、工序统的生产制造中,通常以BOM表为中心来完成 间的链接约束以及资源竞争问题。同时,现代化任务分解,建立BOM表非常关键。然而,在实际 制造还要求多部门甚至多企业进行协同制造,因生产中发现,若采用图1所示的传统的完全串行 此需要系统能充分考虑协同制造的情况 化的目标任务分解来构建调度平台架构,则平台 目前,国内外有很多学者从事生产调度方面对底层子目标的管理、监控完全依赖于BOM表 的研究1-3,并提出了形式、特长各异的算法然这种串行的分解可能限制实际生产效率的提高, 而多数研究是在理论或者模型仿真上进行的,能其产生原因主要是模具设计制造过程的短时性 够应用到实践中指导生产的极少。本文致力于面多变性。BOM表本身的完成也是子目标之一,它 向应用的非量产计划调度问题的约束调度技术研所产生的约束却可能是全局性的。例如,对于某 究,在此基础上提出一种结构简单的基于约束加些简单的塑胶模,在具备产品规格书、草图等而 收稿日期:2005-06-15 BOM表尚未建立的情况下,若按照传统的分解模 基金项目:国家自然科学基金资助项目(50235024) 式,设计部门将等待BOM表的完成才开始设计, ·161· 201994-2009ChinaAcademicJournalElectronicPublishingHouse.Allrightsreservedhttp://www.cnki.net非 产棋式下墓于约束加优先权值调度技术 与算法 — 昊 序一 王 志勇 伍晓宇等 非量产模式下基于约束加优先权值调度技术与算法 吴序一 ’, 王 志 勇 伍 晓 宇 ’ 陈锦盛 , , 深 匀, 大 学 , 深 匀, , 佛 罗里 达 国 际 大 学 , 迈 阿 密 , 美 国 , 深 匀 标 准技术研 究院 , 深 匀, 摘要 根 据 面 向 网络协 同制造 的 需要及 非 产的特点 , 对该 生 产模 式进行 一 种 新 的调 度 目 标 并行 分 解 , 提 出 了 “ 先 于 完成 ” 时 间约 束 和 “ 先 于 开 始 ” 时 间 约 束 ‘ 、 、 目标链接 约 束 、 以 及 目标 链 ‘ 。 等概 念 定义 。 在此 基础 上 分 析 了协 作 多 目标 时 的 物料 资源 竟 争和 设 备 资源 竟争 , 提 出 了基 于约束的加 优 先权 值 调 度 算法 , 该 算法 能 有效 解决 非 童 产模 式 下 的排 程 调 度 问题 。 关健 词 非量产 , 目标约束 , 生产调 度 , 网络协同制造 中圈分类号 文章编号 一 一 一 五 心 五 五 · , ‘, , , , , , , , , , , , “ , , 司 , “ , , , , ‘ 。 ‘ 。。 , 竺 引言 制造过程 中对 生 产计 划 、 生 产 调 度 的要 求越 来越高 , 由此产生 了各类生产调度 、 生产计划排程 系统 。 然而 , 在不 同行业 、 不 同制造背景下 系统所 考虑的问题各异 , 以广东顺 德某大型 模具 制造 厂 为例 , 其生 产模式是按订单 、 小批 量单件非量产模 式 , 对 于模具 的生 产要 求主要 体现 在需要 将其做 得又快又好 , 并按时交货 , 对 于这种典型 的非量 产模式 , 主要考虑生 产工序的各种时间约束 、 工 序 间的链接约束 以及 资派竞争问题 。 同时 , 现 代化 制造还 要求多部 门甚 至 多企 业 进 行协 同制 造 , 因 此 需要 系统能充分考虑协同制造 的情况 。 目前 , 国内外有很 多学者 从事生 产 调 度方 面 的研究〔, 一 〕, 并提 出 了形 式 、 特 长各异 的算法 , 然 而 多数研究是在理论 或者模型仿 真上 进 行 的 , 能 够应用 到实践 中指导生产的极少 。 本文致力于面 向应 用 的非 产计划调度问题 的约束调度技术研 究 , 在此基础 上 提 出一 种结构简单 的基 于 约 束 加 收稿 日期 一 一 ‘ 金项 目 国家 自然科学鑫金资助项 目 优先权值 的算法 , 并 在 网 络 协 同 制 造 系 统 一 上 进行 了实现 调度平 台相关约束分析 目标任务分解 在生 产中为了完成模具 产品 的制造 , 通 常将 总任务分解 为多级 多 子 目标 , 通 过 各子 目标 间 的 相互 协作满足各约束最终实现产品 的制造 。 在传 统 的生产制 造 中 , 通 常 以 表 为 中心 来 完成 任务分解 , 建立 表非 常关键 。 然 而 , 在实际 生产 中发 现 , 若采用 图 所 示 的传统 的完 全 串行 化 的 目标任务分解来构建调 度平 台架构 , 则平 台 对底层子 目标 的管理 、 监 控 完全依 赖于 表 。 这种串行 的分解 可 能 限制 实际 生产 效率 的提 高 , 其产生原 因主要 是模具设 计 制造 过 程 的短 时性 、 多变性 。 表本身的完成也是子 目标之一 , 它 所 产生 的约 束 却可 能是 全 局 性 的 。 例 如 , 对 于 某 些 简单 的 塑胶 模 , 在 具 备产 品 规 格 书 、 草 图 等 而 表 尚未建立 的情况 下 , 若按 照 传统 的分 解模 式 , 设 计部门将等待 表 的 完成 才开 始设 计