非量产模式下基于约束加优先权值调度技术与算法一吴序一王志勇伍晓宇等 述如图4所示,表示当目标G受CM的时间约束 其中又分两种情况:①L<0,这种情况便是 时其任务的操作开始时间必须先于约束时间t这前面进行目标任务分解时遇到的那种目标间既存 种约束主要适用于对模具交货时间有要求,但允在一定前后工艺链接约束,又存在一定程度上的 许模具在一定时间段内完成的情况。一般根据经并行协作的约束,相对于下面一种链接约束,这种 验公式计算出模具的估计生产周期及里程碑式子链接约束在允许的情况下可有效地提高生产效 周期,并计算出“先于开始”约束时间,使里程碑率;②L≥0,这种链接约束较上面一种链接约束 式最初子目标满足约束即可 在时间上显得较为宽松,但在某些特殊任务的完 inf(a)≤t 成中则普遍存在,如模具经某些表面处理或热处 理后需放置一段时间方可进入下一工序的加工 定义4特别地,当多个日标[G1,G2,…,G (n≥3)满足CmnG,O1,L)(i=1,2,…, n-1)时,称GNn=LG1,G2;…,Gn](n≥3)为 图4“先于开始”时间约束C 目标链,m=∑a+∑L表示G的理论 1.3目标链接约束 总时间区间。同时Ch1(Ghsn,t)表示C1(Gn,t), 总目标的达成是以各子目标的完成来实现Cn(G,t)表示Cm(Gn,) 的,在这个过程中各子目标的协作存在着约束关 目标链的描述在实际生产中普遍存在,几乎 系生产中的工艺链约束关系就属于这一类,我们所有的目标分解到最底层的子目标后都可以用目 将其定义为目标链接约束Cdm 标链的定义来描述整个目标的达成过程,在模具 定义3c={<G,G,L>1(30[6=生产上则反映为满足生产工艺流程的整个或部分 mf(a1)-黜p(a1)-L≥0,其中, Hodson(G,工序链 OP,a)且 Holds-on(G,OP,a)]},当满足这种1.4多目标达成的资源竞争约束 约束时,称G为G的具有间隔时间段代数量L的 目标的达成需要各种资源,在资源相对目标 前置目标G=,由函数Chn(G,G,L)表示这种有限的情况下必将形成多目标达成的资源竞争 约束关系 对于模具制造这种按订单、非量产模式,其基本原 定义3目标链接约束Cm的甘特图描述如图料一般都可以按照订单提前做好准备,且由于都 5所示,表示当目标G受具有间隔为L的目标G;是小批量甚至单件的生产,所以很难形成根目标 的链接约束C时,G操作开始时间inf(a,)必间物料资源的激烈竞争。而对于同级别且互相不 须在G操作结束时间p(a)加上间隔L后的某存在链接约束的子目标,则可能由于目标作用对 时刻开始,即以p(a)+L≤if(a)或L≤象相同而存在多目标对同一物料资源的竞争约 inf (a )-sup(ai) 束。此外,对于生产中的设备资源,尤其是价格昂 Cebi 贵、数量有限的高等级设备,也普遍存在多目标的 资源竞争 1.4.1物料资澴争约 对于某个目标G的达成所需要的物料资源 M。一般含有若干不同物料资源,表示为M n(a, )sp(a,) mc1,mc2,mn](n≥1)。以目标只有一个物 (a)L≤mf(a1)一(a)<0的情况 料资源为例,如具有相同根目标的目标G1和目标 G2的物料资源分别为M1=[mc-],Ma2 [ma-1],若mo-1=m21且两目标间没有先后链 接约束关系,即两目标物料资源相同但未形成目 标链,则两目标将受物料资源竞争约束,虽然相对 独立但也不能并行完成而必须有先后次序。与前 p(a;)i∫(a,) 文描述链接约束关系不同的是,目标间的先后次 序是可交换的,如模具加工中,对同一工件若有两 (b)0≤L≤加(a)一黜p(a)的情况 道工序没有先后的工艺链接约束,则分别完成两 日5自标豔技的束Ca 个目标的这两道工序就存在上述的物料资源约束 201994-2009ChinaAcademicJournalElectronicPublishingHouse.Allrightsreservedhttp:/www.cnki.net非 产模式下基 于约束加优先权值调度技术与算法 — 吴序一 王 志勇 伍晓宇等 述如图 所示 , 表示 当目标 受 的时间约 束 时其任务的操作开始时间必须先于约束时 间 。 这 种约束主要适 用 于对 模具交货时 间有要 求 , 但允 许模具在一定 时间段 内完成 的情况 。 一 般根 据经 验公式计算出模具 的估计生产周期及里程碑式子 周期 , 并计算 出 “ 先 于 开 始 ” 约束时 间 , 使里 程 碑 式最初子 目标满足约束即可 。 动 《 圈 “ 先于开蜻 ” 时间约束 认 目标链 接约柬 总 目标 的达成是 以各级子 目标 的完成来实现 的 , 在这个过程 中各子 目标 的协作存在着约束关 系 。 生产 中的工艺链约束关系就属于这一类 , 我们 将其定义为 目标链接约束 如 。 。 定 义 ‘ , 场 , 日的 , 认 一 二 ‘ 一 妻 , 其 中 , , 印 , 。‘ 且 场 己 一 。 , , , 〕 , 当满足这种 约束时 , 称 ‘ 为 , 的具有间隔时间段代数量 的 前里 目标 阶 , 由函数 亡‘ 。。 ‘ , , 表示这种 约束关系 。 定义 目标链接约束 ‘ 的甘特图描述 如图 所示 , 表示 当目标 乓 受具有间隔为 的 目标 ‘ 的链接约束 抽 。。 时 , 操作开 始时间 , 必 须在 ‘ 操作结束时间 ‘ 加上 间隔 后 的某 一 时刻开始 , 即 二 , 或 , 一 二 ‘ 。 沁, 匕龙 了 , , 。‘ 《 加 , 一 二 ‘ 的情况 口 『 曰 , ‘ , 匡七 , 之 , 万 ‘ ’ , 少 , 《 ‘ 加 约 一 二 ‘ 的情况 圈 目标挂彼的柬 如 其 中又 分两 种情况 ① , 这种情况便是 前面进行 目标任务分解 时遇 到 的那种 目标间 既存 在一定前后 工 艺链 接约束 , 又 存在 一 定 程度上 的 并行协作的约束 , 相对 于下 面一 种链 接约束 , 这 种 链 接约束在 允 许 的 情 况 下 可 有 效 地 提 高生 产 效 率 ② , 这 种链 接约束较上 面 一种链接约 束 在时间上显得较为宽松 , 但在某些 特 殊 任务 的 完 成中则普遍存在 , 如模具 经 某些 表面 处 理 或 热处 理后需放置一段 时间方可进 人下 一 工序的加工 。 定义 特别地 , 当多个 目标 , , … , 。 满足 、。 ‘ , 二 , ‘ , , … , 一 时 , 称 仅‘ 。 , , , … , , 〕 为 一 目标链 , 。‘、 。 习 。 、十 艺 ‘ 表示 。、 。 的理 论 总时间 区 间 。 同时 、 。 , 表 示 , , , , 。、 。 , 表示 。 , , , 。 目标链 的描述在实际 生 产 中普遍 存在 , 几 乎 所有 的 目标分解到最底层 的子 目标后 都可 以用 目 标链的定义来描述整 个 目标 的达 成过 程 , 在模具 生 产上则反 映为满足生 产工 艺流程 的整个或部分 工 序链 。 多 目标达成的资源竞争约束 目标的达 成需要 各种 资源 , 在资源 相对 目标 有 限的情况下必 将形成多 目标达成的资源 竞争 。 对于模具制造这 种按订单 、 非量产模式 , 其基本原 料一般都可 以按照 订 单提前做好 准备 , 且 由于 都 是小批量 、 甚 至单件的生产 , 所 以很难形成根 目标 间物料资源 的激烈竞争 。 而 对 于 同级 别且 互 相 不 存在链接约束的子 目标 , 则 可 能 由于 目标 作用 对 象相同而存在 多 目标对 同一 物料 资源 的竟 争约 束 。 此外 , 对 于 生 产 中的设 备资源 , 尤其是价格 昂 贵 、 数量有限的高等级设备 , 也普遍存在多 目标 的 资源竞争 。 物料资摄义争约来 对 于某个 目标 的 达 成 所 需 要 的物 料 资源 一 般含 有 若 干 不 同物 料 资源 , 表示 为 七 〔 , 。 , … 。 , 》 。 以 目标只有一 个物 料资源 为例 , 如具有相 同根 目标 的 目标 , 和 目标 味 的物 料 资 源 分 别 为 乙 【 。一 〕决编 。一 , 若 一 卜 且 两 目标 间没 有先后 链 接 约束关 系 , 即两 目标 物 料 资源 相 同但未形成 目 标链 , 则两 目标将受物料资源 竞争约束 , 虽然相对 独立但也 不能并行完成而 必 须 有 先后 次 序 与前 文描述链 接约束关 系不 同的是 , 目标 间 的先后 次 序是 可 交换 的 , 如模具加工 中 , 对 同一工 件若有 两 道工序没 有先后 的工 艺链 接约 束 , 则 分 别完 成 两 个 目标 的这 两道 工序就存在上 述 的物料 资源 约束 ·