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

维普资讯 第 10卷 第l期 应用数学与计算数学学报 Vo1．10 No．1 1996年6月 COMM ．oN APPL．M ATH．AND COMPUT Jline 1996 旺 加 璐 【上樽 大学理 学 院，上樽t201800) 摘要 本文在 同纽工件 连续加工 的条件下考虑 了单机加工 中的二个排序 问题一其 目标 函数分别为扳 小加 工全程和延 误工件数．文 中在不同的条件下对它们给出了多项式时 间算法 关捷词 ：排序 ．成缸加工 ．加工全程 ．延误 工件教 ． — — ～ — — — — — — … I．弓I 言 不 同于仅考虑逐个工件排列的传统问题，柔性制造系统中的现代技术引出了一些新 的排序问题 ．即成组加工．成组加工显示 了一个新的内容丰富的研究方 向．其解决可增 强管理的能力、改善 资源的利用，更能满足顾 客的需要． 本文考虑下述n个工件的单台机器成组加工问题：工件分为m组，第 组工件记作 且，其所含工件数 l且 l： nl+n2+ ·+n =n．对工件 ∈N = {l，2．… ，n)，其到达 时间、所需加工时问、应交工 时间分别 为0， ，由．当这n个工件在一 台机器上加工时， 机器只有加工完一组工件后才能加工另一组工件，并且机 器从加 工一组工件转 向加工另 一 组工件 时需一独立 的调整时间，独立是指机器转 向加工第 ，组工件，，∈N 时，其所 需调整时 间毋 同前面 加工的是何组 工件还是刚开始加工工件无关．要求适 当安排各组 工件 间的加工顺序和各组 中工件的加工顺序，使某 目标 函数值最小．应用三参数表示法 _lJj上述问题可记之为l／r- ，GT／g．其中r为工件的准备时间向量， 为机器调整时间 向量，GT指 同组 工件 顺序 加工， 为一给定 目标 函数， 目标函数 中涉及 的工件完工时 间为 工件本身的完工时 间． 成组加工中最简单的是r= 0，sj= 0时的1／GT／Eq 问题，其 中q 为工件 的 完工 时间，对此 问题Baker[2J基于WSPT 规则13J给出 了多项式 时间解法．Potts和Van wassenhovel_‘则介绍了应用复合工件技术l】解1／ …GT／L 和1／ ，GT／∑W0q 二 问 题的0(nlogn)算法，其中L 为最大迟后，W 为权因子．Posner16]则在各组工件间加 工顺序已定及后面要引出的条件 (2)下对i／,．GT／∑w0 给出了一0(n。)算法，文17】则 研究了1／,，GT／L 问题，从上述可知，对∑w c,-和 这二个 目标函数的成组加工 研究得已比较多，本文则对 一 和∑ ，即makespan和延误工件数这二个 目标函数的 成组加工分别在第 2、3节加 以研究 2，成组加工 中的 问题 目l理1 对1／,，GT／G 问题，存在这样的最优序．其任日 中工件依到达时间的非 降序排列 ． 本文1996年 1月18 日收到． t国家 自然科学 基盘 资助辣西 维普资讯 I期 孙世杰：成组加工 中的加工全程和延误工件数何题 一4g一 证明 我们已经知道．1／r／G 问题可依{0)的非降序排列得最优序 因此对任 且 中工件，依组 中工件到达时 间的非 降序排 列可 使该组工件尽早 完工， 由此 而得引理 结论 ． 定理1i／r，CTlGt 可在0(nlogn)时闻内获解． 证明 依引理1，不妨设 中工件依 。+1．… ，t)顺序排列，其中t=s+rti一1，且 Sr|+ls… rt．若在某序 中且 前一批加工的工件完工时间为C．则且 这组工件 的完 工时 间为 C{B。)=max(G+P+一·