（概率论与数理统计专业论文）加工时间恶化的成组加工排序问题.pdf

加工时间恶化的成组加工排序问题 中文摘要 中文摘要 本文包括四个部分，第一章引言介绍了排序问题的一些背景知识第二章对 工件的加工时间是其开工时间恶化函数的情形，分别研究了单机成组加工总完工 时间li 胁_ 6 矿嘞，s ，g r i g 问题，流水作业成组加工时间表长f ml = g 乒，矿= 的，g t , 西ig 。问题，流水作业成组加工总完工时间f ml = g i v ， g ，= 的，g t , 岛i 白问题。对以上这些问题都给出了最优解。机器使用时间受 限的单机成组加工时间表长1ip c = a c t f ，( b l ，b 2 ) ，g t ，s 产铂ig 。问题，转化为了 o 1 整数规划问题。第三章对工件具有相同加工时间和相同窗口交货期的e t 调 度问题，给出了简洁的数学模型和计算公式。第四章综述了论文的结果，并给出 了一些展望。 关键词：排序，成组技术，时间表长，总完工时间，流水作业，线性恶化。 作者：金霁 指导教师：闻振卫 加工时间恶化的成组加工排序问愿a b s t r a c t s c h e d u l i n gp r o b l e mi ng r o u pp r o c e s s i n gw i t h d e t e r i o r a t i o np r o c e s s i n gt i m e a b s t r a c t t h i st h e s i sc o n s i s t so ff o u rp a r t s c h a p t e ro n ei n u o d u e e ss o m eb a c k g r o u n d i n f o r m a t i o n c h a p t e rt w oi n v e s t i g a t e ss i n g l ep r o c e s s o rs c h e d u l i n gp r o b l e mm i n i m i z i n g t o t a l c o m p l e t i o n t i m e w i t hg r o u pt e c h n o l o g y , f l o ws h o p s c h e d u l i n gp r o b l e m m m 。m 。l l z m gm a k e s p a nw i t hg r o u pt e c h n o l o g ya n df l o ws h o ps c h e d u l i n gp r o b l e m m m 。l m l z m 。g t o t a lc o m p l e t i o nt i m ew i t hg r o u pt e c h n o l o g y o p t m 咀ls o l u t i o n so f p r o b l e m s1 p 尹b 一叫s i g t e c , f m p = q t 产q = q 口g t , s t c 。缸a f mip = q 乒t # k ，g ，_ g f ，g t , 昂i 白a r eg i v e n s c h e d u l i n gp r o b l e mi ng r o u p p r o c e s s i n gt om i n i m i z em a k e 锄w i t ha na v a i l a b i l i t ye o m a a i n to nas i n g l em a c h i n e1 i 砌2 啪，( b l ，助，g t ，s 卸lg 。c a nb es o l v e du s i n g 也co - li n t e r g e r p r o g r a m m i n gt e c h n i q u e c h a p t e rt h r e ed i s c u s s e sd u ew i n d o ws c h e d u l i n gp r o b l e m 州t l lu i l i f o r mp r o c e s s i n gt i m ef o rs i n g l em a c h i n e t h eo b j e c t i v ef u n c t i o ni st h et o t a lf e e ab r i e fm a t h e m a t i c a lf o r m u l ai so b t a i n e dt os o l v et h ep r o b l e m i nc h a p t e rf o u r , w e s u m m a r i z et h er e s u l t so f t h et h e s i sa n dp u tf o r w a r ds o m ep r o s p e c t k e y w o r d s ：s c h e d u l i n g ，g r o u pt e c h n o l o g y , m a k e s p a n , t o t a lc o m p l e t i o nt i m e ，f l o ws h o p ， d e t e r i o r a t i o no f p r o e e s s i n gt i m e w r i t t e nb y j i n j i s u p e r v i s e db yp r o f w e n - z h e n w d 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文 不含其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏 ：j i 1 大学或其它教育机构的学位证书而使用过的材料。对本文的研究作 出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本 声明的法律责任。 研究生签名：么至：盏日期：兰立：坚：y 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论 文合作部、中国社科院文献信息情报中心有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论 文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的 保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的 全部或部分内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名：今昔日 加工时间恶化的成组加工捧序目置一引言 一引言 1 1 排序问题简介 排序( s c h e d u l i n g ) 问题产生的背景主要是机器制造，后来被生产管理、计算 机系统和运输调度等领域广泛应用。从普通生产部门的计划安捧、人员调度、学 校课程表的制订，到宇宙飞船复杂庞大的飞行计划，都要用到排序的理论和方法。 1 1 1 排序问题的定义 排序问题是一类重要的组合优化问题，它是利用一些处理机( p r o c e s s o r ) 、机器 ( m a c h i n e ) 或资源( r c s o u r ) ，最优地完成给定的任务( t a s k ) 或工件o o b ) 加工执行 任务时需要满足某些限制条件，如工件的就绪时间、完工的限定时间、任务的加 工限定顺序( 如出树等) 、资源对加工时间的影响等。最优地完成是指使得目标函 数达到最小，目标函数通常是对加工时间的长短、处理机的利用率的描述。 1 1 2 排序问题的分类 排序问题按处理机数量的不同，可以分为： 单处理机问题 多处理机问题 多处理机问题又进一步可分为以下几类问题： 同类机( 平行机) 问题 多类机( 车间作业) 问题 柔性流水作业问题 多类机指的是m 个处理机具有不同的功能。在多处理机环境中，被加工的任 务需要在不同的处理机上加工。在这种情况下，把任务( 切s k ) 称为工件或作业( j o h ) 。 设有工件集为j = ，五，以) ，每个工件巧有吩道工序( 0 1 ) e r a t i o n ) 勘， 咖，工序指的是某工件在某处理机上被加工的这部分子任务。 如果每个工件需要在每个处理机上加工，即，旷m ，j = 1 ，2 ，n ，每个工件 在各机上的工序顺序固定且相同，并且每台处理机上工件的加工顺序也相同，则 把这种多类机的环境称为流水作业( f l o ws h o p ) 或同顺序作业 加工时间恶化的成组加工捧序问蘑 = ! 堕 每个工件有自己固定的加工顺序， 如果每个工件需要在每台处理机上加工， 称这种环境为异顺序作业( j o bs h o p ) 如果每个工件需要在每个处理机上加工，每个工件可按任意顺序加工，把这 种环境称为自由作业或开放作业( o p 皿s h o p ) 。 1 1 3 捧序问题常用符号 下面对排序问题的常用符号作一简要说明： p 第- ，个工件 万一工件七的加工时间 一工件占的优先因子( 权) 0 一工件巧的完工时问 g d 最大完工时间或时间表长 矗研台处理机的流水作业 o | 广1 ，l 台处理杌的自由作业 1 1 4 排序问题的目标函数 对于工件 ，1 2 ，厶来说，如果它们对应的优先因子分别为w i ，w 2 ， 完工时间分别为c l ，c 2 ，g ，那么常用的最优准则有： 时间表长，即r a i nm a x g ) j s g 加权总完工时间，即历加白 i - i i 1 5 摊序问题的三参数表示 1 9 7 9 年g r a h a m , l a w l e r , l e n s t r 和r i r m o o yk a n 等人提出用三参数来表示。三参 数记号由三个域组成：al ，lj ，。它们具有下面的含义。 口域表示处理机的数量、类型和环境，它可以为 l ：单处理机 ，_ ：研个同速机 q _ ：册个恒速机 2 加工时间恶化的成组加工排序问置一引言 ：m 个变速机 凡：m 个处理机，流水作业 0 二：脚个处理机，自由作业 厶：用个处理机，异顺序作业 p 域表示任务的性质、加工要求和限制。可能的项主要有 ，：任务另的到达时间 p r m p ：加工可中断 卵，c h a i r 船，i n t r e e ，o u t t r e p ：分别表示一般有序约束，链约束，入树和 出树 b r k d w m 机器故障( b r e a k d o w n s ) 表示机器不能连续被使用 任何约束条件的项都可以出现在口域中，同时可以出现多项。若出现两项或 两项以上， 两项之间要用逗点隔开另有一些项比较复杂会在有关章节使用它们时再做解释。 g 域表示要优化的目标函数，它可以是 c 二讲时间表长 q ，q ：总完工时间，加权总完工时间 厶。：最大延误 马，w j d j ：总误工，加权总误工 e w j q ：误工任务数，加权总误工任务数 1 1 6 排序问题的求解 捧序问题是一类重要的组合最优化问题。由于排序问题中的处理机、任务或 工件都是有限的，排序问题求解就是从有限个可行解中找出一个最优解，使目标 函数达到极小在排序问题中，把可行解称为可行排序( f e a s i b l es c h e d u l i n g ) ，最优 解称为最优排序( o p t i m a ls c h e d u l i n g ) 。求解排序问题的基本思路是：应用或借鉴求 解其他组合优化问题的方法，充分利用排序问题本身的特殊性质，确定满足约束 条件的最优排序。有些排序问题可直接转化成其他的组合优化问题求解。对具有 多项式时间算法的排序问题，要尽可能地找出空间复杂性和时间复杂性好的算法。 所谓空间复杂性是指算法所占存储的多少，时间复杂性指的是计算时间的长短， 加工时间恶化的成组加工捧序问恿一引言 它们都是输入规模的函数。 对于一个排序问题，首先要用复杂性理论对它进行分析，看它是属于p 问题 还是n p 一难问题，以便知道求解此问题的难度若它是p 问题，则求解此类问题 就是寻找计算量尽可能小的多项式时间算法；若它是n p 一难问题，则大致有两种 基本方法：一是用分枝定界法、动态规划法等巧妙的枚举来求出它的最优排序。 这类算法计算量大，只能对规模较小的问题才是可行的；另一种方法是求出它的 近似最优捧序，各种局部搜索法和启发式算法，分析误差是使用这类方法不可缺 少的工作，也是最困难的工作。这类算法计算量小，并能满足一定的实际需要。 对于尚不知是否存在多项式时间算法的排序问题，也可用启发式算法得到近似最 优排序或针对它的一些特殊情形设计最优算法。 1 2 论文各部分的主要内容 第二章分别讨论了一类工件的加工时间随开工时间线性增加的单机成组排 序总完工时间问题ll 胪6 和琦，s ，g ti c i ，一类工件的加工时间随开工时 问线性增加的成组加工流水作业问题，目标函数分别是时间表长和总完工时间： f m p 乒= q t f k q c k = q ，g t ，s l c 一，f m p i l = q t ，q l = q g t , s i c h 。 此外，还讨论了机器使用时间受限的单机线性恶化成组排序问题llp c = c b j t f ，( b l ， 助，g t , s , = oig 。对前两个问题都给出了求解最优解的多项式时间算法；对第 三个问题，将它转化为了0 1 整数规划问题。 第三章讨论了工件具有相同加工时间和相同窗口交货期的e t 调度问题， 给出了简洁的数学模型和计算公式。 第四章对论文的总结以及今后研究工作的展望。 4 加工时间恶化的成组加工捧序目题二工件加工时间依籁开工时间的成组捶序问题 二工件加工时间依赖开工时间的成组排序问题 2 1 工时随开工时间线性增加的单机成组加工问题 b m 帅e ，s 讨论了捧序问题li p ，= 矽+ 甜i g 。：假定，若工件j 在时刻r 开 始加工，则工件f 的加工时间胁= + r o t ；排序的目的是极小化时间表长。并指 出，最优排序的条件是工件的加工顺序依p j 口a j 的非降序1 。m o s h e i o v , g 讨论了 工件加工时间是开工时间的简单线性增加函数，即若工件f 在时刻t 开始加工， 则它的加工时间是研= 甜( 口 0 ) 的单机排序问题。并证明了相应的时间表长问 题( c _ 。) 、总完工时间问题( q ) 、最大延误问题( z _ 。) 以及延误工件数问题 ( 奶) 均是多项式时间可解的“”。张峰讨论了工件加工时间是开工时间的简单 线性增加函数的单机成组加工时间表长问题，即工件- 在时刻t 开始加工的加 工时间p c = a c t 且离岛，并给出t - r 件的最优加工顺序”程明宝研究了工件加工 时间是开工时间的线性增加函数的单机成组加工时间表长问题，即llp l = l + 6 西 西，g tig 。，并给出了工件的最优加工顺序”。赵又里讨论了比文 5 更一般条 件的排序问题，即li 胪6 巾，s ，g tig 。，也给出t - r 件的最优加工顺序嘲。 秦仁杰研究了工件加工时间是开工时间的相同斜率的线性增加函数的单机 总完工时间问题，即1ip p b + a ti g ，并证明了工件按目非降序加工目标函数 最优嗍。本文在文 6 问题的基础上，增加成组加工的条件，考虑问题llp l = b c + a t ， 西，g tl o ：设有m 组工件需要在同一台机器上加工；第f 组工件中有n ，个工 件，m 组工件共有个工件，n = ”l + ，矿+ ；g t 表示成组技术( g r o u p t e c h n o l o g y ) ，它要求同组内的工件必须在机器上连续加工，不可拆散加工，也不 可被别组工件插入加工；第i 组工件中的第，个工件由的加工时间肋满足所= b f + 口咖其中白为工件西开始加工的时间，j = 1 ，2 ，m ，j = l ，2 ，胁，口为常 数；加工第f 组工件之前需要一个安装调整时间s 。排序的目标是使总完工时间 最小。即本文要讨论的是，工件加工时间是开工时间的相同斜率的线性增加函数 的单机成组加工总完工时间问题。 设石= ( 。，j 1 2 ， j i ，2 l ，砘，m l ) 是工件的一个加工顺序，并 且我们已经对工件进行了重新编号，其中西表示第f 组工件中的第，个工件。下 面给出每个工件的加工时间p f 和完工时间白的表达式： 垫三堕旦墅些塑壁丝塑三茎堡旦星 三三壁塑三堕旦竺璺互三堕旦盟堕塑堡壁塑垦 第1 组工件： p 1 1 = b l i + 磷， p 1 2 = 6 1 2 + 甙- s + p l ，) = b 1 2 + a b i i + a ( a + 1 ) 墨， p l = b n + 口6 l 一l + 口( 4 + 1 ) “ 一2 + + 口( 口+ 1 ) 一2 b o l + 口( 口+ 1 ) 一1 墨； c l l = 墨+ p 1 1 = b l l + 0 + 1 蜗 气：窆( 口+ 1 ) “- k , b 。 + ( 口+ 1 y s , ，( 1 s 啊) 一l 第2 组工件： 见l = l + “q i + 是) = 屯i + 口c l + 码 p 2 甩= 6 2 2 + 口6 j 一2 一i + a ( a + 1 ) b 2 月：2 + 。一+ 口( 4 + l 户一1 g + 口0 + l 户1 岛 c 2 i = c 1 一i + 岛+ 见i = b 2 l + + 1 ) c 1 + 0 + 1 ) 是 c 2 。 = 芝：( 口+ 1 ) 一与6 2 + ( 口+ 1 ) 。2 c i + ( 口+ 1 ) 是，( 1 s 五s ，) t 2 - i 第m 组工件 p 。j = 6 坩，1 + 口c - i ，_ + 凸晶 p 。 = 虬 + 口k ，一l + 口( 口+ l 地- 2 + c - _ j ：k ，l + ( 口+ 1 ) c _ - i 一+ ( 口+ 1 ) 墨 + 口( 口+ 1 ) 一l c 0 l 。+ 口( 口+ 1 ) 一_ 一& j 。 c _ = ( 口+ 1 p 4 。6 _ 厶+ o + 1 ) 厶c _ 山。+ ( a + 1 ) l 墨，( 1 l ) i - 1 6 加工时间恶化的成组加工排序问题 二工件加工时问依赣开工时问的成组捧序问题 于是，总完工时间c i ： ：c ；= c l l + c 1 2 + + c i + c 2 l + + c 2 + + g j + + c ： = 艺宝( 口+ 1 ) “响6 l + 窆( 口+ 1 ) 墨+ 主宝( 口+ 1 ) n b 6 ；b + 主( 口+ 1 ) n 是 + 芝( 口+ 1 ) 艺量+ 1 产一i - jm 屯l m l c l - i - , - i - + 芝( 口+ 1 y - z + 芝 + 1 ) “q 吐铀 令d = 意芝。+ 1 ) “呐岛 ，4 ：窆( 口+ 1 ) 一呐，b s ：壹( 口+ 1 ) “墨，f ：l ，2 ，研 贝 。1 与。1 1 1 1 1 c i = + 0 + 1 ) “墨 g ：j ( 口+ 1 ) n j - + n l - 委4 + 壹+ 1 ) 一+ ”嘶_ ，o s j 呐 f = li - i q = 喜4 + 喜尽+ 喜鱼兰生二詈坞+ 喜鱼生坐= 气；垒兰旦鼍 = ( 杰d ) + ( 至驴崖绁芝掣( 4 俐+ ( m - l 掣岛) + ( 册_ 1 ) i - it = lj = l u - 。l a 在上式中，第二项、第四项与第五项都是常数，第一项仅与组内排序有关， 文由 6 知，组内按非降顺序捧列，第三项与组间排序有关。由于第三项的系 数鱼! 竺：二竺：l 二鱼1 2 随础目加而减小， 口 排列 从而得到下面最优排序的定理 故组间按a i + s o = 1 , 2 ，m ) 非降顺序 定理组内按6 p 非降顺序排列，组间按4 + s ( f = l ，2 ，m ；i = 1 2 ，啊) 非降顺 序排列，可得问题1 l 助= b e + 讲，墨，g ，i q 的最优排序。 7 加工时间恶化的成组加工排序问愿二工件加工时间依赖开工时间的成组捧序问题 2 2 工时随开工时间线性增加的成组加工流水作业问题 文献 3 】、 1 1 、 1 2 讨论了不同形式的线性恶化函数的确定性单机调度问题。 文献 4 6 讨论了不同形式的线性恶化函数的单机成组加工问题，文献 1 3 对两 台机流水作业问题进行了讨论。赵传立等在文献 7 中讨论了简单线性恶化函数的 系数与机器无关情况下的m 台机流水作业问题。 本文将分别讨论目标函数为时间表长c 。以及总完工时问g ，恶化函数为 = 矿矿且g ，呷f 的成组加工流水作业问题，即问题砌i = q c k 矿g ，= 孙g z 昂ic k ，与问题f mi 印i v ，g ，= 缈g t , 西i 白。其中表示第f 组中 第，个工件在第k 台机上的加工时间，g ，是第f 组中第，个工件在第k 台机上加 工时间的系数；矿是第f 组中第_ ，个工件在机器k _ h 的开始加工的时间，f = l ，2 ， f , j = l ，2 ，mk = 1 ，2 ，肌。 设有f 组工件，第f 组中有工件( 厶，以) ，f = 1 ，2 ，凡所有工件依 同一顺序在m 台机器上加工，不妨设该顺序就是机器m ，机器m 2 ，机器 腻。，且要求在各机器上工件的加工顺序完全相同；成组技术( g r o u pt e c h n o l o g y ) 限定一组一组加工，同组工件不可拆散分开加工总假定首个工件在给定的时刻 t o ( t o o ) 开始加工，工件由在机器七上的加工时间为= q 矿，f = l ，2 ，e ，= 1 ，2 ，开 k = l ，2 ，m ，矿是工件西在机器k 上开始加工的时间。记c i 为工 件由在最后一台机 厶上的完工时问。排序的目的是使时间表长g 。= m 积 c d i = 1 , 2 ，f , j = l ，2 ，一，) 及总完工时间o 达到最小。 2 2 问题f mi = g 尉，g ，= 的，g t , 西lc k 的求解 ( 1 ) f 司mf mi = g v ，g 广= g ，g t , s = oig 。，工件组之间没有调整时间 的情况 引理1 m 对于问题f mi 助= 口而，口f = 吩ic 。，其中吩表示工件每在机器i 上加工时间的系数，设首个工件的开始加工时间为t o ( ，p o ) ，记m = 如f 吩) ， 那么时间表长c j 。与工件的加工顺序无关，并且g 。= t o ( 1 + 4 圹。1 兀( 1 + q ) 。 j ；l 对于问题f ml p ，= g ，矿，g ，= 盼，g t ，昌= olg 。，由引理1 知，时间 8 加工时间恶化的成组加工捧序问题 二工件加工时问依赖开工时间的成组排序问题 表长c ，一与组内工件的加工顺序无关- 下面确定组问加工顺序c j ，是第，组工 件的完工时间。 令局2 ( 1 + 吼 广1 珥( 1 + 劫，其中吼 2 踹 g f ，卢1 ，2 ， 由引理1 ：q = t o o + q , ) 剃兀( 1 + q v ) = t o a i ， c i 2 c f - l , l 4 ( q i , ) + i i - d i ( 1 + q 茹2 c ，4 呐妒t 甜i a 2 由 m c f + l , n 1 4 1 = c ，一( 1 + 以+ i m ) 剃兀( 1 + q f + u ) 2 c ，一，a f + l = i o a i a 2 缸l j - i c ，加= c f i 帕( 1 + 靠山) + 忏i - i ( 1 + 靠j ) = c ，i m a ，= t o a l 一2 ”_ ， 1 - 1 交换任意相邻两组工件第，组与第p 1 组顺序( 1 ，只1 ) ，得 c f + l , n i + l t = c f _ i 打( 1 + q + 。，) ”1 f i ( 1 + 竹+ u ) = c f 。 。4 一l - i 2 卅一2 ”啤l 竹l c ，竹= c ，岫。( 1 + 乃，) 一- 矗( 1 + ) = c ，+ 。m 4 j - i 2 缸i i a 2 “4 f 咖l 母 即c ，一，2c 蚋，所以交换任意相邻两组工件顺序后不改变时间表长c l t 定理1 对于问题f mi = g f ，g ，= 的，g t , s = oig 。，时间表长g 。 与组内工件加工顺序无关，也与组间工件加工顺序无关，且c k 产t o a i 一2 a 几 ( 2 ) 问题f mlp o t = g i v ，q ，= 的，g t , s = 岛ic k 。，各组之间调整时间相等的情 况 9 加工时问恶化的成组加工捧序问置二工件加工时间依赣开工时间的成组捧序问题 c 1 = ( ，o + 蜀x 1 + 吼 ) 剃兀( 1 + q t j ) = ( f o + 西m l g - i j c k = ( c i + s 2 x l + q z ) 剃兀( 1 + q 2 ，) = 【( ，o + 两m l + 2 铂+ 西m 一2 + s 2 a 2 月， c r 鼍c f - h + s f ) o + q f l r ) ”lh ( 1 + q s ) j - l 。( ，0 + 岛州一2 ”a + s u l 卅3 4 厂+ s 姐一4 ”4 厂+ 一斗写由 c l m 啪埚m 一2 a f + , + s 2 a 2 a 3 - a + l + s 3 a 3 a ( 4 ，+ l + 。+ 即，+ i + 跏i 爿f + i g 一，= ( f o + 岛m l 一2 _ 删卅3 a # s 3 a 3 a 4 ，+ 惦叫， 交换任意的相邻两组第厂组与第p 1 组顺序( 1 ，只1 ) ，得 c f + l 2 ( c ，一l m + 卧1 ) 厶i 气郴l m l 4 1 4 产l 蟠钮2 ”母1 4 产1 + + 霉1 母1 4 产i + s j q - l a f i i ， c ，竹气c _ ，+ l m 蝎州只旬埚m l 厶i + 跗2 咖i + s 3 a 3 厶1 + + 母i 母1 4 ，争l 蟠弘厂h 黔1 4 户蜘i g m 啪+ 岛m t a f + 2 a 2 a r v + 母1 4 l 一跚一一2 a f + s f + i a f 4 f + i a ，+ + s 耳a r c ， 。c f = s g g + 卅z + s 小。与砂”一趴1 4 ，纺1 卸一蹄1 以1 一 a t 2 母l 办办3 一_ ，- s + 咖l a 刚- a # ) s o f + 2 ” a t ， 那么，c ；。g 。 1 0 的充要条件是护竹l 定理2 对于问题f mi p 矿= g i v ，g 上= 的，g t ，s = 岛ig 。，时间表长g 。 与组内工件加工顺序无关，组间工件按a 递减顺序加工可得最短时间表长。 1 0 加工时间恶化的成组加工捧序问题二工件加工时间依耪开工时间的成组丰| 序问题 2 2 2 问题f mi 印，q c k = q ，g t 岛i c 定理3 对于问题f m l = 窖g v ，g ，= 的，g t , 昌i q ，组内工件按q f 递增( s p t ) 顺序加工，组间工件按s 递增顺序加工可得最小总完工时间。 证明：由文 7 】知组内工件按的的s p t 序加工最优，因而只要证明组问工件 的加工顺序即可 不妨设最优调度为j r = ( 。，z ，厶，厶，j 砘，山- ，以。) ， - i 令三仁【( 1 + g n ) ”h l + g j 2 ) _ ( 1 + 毋l 卜h l + 吼 厂兀( 1 + 劬) 】，则 - i 第1 组中工件的完工时间为： c l l 啪+ $ 1 x l + q l , 尸 c l 2 5 ( 如+ s l x l + 吼 ) 。兀( 1 + 吼，) 2 ( r o + s i m l j - i 令q l = 窆c l 啪+ 禺) “l + 尸h 1 + q 1 2 ：( 1 + q 1 0 + 1 - 1 月h l h l + 叮h 广兀( 1 + 吼川2 m + 岛) d l - 第2 组工件中工件的完工时间为： c 2 l = ( c 1 喝) ( 1 + q 2 l 尸 m 2 - i c 2 气c 1 1 坞) ( 1 + 9 2 尸兀( 1 + 9 2 ) 2 ( c 】 + s 2 ) a ：( t o + s , ) a , a 2 + s 弘2 ，- l 令q = 窆c 2 ，气c l ，+ 岛j 【( 1 + q 2 。) 胛卜+ ( 1 + 9 2 。尸矗( 1 + g ：，) 】气c 1 + 岛) d 2 a l j - ； = ( r 0 + 两m l 仍+ d 2 第厂组工件中工件的完工时间为： 嘞气c ，讥。+ 与( 1 + 哩，1 ) _ - 加工时问恶化的成组加工捧序问题 二工件加工时间依赣开工时间的成组排序问题 _ ，一i c ，竹2 ( c m + 动( 1 + 办，广兀( 1 + ) 2 ( q 一。m 蝎玢 令鲈量巳气c ，一啪 邓o + 禺) a i ” a i d d - s z a 2 ”母i 上犷坶1 4 l 巧蝎巧 第，组工件： q i 气c n m + s v x l + q f , 0 o 一，气c f i m ( 1 + g n ，广兀( 1 + q r ，) = ( c 。m 坶弘， 令妒艺c ，气c 山。+ s f ) d r j i i 气，o + 两) a i ” a f i d f + s 2 a 2 ”一b l p 一+ s f i a f - i d f + s f d f 于是 e c # = ( c n + c n + ”叶c i ) h c 2 l + ”呻c k 卜+ ( c e l + + g ) = q t 2 ( d l 十彳l z ) 2 + + a i 。a f i d f x t o + s i ) + ( 仍+ 一2 岛+ 斗爿2 ” a f - i d r ) s 2 + + ( d f i + a f i d f ) s f i + d 耳q f 由爿， l ，d i l ( i = 1 ，2 ，) 可知s 的系数不增，于是组间按& 不减的顺序 加工，可得最优解。即定理得证 加工时间恶化的成组加工排序问愿二工件加工时间依耪开工时问的成组捧序问题 2 3 机器使用时间受限的单机线性恶化成组排序问题 m o s h e i o v , g 对工件加工时间是开工时间的简单线性恶化函数的单机排序问 题进行了研究“4 张峰讨论了工件加工时间是开工时间的简单线性恶化函数的单 机成组摔序问题。l e e 对机器带可用时问限制的加工时间恶化问题分别研究了单 机和平行机问题【“1 c h i n c h i aw u , w e n - c t 6 u n gl e e 讨论了机器带可用时间限制的 单机加工时间恶化问题o ”本文对机器带可用时问限制的单机加工时间恶化的成 组问题进行了讨论，把该问题转化为o 1 整数规划问题。 设有工件集，其中有m 组工件，需要在一台机器上加工；第f 组工件中有m 个工件，m 组共有以个工件，万；胁+ n 2 + + ；g t 表示成组技术( c 椭u p t e c h n o l o g y ) ，它要求同组内的工件必须在机器上连续加工，即不可拆散加工，也 不可被别组工件插入加工；第f 组工件中的第，个工件由的加工时间所满足砌 - - a d ，其中白为工件由开始加工的时间，净1 , 2 ，川，= 1 2 ，朋，机器上 首个工件的开始加工时间为t o ( t o 0 ) ，组与组之间的安装调整时间s 卸。假定机 器在时间段( 6 l ，6 2 ) 内不可用( 0 b l 6 2 ) ，并假定：若某工件由在时刻白( 0 t u 6 1 ) 开始加工且加工至时刻b l p l o ) 。 - l 引理2 啪对于问题1i 砌= 啪，g t , 昌喝ig 。，令a j = n ( 1 + 嘞) ， - i 卢1 2 ，册。如果组与组之间按a ，单调递减序加工，则得到最优排序。 设石2 l ，j z 2 ，j i ，止j ，砘，厶l ，以 ) 是一个给定的工件加 m 。 工顺序，令a j = 兀( 1 + 口口) ，i = i ，2 ，肼，那么 j - i 加工时间恶化的成组加工捧序问露二工件加工时间依赣开工时间的成组排序问题 第1 组中工件的完工时间分别是： m c n = t o + p u = t o + c t l l t o = ( 1 + c t n ) t o , ，= 兀( 1 + q j ) t o = a i t o - l 第i 组中工件的完工时间分别是： c f l 2 q 一1 山+ 嘶lc j i 2 ( 1 + a h ) c o l _ ， k “= 兀( 1 + ) c f 咖。= a i a 2 ” a u l t o 兀( 1 + ) j = l 1 = 1 下面分两种情形讨论。 情形1 若第f 组中第七个工件的完工时间恰好等于b l ，即 i q = a i a 2 ” a u l t o 兀( 1 + ) = b t ，则 j 1 第i 组中第n 1 个工件的加工时间为p 伊l = a t h l 幻，相应的完工时间为 c k + l - c 一仇h l h 6 2 一巩) = ( 1 + 瓯h 1 ) 6 2 c m = q h l + p 脚2 = ( 1 + 瓯h l x l + 啦h 2 ) 幻， c = 6 2 兀( 1 + ) j - k + l 第什l 组工件的完工时间分别是： c f + l 1 2 c j 协l ，j c 1 + 啪，1 ) 6 2 四竹小， t + i l l q 岫。= 兀( 1 + q w ) 兀( 1 + ) b 2 = a h lb 2 兀( 1 + ) j l ij - k + lj = k + l 第，( 斗2 ，神组工件： 嘞2 c ，山，。+ 嘞c ，山，2 ( 1 + 鳓) 啤l6 2 j i 。- i + ( 1 + a f ) m c ，竹= a e q 母6 2 兀( 1 + 嘞) j - k + l t 注意到兀( 1 + 嘞) ：兀( 1 + ) 兀( 1 + ) = a i a ，, a o b l = k + l，- l产l 1 4 加工时同恶化的成组加工捧序问置= 工件加工时间依赖开工时间的成组捧序问题 则g 。= 彳h j ”叫。b 2 a i a 2 一向b l = a j a 2 a 小如b l 是个常量 定理1 若第f 组中第七个工件的完工时间c k = a i a 2 a l - l t o 兀( 1 + ) = b l ， j - i 则问题li 肋：c t o ，0 ，( 6 l ，蚴，g t 3 r - - oig 。等价于解方程窆口，_ ：口，其中毋： j = l 坝l + a o ) ，x f o ，l ，o = l n b , u i a 2 以l 如) 】，卢l 2 ，m ，即确定b l 时刻前完成加 工的卜1 组工件，中断加工的第f 组工件以及b l 时刻前完成加工的第i 组中的k 个 工件。 情形2 若第f 组中第七个工件的完工时间c k = 一l 彳2 ” a l t o 兀( 1 + a o ) b l 由于第i 组中第k + 1 个工件的加工时间p i p l _ 瓯h i c k ，则相应的完工时间分 别为： k + l q h l = c 止+ a ，+ , + ( b z - b o = a 1 a 2 ”_ i t o 丌( 1 + 嘞) h 6 2 一b 1 ) k + 2 q h j = q + 凡i + 2 = 彳一2 ” a “t o 兀( 1 + 嘞) h 幻一b 1 ) ( 1 + 啦i + 2 ) j - 1 2 彳鼢叫舻阢6 1 ) m 1 - 。i ( 1 + a f ) 第什l 组工件： c i + l ，1 。c + 嘶l ，l g 2 ( 1 + 鲰1 0 a , a 2 一而h l + l ，1 ) 他b 1 ) 兀( 1 + c t f ) 1 - * + z f c ：+ i 。= _ l 彳2 a t + l r o + 一h l ( 幻6 1 ) r i ( 1 + 口口) j - k + 2 第肌组工件： 加工时间恶化的成组加工捧序问题 二工件加工时问依赖开工时问的成组排序问题 g 1 2 c - 一i 山+ l q l m2 ( 1 + 1 ) 一l 彳一l ”( 1 + 1 ) 渤- 加) 兀( 1 + 唧) j - k + 2 c _ a i 叫m t o + a h l 厶池一b o 兀( 1 + 口) j f k + 2 注意到公式( 2 ) 中，一l ，“一如，6 2 幽，都是常数，因而只要 。 爿州”- a ii ( 1 + ) 极小，目标函数g 。就最优。 j - k + 2 h+ i 由于兀( 1 + ) = 兀( 1 + 嘞) 1 1 ( 1 + ) = a i a 2 ”叫而【c k ( 1 + n h 1 ) 】 j - k + 2j - i1 - i m 贝j j - i + l - 4 _ r i ( 1 + ) = 彳l _ 历t o 【c k ( 1 + c k + 1 ) 】 j - k + 2 另一方面，一 1 叫，兀o + 口f ) 极小要求一h l ，一为a l ，a ，中的m - i j - k + 2 个较小者。于是我们得到如下结论。 定理2 若第i 组中第七个工件的完工时间c k = a i a 2 a f - i t o 兀( 1 + ) 籼， 则嘶l - 硪 a 对ii = 1 , 2 ，m ；j = l ，2 ，”。) ，a l ，a 。中聊i 个较小的工件 组在6 2 时刻后加工，记这m - i 个工件组为，。于是问题lip c = d 锄，p l ， 蚴，g t , s , - - oig 。等价为o - l 整数规划问题 m a x i m i z e z = q _ 1 j 让“ s ly口工， 口 凡l 篇i “ 其中毋= 坝l + a 砂，刁= 0 ，1 ，e = i n b l a 一2 a l ，0 ) 】，i j j 。 1 6 加工时阃恶化的成组加工捧序问题三工件具有相同加工时间和相同窗口交货期的单机盯调度问题 三工件具有相同加工时间和相同窗口交货期的 单机e t 排序问题 对于工件具有相同的窗e l 交货期m ，蝴，目标函数为如下总费用函数 f = m i n 粥一o + a q 一勘) ( 1 ) 的单机e t 调度问题，李忠义和k r a m c r 给出了多项式时间的计算方法“1 然而， 在这种单机调度问题中当所有工件的加工时间都相同的时候，如果仍然用他们所 给的算法来求解就显得比较麻烦。本文针对这种特殊情况，给出了一个求得对应 单机调度问题最优解的简洁的数学模型及计算公式。 设有_ ，个工件须要在一台机上加工；每个工件的加工时间相同，均为p j = p ( 常 数) ；每个工件具有相同的窗口交货期m ，蝴，其中，窗口交货期的长度d = , 2 一函 是给定的常数。若一个工件的完工时间落在窗口交货期哺，瑚内，则该工件没有 额外费用；若一个工件在函之前完工，则该工件每提前一个单位时间完工，有口单 位的额外费用；若一个工件在杰之后完工，则该工件每推迟一个单位时间完工， 有声单位的额外费用。那么，对于任一给定的调度( 排序) 方案，按工件的完工 时间可将工件集合划分为三个子集：过早完工工件集合，窗口完工工件集合，延误 完工工件集合，分别记它们为e = ( _ ，l g , 2 ) ，其中0 是工件，的完工时间这里调度问题的目的是选择适当的调度( 捧 序) 方案，即择适当的加工时间表( 包括窗口交货期的位置) ，来极小化由上述式 ( 1 ) 所示的总费用函数。 对于上述的调度问题，我们讨论两种情行： 问题( 一) 而为决策变量； 问题( 二) 函为给定的常数( 非决策变量) 。 ( 1 ) 函为决策变量 由于函为决策变量，故第一个开始加工的工件可以从零时刻开始，并且让所 有工件不间断地接连加工( 即机器上没有空闲时间。因此调度的目的变为，只要 确定西的合适位置，使总费用最小。总