成组加工中的加工全程和延误工件数问题.pdf

第 1 0卷第 l期 1 9 9 6年 6月 应 用 数 学 与 计 算 数学 学 报 COM M oN APPL M ATH AND COMPUT Vo 1 1 0 No 1 J l i n e 1 9 96 旺 加 璐 上 樽 大 学 理 学 院 上 樽t 2 0 1 8 0 0 摘 要 本 文 在 同 纽 工 件 连续 加工 的 条 件下 考 虑 了 单 机 加工 中的 二 个 排序 问 题 一 其 目标 函 数 分 别 为扳 小加 工 全 程 和延 误工 件 数 文 中在 不 同 的 条件 下 对 它 们 给 出 了多 项 式时 间算 法 关 捷 词 排 序 成 缸 加 工 加 工 全 程 延误 工件 教 I 弓I 言 不 同于仅考虑逐个工件排列的传统问题 柔性制造系统中的现代技术引出了一些新 的排序问题 即成组 加工 成组加 工显示 了一 个新的 内容 丰富的研究方 向 其解 决可增 强 管 理 的 能 力 改 善 资源 的 利 用 更 能 满 足顾 客的 需要 本文 考虑 下述 n个工件的单台机器 成组加工问题 工件分为m 组 第 组工件记 作 且 其所 含工件数 l且 l n l n 2 n n 对工件 N l 2 n 其到达 时 间 所 需 加 工 时 问 应 交工 时 间 分别 为0 由 当这 n个 工 件 在一 台机 器 上 加 工 时 机器 只 有 加 工 完一 组 工 件 后 才 能 加 工 另一 组工 件 并 且机 器从 加 工一 组 工 件 转 向加工 另 一 组 工件 时需一独立 的调整时间 独立是指机器转 向加工第 组工件 N 时 其所 需 调 整 时 间毋同前 面 加 工的 是 何 组 工 件 还是 刚 开 始 加 工 工 件 无关 要 求 适 当安 排 各 组 工件 间 的加 工 顺 序 和 各组 中工 件 的 加 工顺 序 使 某 目标 函数 值 最 小 应用 三 参数 表示 法 l J j 上述问题可记 之为l r G T g 其中r为工件的准备时 间向量 为机器调 整时 间 向 量 GT 指 同组 工件 顺序 加 工 为 一 给 定 目标 函数 目标 函数 中涉 及 的 工 件完 工 时 间为 工 件本 身 的 完工 时 间 成组加 工中最简单 的是r 0 s j 0时的1 GT E q 问题 其 中q 为工件 的 完 工 时 间 对 此 问 题 Ba k e r 2 J基 于 WS PT 规 则 1 3 J给 出 了多 项 式 时 间解 法 P o t t s和 V a n wa s s e n h o v e l 则介绍了应用复 合工件技术l 解 1 GT L 和 1 GT W 0q 二 问 题的0 n l o g n 算法 其中L 为最大迟后 W 为权因子 P o s n e r 1 6 则在各组 工件间加 工顺序 已定及后 面要引 出的条件 2 下对 i G T w 0 给出了一0 n 算法 文17 则 研究了1 GT L 问题 从上述可知 对 w c 和 这二个 目标函数的成组加 工 研究 得已比较多 本文则对 一 和 即ma k e s p a n和延误工件数这二个 目标函数的 成 组 加 工 分 别 在第 2 3节 加 以研究 2 成组 加 工 中的 问题 目 l 理 1 对 1 GT G 问题 存在这样的最优序 其任日 中工件依到达时间的非 降 序 排列 本 文 1 9 9 6年 1月 1 8 日收 到 t国家 自然 科 学 基盘 资 助 辣 西 维普资讯 I期 孙世 杰 成 组加工 中的加工 全程和延 误工件数何题 一4 g一 证明 我们已经知道 1 r G 问题可依 0 的非降序排列得最 优序 因此对 任 且中工 件 依组 中工 件 到 达 时 间 的非 降 序排 列可 使该 组 工 件 尽 早 完工 由此 而 得 引 理 结 论 定理 1 i r CT l G t 可在0 n l o g n 时闻 内获解 证明依引理 1 不妨设 中工件依 1 t 顺序排列 其中t s r t i 一1 且 S r l s r t 若在某 序 中且 前一批加工的工件完工时间为C 则 且 这组 工件 的完 工时 间为 C B ma x G P 一 斗 r 十P 一 一 r 寸 l l 一 P t p t 1 设其 中m丑 x 十 一 F p t r t r 口 P B O 一 十P t 其 中B J t 此值 同序无关 将其代入 1 得 G 鼠 ma x G P 一 f l P n O 一 一 P t m酞 G P r 一 r B f 一P 一 一 一 1 P 一 一 P t m x C P b i r b o p b f f 其 中r 6 T B O一 P O 一 1 P b i P 一 p t 均 同序无关 因此且 可 由复合工 件 代替 而1 r t a T c lm 问题等价于如此构造的ri ft 个复 合工件的l r C m 问题 后 者可多项式求解 总的计算 量为 0 nlo g n 其 中将各组工件依 r 非 降序 排列所需时间 0 l o g s 0 n l o g n 构造m个复合工件所需时间 0 l o g n 0 n l o g n 排列 1 i l m 个复合工件需时间o m l o g m 0 nl o g n 因此总计算量为0 n l o g n 口 定理2 l r 1 S j C T C 可在0 n l o g 时间内获解 证 明相同于定理l中C 日 的假设 在所给某序 中工件组 夙 的完工时间为 G 鼠 ma x G 巩 P 一 一 P t r P 一 斗P t m酞 G s P 一 P t r B 0 P B E 一 一 P t ma x f G P b O 广 p 6 此时的r b r B q一5 I 一P B Q 一 1 P b O 十P 也 同序无 关 因此 日 可 由复 合工件6 代替 定理2获证 从此定理可看 出 成组加工 中r 和s 的同时存在往往并不 比仅r 或仅 存在时的排 序问题更复 杂 文I7 j 已指 出了此点 3 成 组加 工 中的 问题 对 吩 的成组加工问题 已有的唯一结果 f 6 I 是在各组工件问加 工顺序 巳定 的条件 下获得的 因此我们先讨 论这种情形 此时只要排列组 中的工件 定理3 当各组工件间加工顺序已定时 C T 吩 可在O n o g n l时间 内获最优 序 证 明既然各组 工件间的加 工顺序 已定 我们从第一组起依次排 列各组 中的工件 对Bl利用Mo o r e H o d g s o n l 算 法可 在0 n l l o g n 1 时间 内获 由B1中工件组成 的最 优部分序 1 相应完工时间为 1 p 此是一常数 现对B 2中工件从时刻 维普资讯 应 用 数 学 与 计 算 敛尝 学 报 l 0卷 c o 0 起利用M H算法得最优部分序 2 其完工时间为cp 2 P i 一 对日 m B 1 uB 中工件 从时刻c m一1 起 其中c m一1 丹 利用M H算法得最 B l u uB m 一1 优部分序 m 显然 如此构 成的序o I 1 o 2 l m 即为原问题的最优 序 所需时间为0 n l o g 定理4 当各组工件间加工顺 序已定 时 1 ar l 可在0 n l o g 时间 内获最 优 序 证 明类似于定理3 只需对第 组工件 2 1 应用M H算 法从 时刻c 一1 s 起 便 可 其 中 一 l c 一 1 0 0 B1 u uB l l 在讨论 1 C T U 时我们引进如 文1 6 的下述条件 m J E ax B r 冕 弩 m 2 条件 2 保 证了机器一旦开始加工某组工件 则不空转地莲续加工完这组工件 文i 6 I 在各组工件问加工顺序 已定及条件 2 下对i r cr l H 0 问题给 出了 o 算法 算法 中用 WS P T规则解 中间出现的1 q 问题 对此规则来说 排列 当前工 件仅 同未排工件有关 而用M H算 法求解 1 1 1 问题时 排列某一工件 同前面 已排工 件的完工时间有关 因此相对复杂些 为了讨论I r G r 问题 我 们先分析 相应工 件集占 l 1 2 n 的1 r 问题的求 解 首 先 需 指 出 在r存 在 的 情 况下 工 件 尽早加 工 未必 有 利 例 工 件 r P J 出 若在 时刻 1开始加 工 此 时仅工件1到达 机器 只能加工 件l 当工 件1完工时 其 余工件均到达 应用M H算法排列这些余下工件得全序 1 4 5 2 3 2 若在时刻2开 始加工 此 时全部工件 已到达 用M H算 法得全序 4 5 3 1 2 u i 1 此例 中工件迟开始加工 比尽早开始加 工好 g l 理2 1 r 存在形为 E D 的最优序 其 中E为如期完工工件集 D 为延 误工 件集 若在条件 2 下 则E 中除第一个工件外 其 余工件依EDD序 推 证明若某一最优序 中无如期完工工件或无延误工件 则引理平凡 故不妨设最优 序 中 既有 如 期 完 I I 件 也 有 延 误 工 件 设 为 中最 后 一 个 如 期 完 工 的 工 件 那 么 在将 中J前的所有延误工件均移至 后所得序 显然不差于 且呈 E D 状 引理前一 半 获证 而在条件 2 即m 1 m 0 舛 1 n 下 设最优序 E D 中E的第一个工件为 而E 的排列不呈E DD状 由于在条件 2 下 在工件 完工时 m 4 2 坫 3 2 鲫 2 1 1 3 维普资讯 1期 孙 世 杰 成 蛆 加 工 中 的加 工 全 程 和 延 误 工件 敦 向题 E J中所有工件均 已到达 因此只需对E 中不依E D D序排列 的相邻工件作相邻对交换 便 得 引 理 后 一 半 获 证 定理5 在条件 2 下 1 r 可在D n l o g n 时间内获如引理2所述最优序 证 明对V j C 以工 件 为第一个完工工件 那么 在条件 2 下 当工件 在时刻 r p 完工时 所有其余工件均已到 达 因此可对工件集 从 时刻0 丹 起应用M H 算法年 导 部分 序 面 i dY 为V t 以 为第一个完工工件时的最优序 不一定为原 问题的最优序 作 J J 1 2 n 崮子 1 r 的最优 序中必有 某工件 N 第 一 个完工 此时 这个相应j为第一个完 工工件时的最优序亦为原 问题的最优序 因此 最优序 可在 中找到 构造 所需时间为D l o g n 在 中我最优者所需时间为 D n l o g n 故总计算量为0 n l o g n 若最优序不呈引理2所 述形状 只需如引理2所证作相应调整即可 所需时 间为 D n l o g n 定理 获证 现在我们转 回I r G 问题 我们指出 当各组 工件间加工顺序 已定时 在条 件 2 下 i k G 可如 下在D n l o g n 时间内获解 对 工件组且 3 j 8 1 t 其 中t 3 r q 一1 d 也 l S 出 设在某序 中 且一 l的完 工时间为 且 1 对任给工件J s 1 t 令百 m 且一 1 l r i 对 且 中工件从时刻 P 起用M H算 法得部分序 令 i s f 记 1 1 为 中序 的个数 那么 由定理5得 引理3 在各 组工件 间加工顺 序已定及条件 2 下 1 c I I 存在这样 的最优 序 其任 且 中工件取某 j o h 形式 从此引理知 最优序必可通过从每一 中取一 组 成 从 知 l l n 即 l 中B i 的完工时间至多n 个不同的值 对每一不同完工时间值 从使 最小 B l 角度取一相应的 o U 序 组成集 合 c 显 然 中组 的不 同完工时间值至多 t1 1 个一对且 的每个不同完工时间值c Bd 构造相应的 并仍记所有这样 的 集的并 集为 2 那么l 2 l n l n 2 但 在条件 2 下 M1 中相应 的可 能完工时间集合为 G 1 l U 叶 P 2 2 其中马 即 j B 其不同的完工时闷值最多n b 啦 个 同样地 对每个同的完工时间值 从使 1 u口 最小的角度找 出相应 的 2 l 序 组成集合 如 c l 2 l Ml 2 一 般地 设 一 1 c 心 l 一 2 一 其 中 一 l的完 工时间至多 取n l n l不 同的值 故l s n l n 一 1 n 而形为 l 一 l 的部分 序 的完工时间至多取n l 个不 同的值 对每一 不 同值 取相应使 最小的这样的 序组成 当 m时 中 最小的相应序 f 6 B U B 为1 r G 的最优序 即 定理6 当各组工件问加工顺序 已定时 1 r G 可在D n l o g n 时间内获解 证明由上述过 程知 可得最优序 而构造 及相应的 靠 所 需的时间为 f n 1 n D n l o g n 故算法的计算量为 n l 一 1 n D l o g n D n 3 l o g n 维普资讯 5 2一 应 用数 学 与 计 算数 学 学 报 1 0卷 上述内容讨论 了各组同加 工顺序 已定时的 问题 当各组问加 工顺序束 定时 文 4 J 指出 I cr l E 的求解和计算复杂性仍未解决 参考文献 f 1 R L G r a h a m E L L a w e r J K L e n s t r a a n d A H G Rin n o o y Ka n Op t m z a h o a n d印 m d e t c r m4 n c n o c h e dali ag d u f nn D c r et e M a t h 197 9 6 287 326 1 2 K R Bal k e r r w咖 如 叼u 4 J o h n Wi i e 8 o n g I n c 1 9 7 4 P 8 7 3 W E S mi t h V a n o a J o m mt o J 加 咖e Na v a l B L o g i s t q 1 9 5 6 3 5 9 6 6 4 l C N P o t t a a n d L N V a n w B e n h a I n t 菩 r n g du l I n g w i t h b a c h mg a n d L o t i L I n g a r e v i e w 0 f alg or i t hm a a nd c ompl e x i t y J 0p1 R Soc 1 99 2 43 3 95 4 06 1 5 R L L a w i e r 口 哪 m i m m tot a l w e i g e d m e D n e P 础 n An n Di s c r e t e M at h 19 7 8 2 7 90 l 6 M E o s n e r A 钾u i r f m n d l e 血 f a r d c j k j o h Ma n a g e me n t S c i e n c e t 1 9 8 6 l 3 2 7 3 一 7 3 8 7 孙世杰 到连 时 r 不 同的工件作 盘担如 工 时的置 太退后 同意 应 用科学 学 报 1 9 9 6 1 l 6 6 1 0 8 l A H G Ri n n o o y Ka n Ma c h i c h e d u h a g P m f m c o m p l c t y a n d mP Ma r t i n u s N i j h o ff T he H a gu e 1 976 P 5 9 J M Mo o r e n 删m q 州 咖al o r Y Am r m t h e n mkr 0 如6 M a n a