（概率论与数理统计专业论文）几类加工时间与环境有关的排序问题.pdf

几类加t 时间与环境有关的排序问题中文摘要 中文摘要 排序问题是一类重要的组合最优化问题。本文包括六个部分： 第一章序言，介绍排序问题的一些背景知识。 第二章讨论流水作业加权总完工时间问题中加工时间受资源影响的资源分配 问题：eic h a i n ，仍j = 如一口：心，鸬万i q 给出了求问题最优解的多项 j = lj - - l 式时间算法。 第三章研究具有学习和恶化效应的单机排序问题：工件的加工时间是工件开 工时间和工件加工位置的函数：办( f ) = p f l t ) r ；分别对目标函数是时间表长、总完 工时间、完工时间平方和的问题给出了多项式时间算法。 第四章研究一类具有学习效应的单机成组排序问题：工件在组内具有与位置 有关的学习效应；不同的工件组具有不同的学习因子；分别对目标函数是时间表 长和总完工时间的情况进行讨论，证明它们多项式时间可解。 第五章讨论单机上工件的加工时间同时依赖于开工时间和所分配的资源量的 排序问题；极小化的目标是时间表长与资源费用之和：ll 历= 糸一咖lc 缸+ 颤“) ； 给出了多项式时间算法。 第六章对论文的总结以及今后研究工作的展望。 关键词：运筹学，排序，加工时间，时间表长，学习效应 作者：王官龙 指导教师：闻振卫 几类加工时间与环境有关的排序问题 英文摘要 s o m es c h e d u l i n gp r o b l e m sw i t he n v i r o n m e n t d e p e n d e n tp r o c e s s i n gt i m e s a b s t r a c t s c h e d u l i n gp r o b l e mi so n eo ft h ei m p o r t a n tc o m b i n a t i o n a lo p t i m i z a t i o np r o b l e m s t h i st h e s i sc o n s i s t so fs i xp a r t s ： c h a p t e ro n e ：i n t r o d u c es o m eb a c k g r o u n di n f o r m a t i o no ft h es c h e d u l i n gp r o b l e m c h a p t e rt w o ：d i s c u s st h ef l o w - s h o ps c h e d u l i n gp r o b l e mw i t hr e s o u r c ed e p e n d e n t p r o c e s s i n gt i m e s t h eo b j e c t i v ef u n c t i o ni st om i n i m i z et h et o t a lw e i g h t e dc o m p l e t i o n t i m e c h a p t e rt h r e e ：i n v e s t i g a t e ss i n g l e m a c h i n es c h e d u l i n gp r o b l e m sw i t hl e a r n i n g e f f e c ta n dd e t e r i o r a t i o n t h eo b j e c t i v ef u n c t i o ni sr e s p e c t i v e l yt h em a k e s p a n ，t h et o t a l c o m p l e t i o nt i m ea n d t h et o t a ls q u a r eo fc o m p l e t i o nt i m e c h a p t e rf o u r ：s t u d yt h ep r o b l e mo fs i n g l em a c h i n eg r o u ps c h e d u l i n gw i t hl e a r n i n g e f f e c t t h ej o b si nt h eg r o u ph a v et h ep o s i t i o n - b a s e dl e a r n i n ge f f e c t s d i f f e r e n tg r o u p s h a v et h ed i f f e r e n tl e a r n i n gf a c t o r s t h eo b j e c t i v e so ft h es c h e d u l i n gp r o b l e m sa r e r e s p e c t i v e l yt om i n i m i z et h em a k e s p a na n dt h et o t a lc o m p l e t i o nt i m e i ti sp r o v e dt h a t b o t ho ft h e mc a nb es o l v e db yp o l y n o m i a lt i m ea l g o r i t h m s c h a p t e rf i v e ：d i s c u s ss i n g l em a c h i n es c h e d u l i n gp r o b l e mw i t hp r o c e s s i n gt i m e d e p e n d i n g o nt h ea l l o c a t i o no fr e s o u r c ea n di t ss t a r tt i m e c h a p t e rs i x ：w eg i v es u m m a r yo f t h et h e s i s ，a sw e l la sf u t u r ep r o s p e c t sf o rf u r t h e r r e s e a r c hw o r k k e y w o r d s ：o p e r a t i o n sr e s e a r c h ，s c h e d u l i n g ，p r o c e s s i n gt i m e ，m a k e s p a n ， l e a r n i n ge f f e c t w r i t t e nb y ：w a n gg u a n l o n g s u p e r v i s e db y ：w e nz h e n w e i u 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文 不含其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏 州大学或其它教育机构的学位证书而使用过的材料。对本文的研究作 出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本 声县目的法律责任。 研究生签名：墨室垄 e t 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论 文合作部、中国社科院文献信息情报中心有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论 文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的 保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的 全部或部分内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名：圭室墨日期：之芝兰2 导师签名：日期：噬呈：竺矿 几类加工时间与环境有关的排序问题第一章序言 第一章序言 1 1 背景 排序( s c h e d u l i n g ) i n 题是一类重要的组合最优化问题，它产生的背景早期是机 器制造，后来被广泛用于计算机系统，运输调度，生产管理等领域。事实上，排 序问题在编制作业计划，企业管理，航空航天，医疗卫生等各个领域都有着广泛 的应用。它是利用一些处理机或机器以及可能的资源，最优地完成一些给定的任 务或工件，在处理这些任务( 或工件) 时还需满足某些限制条件，如任务可以有就绪 时间，完工可以有时限，任务的加工可以有顺序关系( 如出树等) ，加工时间可以受 资源的影响等。最优地完成是指使目标函数达到最小。目标函数通常是对加工时 间的长短，处理机的利用率等的描述。 1 2 常用记号 排序理论中常用g r a h a m 等人【1 3 】首先使用的三元组来描述排序问题。三元组记 号由三个域组成伐lpi 丫i 它们具有一下含意： o c 域表示处理机的数量、类型和环境，它可以取： 1 ：单处理机 p m ：m 台同速机 q m ：m 台恒速机 r m ：m 台变速机 f m ：m 台处理机流水作业 o m ：m 台处理机自由作业( 或开放作业) j m ：m 台处理机异顺序作业 f f 。：s 种处理机柔性流水作业 p 域表示任务的性质，工件加工的要求或限制，资源对加工的影响等约束条 件。它同时可以包含很多项，可能的项包括： 厂，：工件有不同的就绪时间 毋：表示在任务历的安装时间 几类加t 时问与环境自关的排序问题第一章序言 g t 表示成组技术 懒表示要优化的目标函数，它可以是： g 戡：时间表长或最大完工时间 g ，0 ：总完工时间，加权总完工时间 五m 稚： 最大延误 e d j ，z w j d j ： 总误工，加权总误工 奶，坳：误工工件数，加权总误工工件数 1 3 排序问题的求解 排序问题是一类重要的组合最优化闻题。由于排序问题中的处理机、任务或 工件都是有限的，排序问题求解就是从有限个可行解中找出一个最优解，使目标 函数达到极小。在排序问题中，把可行解称为可行排序( 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 4 论文各部分的主要内容 第二章讨论流水 乍业加权总完工时间闻题中加工时闻受资源影响的资源分配 问题：互i c h a i n ，岛= 乞，一吃，鹧，恐瓦| 0 给出了求闻题最优解的多项 2 几类加工时间与环境有关的排序问题第一章序言 式时间算法。 第三章研究具有学习和恶化效应的单机排序问题：工件的加工时间是工件开 工时间和工件加工位置的函数：p j r ( o = 以，) 尸；分别对目标函数是时间表长、总完 工时间、完工时间平方和的问题给出了多项式时间算法。 第四章研究一类具有学习效应的单机成组排序问题：工件在组内具有与位置 有关的学习效应；不同的工件组具有不同的学习因子；分别对目标函数是时间表 长和总完工时间的情况进行讨论，并证明他们多项式时间可解。 第五章讨论单机上工件的加工时间同时依赖于开工时间和所分配的资源量的 排序问题；极小化的目标是时间表长与资源费用之和：li p j = f ，( u ) d i tic m 戤+ | | ( 甜) ； 给出了多项式时间算法。 第六章对论文的总结以及今后研究工作的展望。 几类加工时间与环境有关的排序问题第二章排序问题中的类资源分配问题 第二章排序问题中的一类资源分配问题 2 o 引言 文献【1 2 ，3 - 6 1 讨论了单机上的j n 权总完工时间限定下的最优资源分配问题。文 献【4 6 】讨论了资源有限的单机极小化加权总完工时间问题。秦仁杰和闻振卫【7 】 讨论了加工时间依赖资源而目标函数是极小化时间表长的两台机流水作业资源分 配问题呸ic h a i n ，岛= 6 ：【一巳一，竹万i c 腿。本章在文【7 】的基础上，讨论加工时 j = l 间是资源的线性函数，目标函数为极小化加权总完工时间的两台机流水作业中的 刀n 资源分配问题e c h a i n ，p 2 = - - a 2 鸬，鸬万i q ，并给出了一个求最优 解的多项式算法。 2 1 问题的描述 我们的问题描述为，假设，有两台机器m 和，有1 1 个工件m ，以 ； 每个工件必须在先m 后m 2 上加工；每台机器都按给定的同一工件顺序进行加工。 以下总是不妨设给定的工件顺序为m ，以，朋。一个工件在一台机器上的加工叫 做一道工序；第二道工序的加工时间是所分配给该工序的资源量的线性减函数； 一道工序的加工不可中断；资源是不可再生的且资源量有限。排序的目的是在资 源量有限的条件下使加权总完工时间最小。这类问题可记为： 一一 最ic h a i n ，p 2 = 6 2 一a 2 z 2 ，段，万l _ q( 1 ) 等l皇l 其中，决策变量鸬j 是分配给相应工序的资源量，些s 鸬j 历产1 ，2 ，刀 丝和尾j 分别是资源分配量的下限和上限，不失一般性，可设2 _ 2 _ ，= o ，o _ a 2 ， 0 0 ，则置： c = 蕊n 岛f g 纠lc 2 ：- c l “ o ，廷巡“毪一2 ，森2 f2 蕊珏 正，材，专， 6 雌 叫瑚 吃 出找 几类：b l l i 时间与环境有关的排序问题第二章排序问题中的一类资源分配问题 鸬，= ：鸬，+ 2 ，以，= ：反厂a 2 ，甜= ：甜一a 2 ，； 6 )若反，= 0 ，则置：t = 丁 ) ； 7 )若t = g 或“= 0 ，则算法终止，否则转2 ) 。 则= ( 肋l ，肫2 ，肫。) 为最优资源分配向量。 定理2 2 ：对于问题( 1 ) ，算法1 给出的是最优资源分配。 证明：设给定的工件加工顺序为m ，以z 】。对于一个资源分配= ( 肫l ，肫2 ， 胁) ，我们能写出目标函数的表达式为： 竹刀一一埘，一l 一q = w j p l ，+ 一“p ：， j 2 1j 。li - j + m j _ l i= 1j = 0 h打hm ，一l = w 6 l j + _ + 。( 6 2 厂口：) 一万 ：yy 厶厶 nm - - inm f - 1 w 岛+ w j + ，6 2 j - e 一+ ，口2 段 其中，初始时，( 肫l ，肚2 ，肫d ：( 0 ，o ) 。我们首先把资源优先分配给口2 芝“ 最大的工件o r ，并且让肫尸2 ，注：当分配给西的资源量小于或等于a 2 1 时，目 标函数的表达式不会改变；当分配给扔的资源量大于2 ，时，目标函数的表达式改 变) ；再从新的= ( 肫l ，触，砌) 基础上重复这一做法。对于每个，( _ 1 ，2 j ，1 ) ，随 着资源分配量的增加，竹的计算可知在竹的值只会减少不会增加大，所以 口：芝“也只会减少不会增加；所以算法1 是问题( 1 ) 的最优资源分配。 7 几类加工时间与环境有关的排序问题第三章具有学习和恶化效戍的单机排序问题 第三章具有学习和恶化效应的单机排序问题 3 0 引言 在经典的排序理论中，工件的加工时间是固定不变的，然而在实际环境中， 工件的加工时间往往会随着外界环境的改变而改变。近年来工件具有恶化和学习 效应的排序问题受到了广泛的关注和研究【8 1 9 1 。 如果工件在后面加工比在前面加工所花时间多，则我们称工件具有恶化效应。 g u p t a a n dg u p t a 8 1 和b r o w n ea n dy e c h i a l i t 9 1 分别独立地引入了这种概念。c h e n gd i n g a n dl i n t l o 】对具有恶化效应的排序问题作了综述。 另一方面由于重复加工相同或相似的工件使工人提高了技术和熟练程度，从 而使后加工的工件的加工时间得到缩短。w r i g h t t i m 3 1 首先提出了学习效应的概念并 把学习效应引入到了排序理论中来。b i s k u p 1 4 】对具有学习效应的排序问题进行了 全面的回顾和总结。 近年来，人们虽然对具有学习效应和恶化效应的情况分别做了广泛的研究 8 - 1 9 】，但是对同时考虑两者的情况的研究比较少。工件同时具有学习和恶化效应的 情况在现实生活中是经常存在的【15 1 。 l e e 1 5 1 对加工时间是办= 矿和办= ( p o + 呦矿的极小化时间表长和总完工时间 排序问题进行了研究并给出了多项式时间算法。w a n g t l 6 1 研究了加工时间是办= ( 哆 + 励尸的问题；w a n g t l 7 1 对跏= ( 双r ) + 矿) ( 其中以f ) 是t 的凸函数) 目标函数分别为 时间表长、总完工时间以及完工时间平方之和给出了多项式算法：w a n g 和c h e n g t l 8 】 t l r 一1 讨论了办= 劬+ 吁) 矿的情况；w h 等人【l9 】讨论了马【，】：乃( 鱼挚) 口1 ，口2 的情 风+ 乙i - l p t q 况； 本章研究一个新的同时具有学习效应和恶化效应的模型。 3 1 模型的建立 设有r 个工件m ，也，厶) 需要在一台机器上加工。在0 时所有工件均已到达。 工件加工不可中断，机器每次最多只能加工一个工件。用p j r ( t ) 表示工件巧在第， 8 几类加工时间与环境有关的排序问题第三章具有学习和恶化效戍的单机排序问题 个位置且在时刻，开始加工的加工时间并假定p j ，( ，) = 瞅f ) 尸，其中历是工件巧的基 本加工时间，f 是其开工时间，a ( 0 ) 是学习因子，a t ) 是恶化函数，并x a t ) 是非负 可导增凸函数。 我们分别对目标为时间表长、总完工时间、总完工时间平方之和的问题进行讨 论： 1l 纵f ) = p j ( t ) r aic 矗戤 1ip a t ) = 以f ) ，口i 0 1 i 办( f ) = 只以d ，口j 巧 3 2 模型的求解 周知，对于凸函数有如下结论： 引理3 1 ：设火f ) 是一个正的可导增凸函数( 即越长越快函数，例如a 0 = 2 t + 3 ，a 0 = 2 7 + 4 ，2 + 5 且f 0 等) ，0s x l 娩 x 3 是给定的实数，则存在x l 卣 x 2 ，x l 彘 p j 。 则有 g ( 力= t o + p d ( t o ) r a c a # ) = t o + p t f ( t o ) r a + p a t o + p 以幻) 尸) ( 厂+ 1 ) 口 我们交换工件z 和z 得到一个新排序，在兀，中 c = ，( n 9 = t o + p a t o ) ： c i ( 7 r = f 0 + p f l t o ) ：+ p 扳硒+ p j ( t o ) r a ) ( r + 1 ) 口 c , o r 9 - 啄力= t o + p a t o ) ：+ p d ( t o + p t ( t o ) r a ) ( r + 1 ) q 一 t o + p d ( t o ) r a + p f l ( t o + p j ( t o ) r a ) ( r + 1 ) 口】 = 夕f o ) ，一只以硒+ p d ( t o ) r a ) ( r + 1 ) 口】 + 【p 次f 0 + 烈幻) 厂口) ( 厂+ 1 ) a - p d ( t o ) r a = 坝幻) r a - p a t o ) ( 厂+ 1 ) 口+ p j ( t o ) o + 1 ) 口一瞅幻+ p 以，o ) ，) 驴+ 1 ) 口】 + p 次硒+ 拟幻) 一( 厂+ 1 ) a - p d ( t o ) ( r + 1 ) 口+ p 次，o ) ( 厂+ 1 ) 口一p d ( t o ) r a 9 几类加工时间与环境有关的排序问题第三章具有学习和恶化效应的单机排序问题 = 狄f o ) ，口一p a t o ) ( ，+ 1 ) 口】+ 锨，o ) ( ，+ 1 ) 口一p z ( t o + p 以f 0 ) ，口) ( ，+ 1 ) 口】 + p i ，( ，o + p f f ( t o ) r a ) ( r + 1 ) 口一p 次r o ) ( ，+ 1 ) 口】+ 【p j ( t o ) ( r + 1 ) a p 以，o ) 一 = p d ( t o ) ( 尸一( 厂+ 1 ) 口) + 历( ，+ 1 ) 口 ( t o ) - 火f o + p j ( t o ) r a ) 】 + p fp + 1 ) 口 ( t o + p f f ( t o ) r a ) 苁，0 ) 】+ p 以，o ) 【( ，+ 1 ) 口一一 = 髟e ，【，o ) ( 尸一o + 1 ) 口) + p 以f o ) 【( r + 1 ) 口一，口】 + 力驴+ 1 ) 口 八彘) ( 一p 以f o ) 尸) 】+ p i ( ，+ 1 ) 口【八白) ( 见_ 【f 0 ) 尸) 】 = 贝，0 ) ( 尸一( ，+ 1 ) 勺( 助一p j + p j p j ，口( 厂+ 1 ) 口【f 0 ) 【飞白) 一八彘) 】 其中，0 备 t o + 献f o ) 尸，t o 彘 0 ，从而g ( 万啄力 c ( 万，；又由定理3 2 可知g ( 力 g ( 万；与定理3 2 的证明类似可得比7 c 更优，这与7 c 是最优排序相矛盾。故按乃不减排序( s p t ) 可得 问题1 i p a t ) = 袱，) 尸i q 的最优解。 定理3 4 ：对于问题1 ip j r ( t ) = p f f ( t ) r ai g 2 ，按防不减排序( s p t ) ，可以得到问题的 最优解。 证明：与定理3 3 证明类似可得g ( 刀 啄万，以及q ( 力 “万，故有c 疋刀) 2 c x 万2 ，c ( 力2 g ( 万2 ；于是兀比7 c 更优，这与7 【是最优排序相矛盾。故按历不减排 序( s p t ) 可得问题1 1 p j , ( t ) = 瞅，) ，i g 2 的最优解。 1 0 几类加工时问与环境有关的排序问题第阴章具有学习效用的单机成组排序问题 第四章具有学习效用的单机成组排序问题 4 0 引言 唐恒永、赵传立吲对带有安装时间的成组排序问题进行了研究。w e nh u a y a n g 等【2 0 1 研究了具有多种工件类，机器具有学习和遗忘效应的分批排序问题。王吉波 等【2 1 】研究了工件加工时间是开工时间线性函数，带有安装时间的单机成组排序问 题，并对目标函数是时间表长或总完工时间的情况给出了多项式时间算法。 c h i n c h i a - w u 等【2 2 1 研究了工件加工时间和安装时间都是开工时间的简单线性恶化 函数的单机成组问题，并对目标函数是时间表长或总完工时间的情况给出了多项 式时间算法。本章在上述文献的基础上研究了组内工件具有依赖加工位置学习效 应的单机成组排序问题，并对目标函数是时间表长、总完工时间的情况给出了多 项式时间算法。 4 1 问题的描述 设有力个工件“，如，五) 分成了m 个组 g l ，g 2 ，g 掰 ；工件都在0 时刻到 达；工件在单机上加工且加工不允许中断。当这厅个工件在处理机上加工时，只 有加工完一组工件后才能加工另一组工件，并且处理机加工新的一组工件时需要 一个与该组有关的安装时间。记嘞为工件组g j = “l ，如，厶 所包含的工件个 数，n l + n 2 + + 刀刖= 刀；p ，表示工件由的基本加工时间。工件由在组内具有学习效 应p ( u r ) = p c r q ，其中，表示工件乃在组g ，内的加工位置，0 【f ( o ) 是组g ，的学习 因子。本章讨论如下两类问题：。 1lp ( 弛，) = p g r q ，s , g t l c m 双 1 p ( “力2 p e r q ，s , g ti z z c # 4 2 模型的求解 引理4 1 【1 3 】：对于问题1 1 黝砀尸i c m 戤按工件的基本加工时间历不减排序是问题 的最优解。 几类加工时间与环境有关的排序问题第p q 章具有学习效用的单机成纽排序问题 j = 一 c 。“= p ( j ，) j = l 定理4 2 ：对于问题1 ip ( 弛力= p o r 嘶，s ，g ti c m 瓢，组内按基本加工时间p ，不减排 序，组间任意排序是问题的最有解。 证明：对于问题1i p ( “厂) = p g r 白，s ，g t l c m 积其目标值函数可以表示为： i = mi = m ，t c m 戤= 岛+ zz p ( i ，j , r ) 由此可知目标函数的值与组间的排序无关；由引理4 1 ，= l t - - i = l n ji = mn j 可知组内按p l ，不减排序使p ( f ，j f ，r ) 极j 、化，从而可使p ( i ，：，) 极小化；而 ，互脚 墨为常数与排序无关；定理得证。 i = 1 引理4 3 1 1 1 ：对于问题i t p j ，= p j r 口i 0 按工件的基本加工时间历不减排序是问题的 最优解。 c ，= p ( 歹，) o 一厂+ 1 ) j - i= l 引理4 4 1 4 ：对于问题1 1s , g ti z z c u 组内按加工时间p l ，不减排序，组间按 ( 墨+ 笠助) 不减排序是问题的最优解。 j = l i = mj 2 n il = mi ；mj 3 n li = r ai 、 n t q = n ；+ p g ( n ，一厂+ 1 ) + n i ( 以+ ) i = l j - i i = l = 】= l i = 2k = l - ，= l 定理4 5 ：对于问题1 l p ( “r ) = p 扩，嘶，s , g t i z z c , j ，组内按基本加工时间p ，不减排序， j t n 组间按( + p ( f ，r j ) ) n , 不减排序是问题的最有解。 j 军l 证明：对于问题1 p o d , r ) - p o r , s , g t i 白，其目标值函数可以表示为： 1 2 、，力职lp 一 + ，l h 心 惕 砌磁 + d + r 一 体，l力op m 同 砌甜 + 吩 墨 姗僦 = q m 一 砌m 几类加工时问与环境有关的排序问题 第阴章具有学习效用的单机成组排序问题 ，= 埘 ( i ) x g l i 为常数与排序无关； i = mj 2 n l ( i i ) p ( f ，) ( - 一，+ 1 ) 与组间的排序无关，只与组内的排序有关，由引理4 3 i = l = l 可知，组内按工件的基本加工时间砌不减排序可以极小化笠p ( f ，歹，。) ( 一，：+ 1 ) ， j = l f ；mj 。n l 从而能极小化p ( f ，：) ( 吩一乃+ 1 ) 。 t = lj t l ( i i i ) 兰艺( + 兰p ( 七，) ) 由引理4 1 可知组内按工件基本加工时间助不减排序 i = 2 k = l i - i 可使鐾p ( f ，) 极小化从而使( _ + 笠p ( f ，j f ，。) ) 极小化；由引理4 3 可知， i = 1z l ，t 飓 当组内工件的加工时间固定时组间按( _ + p ( f ，- ) ) 惕不减排序可以极小化 1 = 1 所以当组内按基本加工时间珊不减排序， 极小化目标函数。 j = n 组间按( + p ( f ，o ) ) 不减排序可 = l 、，力t，lp 同 + ，l h 树 协 m 几类加工时间与环境有关的排序问题 第五章加工时间依赖开工时间和资源的排序问题 第五章加工时间依赖开工时间和资源的排序问题 5 0 引言 工件的加工时间依赖开工时间的排序问题已经得到了广泛的关注和研究 2 3 - 2 7 l 。g u p t a 和g u p t a 【2 3 1 首先提出了加工时间是开工时间的简单线性函数的情况： 胁= 口f + 6 芦。m o s h e i o v 【2 4 1 考虑了加工时间是开工时间的简单线性函数的情形：p f b _ f s , f ， 分别对目标函数是时间表长、加权总完工和最大误工数的问题给出了多项式时间。 m o s h e i o v l 2 5 】提出了分段函数的情景：如果s 鲻，则胁- - - - a i ，否则胁= 6 f ，并就目标函 数是时间表长和总完工时间问题进行了研究。c h e n g 2 8 1 等人研究了分段线性函数的 情形：p 尸口j - b j m i n s , ，西) 。k u n n a t h u r 和g u p t a e ：9 1 讨论了加工时间是分段增函数的情 况：p 广- m a x a , ，嘶+ 6 f o f 棚) 。 资源约束排序是排序理论的重要组成部分，在实际生活中具有广泛的应用 4 , 2 1 n ) 0 1 。2 0 世纪9 0 年代初，a d a m j a n i 舭2 8 1 研究了问题：1p a = 6 广g l ，c m , c l z u , 这类资源约束的排序。 虽然加工时间分别依赖资源和开工时间的排序问题已有了不少的研究【 4 , 3 - 3 f f 】， 但同时依赖资源和开工时间的排序问题的情况研究得还是较少。胡金华【3 1 】对问题 l 慨= 毋口f 撕+ 耽历f s uc m 缸进行了研究。 5 1 问题的描述 由于资源的投入可使加工时间得到减少，同时，由于学习效应，同一个工件 开工得越晚加工时间也越短。本章我们假定，工件巧的加工时间可表示为：历= 以砂 - 和( ，= 1 ，2 ，行) ，其中，0 磅 1 ，u 是资源投入量，石( 甜) 均是非负可导减凸函数 ( 越减越慢) 且满足( l ( o - f , ( u - - ) ) a , - - p n d n 。 引理5 2 ：对于问题1 1p j = 乃 ) - 嘭，u u 万ic m 戤+ 七 ) ，当资源投入量u 给定时，按以材) 饽不增排序是最优的。 证明：由引理5 1 易知，由引理5 2 成立。 对于给定“下的问题ll 乃= z ) 一嘭，u u 订i + 七似) ，我们记其中 的c m 缸= c m 双( “) 。显然c m 舣( “) 是u 的连续减函数；但由于杖是u 的连续增函数， 我们只知道c t m 默+ 议“) 是u 的连续函数而不能判定它是否为增或减函数。 对于给定的资源投入量u o 也材o 甜) ，若按以甜o ) 巧不增顺序排列中，不等号 均成严格不等，那么由于以功q = l ，2 ，功都是关于“的连续函数，当u 发生微小 改变a u 时，以d 傅的不增排序不会发生改变。但随着i z a u l f 拘增大会出现某f ( u ) a , = 崩甜) 反( f 确，我们称这样的“为一个关键资源量点，并记作品；对于这样的品，至 少存在着两个最优排序，因为交换工件z 和工件巩的加工顺序不会改变目标函数 的值。 如果我们求出( 马u - ) 内的全部关键资源量点： 也- ) u o 1 1 1 1 1 2 ，u m - l 0 而，o 兀( 1 一吃) 为常数， 力打疗 故c m 双( “) = f j ( u ) 兀( 1 - 4 ) + t o 兀( 1 一z ) 在每个小区间上是减凸函数。 由于在整个区间 丝，云 上最优的加工顺序不一样，故整个区间 丝，云 上 一一一 c m 戡似) = f j ( u ) 兀( 1 一z ) + ，0 兀( 1 一吐) 不再是减凸曲线。 由引理5 2 可知，对于给定的资源量u t ( 其中是充分小的正数) ，f = 1 , 2 ，m ， 我们能够找出最优的排序乃；由引理5 3 可知c m 舣( 甜) 是分段减凸函数，而颤功是增 凸函数，故在每一个小区间上目标函数c m “+ 故“) 是凸函数。利用这个性质，我们 利用求导找出每一个小区间上的最优资源分配量 ；及其最优目标函数值c m 戤( 西) + 议西) ，i = 1 , 2 ，m 。于是我们可找出问题的最优目标函数值以及最优排序。具 体步骤如f ： 1 求区间 坠云 上的所有使得以“) 锄= 似甜m ( 后胡的品，设这些点是： 丝= 磊。 z ，a 气丢： - - f j 也) 弓 - - f m ( u ) 磊 3 分析第k 个区间 3 1 对于给定的资源分配量丢t ，由引理5 2 可知【磊丢】上最优排序巩； 3 2 对于给定的排序巩我们在区间 品品。】上利用定理5 3 求出最优资源分配量 玩和最优目标函数五( 玩) = c m 瓠( “：) + 七( 域) 3 3 如果尔触，则 e s t = 派，7 t b c s t - ：刀 k ，i r b e s t - ：u ：； 4 如果k m ，终1 e 运算：否则肛= 尼+ 1 ：返回3 ： 1 6 几类加t 时问与环境有关的排序问题 第五章加工时间依赖开工时间和资源的排序问题 5 3 计算复杂性分析 在算法的第一步至多要计算c ：= n ( n 一1 ) 2 次运算，由于瓜“) ，j = l ，2 ，刀都 是减凸函数故至多求出n ( n 一1 ) 个不同的值，在第三步中，对于每一个小区间，由 引理2 可知，其最优排序的运算的复杂性为o ( n l o g n ) ，而由于目标函数是凸函数故 在小区间内求最优解只需要求一次导数即可求出，故整个算法的复杂性为 o ( n l o g n ) 5 4 问题的总结和扩展 本章主要讨论了工件的加工间依赖于资源的分配量和开工时间的情况，其中 资源分配量决定工件的基本加工时间；我们很容易对问题进行扩充： l 资源的分配量决定基本加工时间的具有学习效应的情况： 1i p j = f a u ) r lc m 戤+ 双“) 1i 历= 以“) 尸i 0 + 舣 学习因子：a o 2 资源的分配量决定学习因子的情况： 1i 历2a j - 以“) fic - m 觚+ 颤“) 3 资源分配量决定恶化因子的情况： 1f 历2a j + f j ( u ) ti c m 默+ 颤彬 1 7 几类加工时间与环境有关的排序问题第六章总结与展望 第六章总结与展望 排序论作为运筹学的一个分支，有着深刻的实际背景和广泛的应用前景。排 序论一直受到国际上学术界的重视。从深层次和长远来看，排序论对提高效率、 资源的开发和配置、工程进展的安排以及经济运行等方面都起到辅助科学决策的 作用。 本文在充分考虑了资源和时间的约束条件下有效的处理工件的加工顺序和资 源分配：在第二章中我们只考虑了第二道工序的资源分配，我们还可以进一步考 虑第一道工序的资源分配以及两道工序同时资源分配的情况；在第五章中考虑的 资源分配是独立于工件，我们可以进一步考虑资源的分配与工件有关的资源分配 问题。 排序问题是工业生产中一类带有普遍性的问题。我们在后续的学习和研究中 应该突破经典排序问题的关于资源类型、确定性、可运算性、单目标和正则性的 基本假设；使数学假设更加贴近现实生活。加强对现实环境的考虑；更多地关注 现代排序论的研究：结合计算机技术，编制更加使用的算法。这些是我们今后研 究的思路和方向，从而使我们的研究能更好的为现实生活服务，为排序论在科学 决策中充分发挥作用做一点贡献。 几类加工时间与环境有关的排序问题 参考文献 参考文献 【1 】王吉波，唐恒永一类资源约束排序问题l lp j = 岛一吩吩，z w , g 彳| 吩【j 】辽宁 师范大学( 自然科学版) ，2 0 0 1 ，2 8 ( 4 ) ：3 1 0 3 1 2 【2 】程丛电，唐t o 永，张丽华加权总完x - n - 问有限的受资源约束排序问题【j 】系统工 程理论方法应用，2 0 0 2 ，1 1 ( 2 ) ：1 3 1 - 1 3 5 【3 】赵琨，唐恒永加权总完工时间有限的资源约束单机排序问题 j 】沈阳师范大 学学报( 自然科学版) ，2 0 0 4 ，2 2 ( 0 3 ) ：1 6 1 1 6 4 4 】唐恒永，赵传立排序引论 m 】北京：科学出版社，2 0 0 2 【5 】唐恒永，赵琨资源有限的加权总完工时间单机排序问题【j 】运筹与管理， 2 0 0 4 ，1 3 ( 3 ) 4 8 5 1 【6 】柏孟卓，唐恒永类资源约束排序问题的几种特殊情况 j 】沈阳师范大学学报 ( 自然科学版) ，2 0 0 3 ，2 1 ( 1 ) ：5 8 【7 】秦仁杰，闻振卫加工时间依赖资源的流水作业资源分配问题 j 】运筹与管理， 2 0 0 5 ，14 ( 2 ) ：6 7 6 9 【8 】g u p t a , j n d ，g u p t a ，s k ，s i n g l ef a c i l i 锣s c h e d u l i n gw i t hn o n l i n e a rp r o c e s s i n g t i m e s j c o m p u t e r sa n di n d u s t r i a le n g i n e e r i n g ，19 8 8 ，1 4 ：3 8 7 3 9 3 【9 】9 b r o w n e ，s ，y e c h i a l i ，u ，s c h e d u l i n gd e t