（概率论与数理统计专业论文）几个不同参数可控的排序问题的讨论.pdf

凡个不同参数可控的撵序问题的讨论 中文摘要 几个不同参数可控的排序问题的讨论 中文摘要 本文包括四部分第一章引言介绍排序问题和可控排序问题及其一些背景知 识。第二章针对工件交货瓣可控的排序问题( p 1 ) ，分裂研究了两种情形：l | 以) = 磅+ 耻l 瞰+ e , 5 和lj 纵) = 弓+ 耻l 仍+ e a ，给出了这两个问题的最优算法 第三章针对加工时闻可控并且带有学习效应的排序问题( p 3 ) ，分剃讨论了：ll 鼢 气肾a j j ) r a ，坳5qic n 搬和li 跏= ( 肾a , j ) r * ，垮sq lz g ，并讨论了这两个问 题在指定工件顺序下最优资源分配的性质给出了它们的多项式可解情形第四 章总结论文的主要结果以及提出一些展望 关键词：排序，工件，可控，学习效应，极小化 作者：胡爱丽 指导教师：闻振卫 凡个不羹参数酉控翁捺彦酒题麴讨论撬要 s c h e d u l i n gp r o b l e m sw i t hd i f f e r e n t c o n t r o l l a b l ep a r a m e t e r s 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 t r o d u c e ss o m eb a c k g r o u n d i n f o r m a t i o no fs c h e d u l i n gp r o b l e m sa n dc o n t r o l l a b l ep r a m e t e rp r o b l e m s c h a p t e rt w o i n v e s t i g a t e 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 m sw i mc o n t r o l l a b l ed u ed a t e s o p t i m a l s o l u t i o n s o f p r o b l e m s1i 李( 砷。苟酗il m a x + 如a n d1 巅萄= 谤+ 酗l q + e aa r eg i v e n c h a p t e rt h l e ed i s c u s s e st w os 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 m sw i t h c o n t r o l l a b l ep r o c e s s i n gt i m e sa n dl e a n i n ge f f e c t t h eo b j e c t i v ef u n c t i o n sa r em a k e s p a n a n dt o t a lc o m p l e t i o nt i m er e s p e c t i v e l y ：il 办= 锄+ a j u j 炉垮sq c m 鼓a n d 1l 办* 锄+ a ju 1 ) 一y u jsq g u n d e r ag i v e nj 曲s e q u e n c e ，p r o p e r t i e so no p t i m a l r e s o u r c e 鑫l l o c a f i o na r ed i s c u s s e d 。w l 也t h e s ep r o p e r t i e so p t i m a la l g o r t h m sa r eg i v e n r e s p e c t i v e l yf o r p j = 辟a j = a ；p = 届奇，* 五；a n da j = 口，舀，= 露i nc h a p t e rf o u r , w e s u m m a r i z et h et h e s i sa n dp r o p o s es o m en e w p r o b l e m s 。 k e y w o r d s ：s c h e d u l e ；j o b ；c o n t r o l l a b l e ；l e a r n i n ge f f e c 篱m i n i m i z a t i o n 。 玎 w r i t t e nb yh ua i l i s u p e r v i s e db yp r o f w e nz h e n w e i 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交蠹勺学位论文是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文 不含其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏 州大学或其它教育机构的学位证书面使用过的材料。对本文的研究作 出重要贡献的个人和集体，均已在文中以明确方式标明本人承担本 声骧的法律责任 研究生签名：翅量虽霉期：趁避 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论 文合作部、中国社科院文献信息情报中心有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论 文本人电子文档的内容和纸质论文的内容相致除在保密期内的 保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的 全部或部分内容。论文的公布( 包括刊登) 授权苏州大学学位办办理 研究生签名：翻熏厨e l 期：丝2 ：_ 垒生 儿个不同参数可控的排序问题的讨论第一章引言 第一章引言 1 1 排序问题的简介 1 1 1 排序问题的定义 排序也叫调度或排时间表，是一类重要的组合最优化问题它广泛应用于管 理科学、计算机科学和工程技术等很多领域，是运筹学研究的一个非常活跃的分 支排序的目的是利用一些机器( 处理机) 或包括资源，在加工时间满足特定条 件，如工件的就绪时间、交货期、工件加工优先顺序、资源对加工时间的影响等 限制下，对给定的工件集进行加工以达到最优地完成其中，最优地完成指的是 给定的目标函数达到最小，而目标函数通常是对加工时间或机器利用效率的描述 1 1 2 排序模型的三元组表示法 由排序问题的定义，我们不难看出：机器，工件和目标函数是构成排序问题 的三要素我们用g r a h a m 1 】等人首先使用的三元组来描述排序问题的具体模型 三元组记号由三个域组成：口i iz 它们具有如下的含义： 碱表示机器的数量、类型和环境它可以为： 1 ：单机，即只有一台机器 i m ：f i t 台同速机，即聊台具有相同功能和速度的机器，任一工件在任一机 器上加工即可，且在每台机上加工所需时间相同 q m t n 台恒速机，即r f t 台具有相同功能但速度不同的机器，任一工件在任 一机器上加工即可，但在不同机器上加工所需时间不同 r m ：册台恒速机，即聊台具有相同功能的机器，任一工件在任一机器上加 工即可，但机器的速度依赖于被加工工件 f m ：肌台机的流水作业，即朋台机器具有不同的功能，每一个工件在每一 台机器上都有一道工序要加工，且各个工件的工序相同 o m ：历台机的开放作业，即聊台机器具有不同的功能，每一个工件在每一 台机器上都有一道工序要加工，且各个工件均可以按任意工序加工 咖：m 台机的异序作业，即肌台机器具有不同的功能，每一个工件在每一台 几个不同参数可控的排序问题的讨论第一章引言 机器上都有一道工序要加工，且各个工件均有自己的工序加工顺序 臌表示工件的性质、加工要求和限制、资源的种类、数量和对工件加工的 影响等约束条件膦可以包括多项，当出现两项或两项以上时用逗号隔开即可 约束条件的可能情况多样，我们在具体用到时再给出详细解释 础表示要优化的目标函数，记c = ( c l ，c 2 ，g ) 为工件集j _ - m ，以，厶) 在一个给定排序下的完工时间，目标函数主要有以下几种： c m 缸：时间表长( 最大完工时间) ，即c m 戤= m a x c j 它等于最后一个被加 工完的工件的完工时间，小的时间表长意味着高的机器利用效率 0 ，e 岵c j ( 加权) 总完工时间 工m 戤：最大延迟，即三m 双= m a ) 【 白) ，其中弓= c j - 巧是工件- ，的延迟时间 乃，龇乃：( 加权) 总误工时间，其中乃= m a x q - 弓，0 ) 巧，m ：( 加权) 总误工数，其中驴 ，翌 1 1 3 排序问题的求解 排序问题作为一类特殊的组合最优化问题，其可行解和最优解分别称为可行 排序和最优排序在排序问题中，一个可行排序( 或可行时间表) 就是一个工件 顺序或排列及其加工时间所处的位置，且按照这个时间表，在给定的机器上加工 所有工件是能实现的由于排序问题中机器、工件或作业都是有限的，因此绝大 部分排序问题是从有限个可行排序中找出一个使得目标函数达到最小的排序，即 最优排序 求解排序问题的基本思路是：应用或借鉴求解其它组合最优化问题的方法， 充分利用排序问题本身的特殊性质，以确定满足约束条件的最优排序求解排序 问题的基本步骤是：首先，要用复杂性理论对问题进行分析，以便知道所求问题 的难度其次，对于存在多项式算法的排序问题，要尽可能地找出空间复杂性和 时间复杂性好的算法，所谓空间复杂性是指算法所占存储的多少，时间复杂性是 指计算时间的长短，它们均是输入规模的函数对于n p 难问题则有两种处理方 法：一是用分枝定界法、动态规划法等巧妙的穷举法求出其精确最优排序这类 算法的计算量大，只有对规模较小的问题才是可行的；另一种是求出其近似最优 2 几个不同参数可控的排序问题的讨论 第一章引言 排序，各种局部搜索算法和启发式算法都是很有效的近似算法，但其近似程度的 界定是一项困难而必不可少的工作 1 2 可控排序的概况 1 2 1 可控问题的定义及其分类 随着经济和科学技术的发展，大量新的排序问题层出不穷，出现了许多新的 模型，可控排序便是其中很重要的一类现代排序模型【2 】 经典排序问题中工件的参数，例如工件的加工时间、交货期、就绪时间和权 等都是给定的常数或分布确定的随机变量然而，在现实生活的有些排序问题中， 工件在机器上加工除了机器的因素外还需要使用人力、资金等其他资源我们通 过改变或者控制机器之外的资源，就可以改变或控制工件参数的大小这时，工 件的参数就不再是固定不变的 上述环境下的排序问题，我们统称之为可控排序根据所控制参数的不同， 可控排序可以分为加工时间可控排序、交货期可控排序、就绪时间可控排序等； 根据所控参数取值的离散或连续性，可控排序又可以分为离散可控排序和连续可 控排序；根据可控排序所涉及的两个费用( 完工费用函数和控制费用函数) 以不 同结合方式构成的目标函数，模型又可以分为如下四类可控排序问题： 沿用n o w i c k i 和z d r z a l k a n 的记号记，= 仙，以，厶) 是加工的工件集合对 于工件加工次序的一个排法7 = 陬( 1 ) ，7 c ( 2 ) ，7 【】和一组控制参数x = o l ，娩， 如) ( 其中而可以是工件巧的加工时间、交货期、就绪时间或权等) ，它对应y - c 件集的一组完工时间c = ( c l ，c 2 ，g ) ，并发生两种费用：一种是与工件加工 次序和控制参数取值都有关的工件的完工费用，记为只g ，兀) ；另一种是控制参数 所需的控制费用，记为屁o ) 完工费用f l 可以是经典排序问题中的任意一种目标 函数；控制费用函数b 与工件加工次序无关，是控制参数x 的非降函数，它是由 问题的实际背景所决定的完工费用冗o ，兀) 和控制费用尼之和称为总费用，记 为f ( x ，兀) ，即： 声诳，7 c ) = 只 ，7 t ) + 局( 】) 3 几个不同参数可控的排序问题的讨论第一章引言 记x 是控制参数工可能取值的全体，n 是所有排法7 c 的全体，我们把具体的 个( 五兀) 称为可控排序的一个可行解，把使得目标函数最小的可行解( z ，冗) 称为最优解根据可控排序所涉及的两个费用( 完工费用函数和控制费用函数) 以不同结合方式构成的目标函数，模型又可以分为如下四类可控排序问题：分别 称为可控问题( p i ) 、可控问题( p 2 ) 、可控问题( p 3 ) 、可控问题( p 4 ) 可控问题p 1 ) ：寻找( ，尢) ( xn ) ，使得总费用m ，力最小： f ( x + ，兀) = r a i n 月砷lz xn e l - i 可控问题僻) ：寻找( 工，7 c ) ( zn ) ，在使完工费用蜀瓴兀) 有限制的条件 下使得控制费用足g ) 最小： 尼q ) = r a i n 疋( 功if l ( x ，兀) s 柳，x 五兀n ) 其中m 是给定的常数 可控问题) ：寻找( j ，兀) ( 五) ，在控制费用局有限制的条件下 使得完工费用r o ，砖最小： 局0 。，7 c ) = m i n f 1 ( x , 兀) f 恳毛z x 氕兀) 其中k 是给定的常数 可控问题( ) ：寻找( j ，兀) ( 五n ) ，使得完工费用f l ( x ，7 c ) 和控制费用 最都达到最小： 局f ，7 c ) = r a i n 凡 ，氕) l 工五尢1 - i ) r f ) = m i n 毋iz 田 注：如果不能使得完工费用r o ，兀) 和控制费用r ( 砷同时达到( 绝对的) 最小， 则要求找出其有效解 1 2 2 可控排序的发展概况 可控排序在其实际背景的推动下，已经引起了广泛的关注可控排序的雏形 可以追溯到1 9 6 9 年l a w l e r 和m o o r e 的论文【3 1 ，他们提出了每个工件可以选择两 个不同的加工时间中的一个进行加工的假定1 9 8 0 年v i c k s o n 第一次在排序文献 中提出可控的概念 4 1 同年，他【5 1 又研究了工件加工时间可控的排序问题p 1 ) l ic p tl 啪蛹，n o w i c k i 和z d r z a l k a 6 1 对于工件加工时间可控的情况研究了多 种排序问题，得到了丰富的成果i - l u a n g 和张峰刀研究了问题lic p tl 印矿蚂 4 几个不同参数可控的排序问题的讨论 第一章引言 的多项式时间可解的特殊情形张峰和唐国春等【8 ，9 】应用凸二次规划松弛方法设 计了问题1ic p tl 鲈矿跏0 的多项式时间近似算法陈德伍和张峰 1 0 j l l 讨论了控 制费用函数取加工时间最大压缩比例的多个情形的可控问题( 尸1 ) ，并给出了多项 式时间算法n o w i c k ie 和z d r z a l k as t l 2 1 研究了平行机可中断排序问题的加工时间 连续可控的时间表长问题，给出了一个贪婪算法h u a n g 等【l3 】研究了可控问题( 尸1 ) llc p t l 呐+ 乃证明了问题是n p 难的，并给出了一个启发式算法张峰【1 4 】和陈 志龙、唐国割”1 研究了加工时间离散可控的排序问题，即每一个工件有若干个加 工时间可供选择徐玲和张峰1 1 6 研究了平行机排序的加工时间离散可控的时间表 长问题p mid i s - o p t ，p m t nl 嘴+ c l 懈，证明了它是m 一难的，并应用线性规划松 弛方法给出了一个近似算法柏孟卓和唐国春【17 】讨论了加工时间离散可控的同时 加工排序问题，分析了问题最优解应具备的性质，并给出了有效的动态规划算法 关于工件的其他参数可控的排序问题也备受关注：n o w i c k i 和捌l 【a 【6 】证明 了就绪时间可控的1l 吩，c ric r 嗽的问题( p 1 ) 是n p - 难的，并且给出了紧界为2 的 近似算法孙世杰o v 2 0 研究了1i 巧，p j = l ，c ric i 懈，li 吩，历= l ，c ri c j ，1io , p j = 1 ，9 = l ，c ri 厶慨和1l ，= ，刃= 1 ，9 = 1 ，c rix w , c ，的( p 4 ) 可控模型，给出了有效点 集求解的拟多项式时间算法c h e n g 和s h a k h l e v i e h t 2 1 1 分别研究了li 乃，易= 1 ， c ric t 呱，ll 巧，历= 1 ，9 = 1 ，c rlc m 积的( p 1 ) 、( p 2 ) 、( p 3 ) 模型，还证明了ll r j ， 历= 1 ，c ri 蚂的( p 1 ) 、( p 2 ) 、( p 3 ) 模型均为n p - 难的c h e n g 、k o v a l y o v 和 s 删e v i c h 【2 2 】则研究了工件加工时间和就绪时间均可以压缩的情形，给出了一些 重要结果张玉忠和张树霞田1 研究了离散就绪时间的( p 1 ) 可控问题li ，= ， d i s c ric m 驭，给出了指定序下的最优算法 孙世杰和r j k i b e t l 2 4 研究了交货期可控的问题( p 4 ) 1ir j ，历= 1 ，9 = li m 联， 在【2 5 1 研究了交货期可控的问题( p 4 ) 1l i 峨给出了有效点集构造的个伪多项式 算法 本文讨论两类参数连续可控的单机排序问题：一类是交货期可控、完工费用 分别取最大延迟三m 舣和总误工数u ，时的可控问题( p i ) ；一类是加工时间可控 且带有学习效应、完工费用分别取时间表长c m 戤和总完工时间c ，的可控问题 ( p 3 ) 几个不同参数可控的排序问题的讨论 第二章交货期可控的排序问题( p 1 ) 第二章交货期可控的排序问题( p 1 ) 设有工件集j = ，2 ，厶) 由疗个工件构成；工件五的正常交货期为弓， 工件的交货期可控，即工件的交货期允许滞后( 延后) ，工件的实际交货期为4 ( x j ) = 芬+ x j ( os x j 历) ，其中历表示工件巧的交货期的最大允许滞后量，力工件巧 交货期的实际滞后量，工件的加工时间、完工时间、延迟时间与延误工件个数分 别记为历，g ，白，铲1 ，2 ，厅) 可控问题中，控制费用函数足通常具有两种形式：一种是取和形式，即 嘴，其中c j 为参数控制的单位费用；另一种是取最大的形式，即m a x 而i - - 1 ， 2 ，刀) 为了便于分析，令a j = x j ，则工件巧的实际交货期表达式可以改写为： 碍( 锄2 弓+ 厚4 ( o s 屏0 4 1 ) 其中决策变量4 是工件西交货期滞后量与其最大允许滞后量的比例 我们考虑完工费用函数凡 力分别取最大延迟三。懈和总误工数珥，控制费。 用函数足a ) 【 4i 产1 ，2 ，刃) 时的( p 1 ) 可控问题，即目标函数为总费用函 数： f ( x ，力= l m 畎+ e a 或踢+ 朗 其中参m a x 4i 歹= 1 ，2 ，挖) ，e 0 是常数 当取定时，要使得完工费用的值最小，显然要尽量的延后各个工件的交货 期，即工件巧u = l ，2 ，刀) 的实际交货期取纵) = 西+ 厚故本节我们讨论 的排序问题不妨表示如下： ll 码( ) = 西+ 厚ai 三m 戤+ e a( 2 1 ) 1l 颤) = 弓+ 历ie 够+ e a( 2 2 ) 6 几个不同参数可控的排序问题的讨论 第二章交货期可控的排序问题( p 1 ) 2 1 问题ll 弓( ) = 吗+ 历ai 上m 。x + e a 由经典排序理论，我们知道e d d 序是问题1ii 棚的最优排序，为了寻求 问题( 2 1 ) 的解，我们先给出e d d 序的不变区间的定义 记l 是方程西+ 届4 = 弓+ 厚4 的解显然，当面西，西+ f l , 弓+ 历( 即届 励，且i = ( 巧西) ( 届仰( 0 ，1 ) 时，并因此当【0 ， ，) 时，呶a ) = 西+ 耻啾) = 弓+ 历；而当【 ，l 】时，纵) = 西+ 耻纵) = 弓+ 耻将所有落在( 0 ，1 ) 内的a 驴( v i ，j = 1 ，2 ，玎) 记作0 = o a l 缸l = 1 这样就将区间【0 ，1 】 分成了s 个小区间【o ，a d ，【a i ，2 】，【缸l ，j 显然，当在某一个小区1 8 - a k 1 ，d ( 七= 1 ，2 ，j ) 内变动时，工件的实际 交货期纵) = 弓+ 鲈u = 1 ，2 ，刀) 的大小次序保持不变， 即工件集的e d d 序保持不变我们称上述这些小区间【o ，l 】，【l 2 】，【缸l ，a s 】为e d d 序不变 闭区间当= a k 时，存在两个工件的实际交货期相同，则既可以看作在【“l ， 七】，也可以看作为在【b “l 】上( i j = l ，2 ，s - 1 ) 定理2 1 1 对于任意的一个e d d 序不变区间【矗l d ( 七= 1 ，2 ，j ) ，当限 定落在【如i ，d 上的条件下， 问题( 2 1 ) 的目标函数只，力= 。撒+ e 必定 在区间端点雠l 或& 处取得极小值 证明v 口，6 【雠l 赴】且a b ，则 厶 0 ，有 厶( 口) + 阳 纵6 ) + e b 故v a 【鲸l ，& 】，厶 ) + e 在右端点处取得极小值 ( i i i ) 当历一e 0 时，有 姒口) + 以6 ) + e b 故v a 【如i ，a k ，郴) + e a 在左端点处取得极小值 进而 v a 【缸l ，d ，只) = m a x 厶( ) + e ai j = l ，2 ，疗) 必定在某端点处取得极 小值口 根据定理2 1 1 ，问题( 2 1 ) 可以转化为问题r a i n 只七) l 七= 0 ，1 ，2 ，s ) ， 于是，我们得到求解问题( 2 1 ) 的算法如下： 算法2 1 步骤l 计算所有的f = 而d j - d ( v f ，j f 21 ，2 ，刀，届厚) ； 假定落在( 0 ，1 ) 内的句共有s - 1 个，设它们是 0 a l j - l 占，则算法结束； 若t s ，则计算舭，) = 弓+ 历a t ，j f = 1 ，2 ，刀 按e d d 规贝0 得到7 t ( r ) ； 计算m f ) = m a x l ，( a t ) ij = l ，2 ，玎) + e ，； 转步骤4 ； 步骤4 若尺勘 d k ，转步骤5 ； 步骤4 若七= 力，则”= ill ，算法结束； 若七 疗，则c h l = c k + p h l ，b = bu j k + j ) ，k _ - 后+ l ，转步骤3 ； 步骤5 计算a = m a x 切i 巧b ) ，则l = l u “) ，b = b “) ， 若k = 疗，则“= i l i ，算法结束； 若七 以，则q = q a ，转步骤3 可见，m o o r e 算法是一种基于e d d 序的算法于是沿用问题( 2 1 ) 的方法， 我们首先将区间【0 ，1 1 分成若干个e d d 序不变左闭右开区间 缸l ，d ( k - - 1 ，2 ， j ) ，然后再对问题( 2 2 ) 在任意一个e d d 序不变区间上进行讨论 记m i n ( u a a ) ) 表示当工件易( = 1 ，2 ，胆) 的实际交货期取纵) = 巧+ 历时 的最小误工工件个数问题，同时也表示用m o o r e 算法求解得到的最小的误工工件 个数 定理2 2 1对于一个给定的k ( 七= l ，2 ，s ) 以及是 缸l m 上一个给定 点，设问题1i 纵) = 弓+ 耻l 的目标值m i n c e u a a ) ) = u k ( a ) = u ，则，3 充分 小的正数匈，使v 毋0 占痂，有i i l i n ( 姒+ 谚) = 甜 证明记s 2 ，) 表示在求解问题面n ( 啄) ) 中，m 。r e 算法的 判断是否误工过程中，发生误工时的工件依次所组成的集合；并记l 2 以，厶， 9 几个不同参数可控的排序问题的讨论 第二= 章交货期可控的排序i b i s ( p 1 ) ) 表示所有依此确定的误工工件集合，记s g = 1 ，2 ，s q ( ，i ，止一，力1 ) ，b = 1 ，2 ，- ) 、们，办，力i ( s q - i 略，( ) ( g = = 1 ，2 ，z ，) ， c j ( ) = 只吃( ) ( s o 1 j 略，( + 岛) 2 略，+ ( + 岛) & ( 9 2 1 2 ，此 显然， c j ( + 岛) = 见吒( ) d j ( a + c o ) ( s v 1 j s q ，g = 1 ，2 ，砧) ，句 a 一( ) 即：可以取。 0 l i n 竺 & - i 9 21 ，2 ，材 从而，对v 占：0 吃( ) 易= c j ( + s ) ( s v 1 y 0 ，v 0 s e 0 ，有m i n ( z 劬( a - e ) ) + 1 证明设俨【兀( 1 ) ，7 c ( 2 ) ，7 c ( n ) 】是对应于问题m i n ( x u ，( ) ) 的最优排序，其中b = 以( 1 ) ，以2 ) ，以( m ) ) 为按时完工的工件集合，且有 以( 1 ) ( ) t ( 2 ) ( ) s s t ( 嚣，) ( ) 则c ( 宁) ( ) = 圭以( ) 以( 。) ( ) ：以( 们+ 展( 。) ( 口；l ，2 ，刀以) 以( j ) = m a x 以( g ) i 以( g ) b ) ( 1sis 刀甜) 构造一个新的子序【7 c ( 1 ) ，n ( i - 1 ) ，7 c ( f + 1 0 几个不同参数可控的排序问题的讨论第二章交货期可控的排序问题( p 1 ) 1 ) ，7 【一“) 】，并将以( f ) 移到后面去取充分小的正数白满足： c ( 一白) = p j j g m j , ，( l = 乃一办( f ) e b = c ( g ) ( ) 一办( j ) ( g ) + 展( g ) ( 一毛) 哗鲢糍著趔 因此可以取氏 m i n 岛i g l ，2 ，理一“) f ，则对v s ：0 s 岛有 c ：r ( g ) ( 一f ) 以( 们( 一s ) q 1 ，2 ，刀一材 磅 所以存在一个工件的加工次序使其前部工件 以( 1 ) ，以( - 1 ) ，以( ，+ i ) ，以( 肿) ) 均 按时完工，所以m i n 伍姒- 勘甜+ 1 口 由定理2 2 1 和定理2 - 2 2 ，我们可以将每一个e d d 序不变区间【缸l ，蛐( 七= l ，2 ，进一步分成若干个小区间【七- l ，d = 【七- l ，趣，1 ) u 【七f i ，七，- 2 ) u u 【& 1 ，k o ) u 【柚，酗，并记雠l = 缸t 则： 若当a 【赴o ，o 时，记相应的m i n ( 啄) ) = “；那么，当a 【七，l ，a u o ( f = 2 ，3 ， ) 时，m i n ( e 姒9 ) = 矿+ z 从而问题( 2 2 ) 的求解转化为s 个e d d 序不变区间【七1 ，的上的子问题，而 每个子问题等价于求解r a i n ( 甜4 - z ) + e 氏，i 七= 1 ，2 ，j ，z = 2 ，3 ，t ) 在e d d 序不变区间【a k 1 ，0 被分成的小区间【a 七；- 0 ( ，= 1 ，2 ，) 后， v & e 【缸，m o - o 有而n ( 啄) ) 不变，故我们不妨称小区间【蛐札，i ) 为误工数不变 区间那么，问题( 2 2 ) 的求解关键在于找出这些误工数不变区间的左端点我 们给出一个类似于张峰的修正m o o r e 算法m m i l l 】 算法【i l 】m m ： 步骤1将工件按e d d 序标号，即d l 杰s 磊 几个不同参数可控的排序问题的讨论 第二章交货期可控的排序问题( p 1 ) 步骤2c t = p l ，令后= l ，b 。= 肌) ，l = 9 步骤3 若q 喀，转步骤4 ；若c k 反，转步骤5 步骤4 若k = 刀，则“= ll i ，算法结束： 若k 刀，则l = c k + 胁l ，b = b u 几1 ) ，| = 七+ l ，转步骤3 ； 步骤5 计算力= m a x 锄l 石b ) ，则l = l u 仉 ，b = b 仙) ， 若k = 刀，则 = i l i ，算法结束； 若k 0 ，有 m i n ( z u j ( a 一回) 0 。 证明 用算法m m 求解问题耐n ( 彰( ) ) 在求解中，i g s 2 以，) 表示每一次对剩余工件的e d d 序判断是否有误工工件时排在第一个的误工工件 所依次组成的工件集合，相应地，记l 2 以，叱，) 表示依次所确定的误工 工件的集合，记s 叮= 1 ，2 ，s q 、 ，l ，止，矗1 ) ，b = l ，2 ，) 、u i ，丘，矗1 ) ( s q 1 - ， 曲) ，这样 q ( ) = p ，( ) = + 色 ( g = l ，2 ，“。) ， i e s q q ( ) = 只 嘭( ) = + 岛 ( 廿l ， 曲，g = l ，2 ，甜) e 上 取充分小的正数，同时满足 q ( 一s ) = 只 a j ( a - s ) - - d j + 局( 占) j e ( 如1 0 ，有m i n ( z 啄a - 司) = 甜 口 根据定理2 2 3 显然可以得到下面的结论： 定理2 2 4 若对于e d d 序不变区间【b l ，d ( 七= l ，2 ，s ) 上的某个而言， m i n ( 啄) ) = 材，且m i n ( 彰( ) ) = 材+ l ，则这个就是某个误工数不变区间的 左端点 于是，我们先给出一个求解给定e d d 序不变区间【如l ，d ( 15 ksj ) 上问 题( 2 2 ) 的方法 算法2 2 1 步骤1 将工件按e d d 序标号，即：4 ( o ) 吐( o ) 以( o ) ( a k - l a o 棘l ，转步骤2 ； 如果as “，转步骤4 若甜 a k - l ，令m = 聊+ 1 ，转步骤2 ； 如果a s k l ，转步骤4 步骤4 计算m i n ( ”+ ，) + e a t , 4 ，= 0 ，1 ”，肌 = r 上述算法是我们对文 1 1 1 算法3 1 修正步骤2 得到的，易知其计算复杂性为 o ( n 4 ) 下面，我们以算法2 2 1 为子算法，得到求解问题1i 水) = 弓+ 厚l + e 的算法如下： 算法2 2 2 步骤l 计算所有的= 而d , - d , ( v 坷，f ，j 2 l ，2 ，行，届历) 假设满足条件的值有s 1 个，即 o l 缸l j ，则算法结束 步骤4 若f k f ，则，= 凡，a = a k 。，七= 七+ l ，转步骤3 ； 若r 之f ，则七= 七+ l ，转步骤3 算法复杂性分析：该算法中至多有矿个e d d 序不变区间，故至多次调用算 法2 2 1 0 ( n 4 ) ，所以算法2 2 2 的计算复杂性为o ( n 6 ) 1 4 几个不同参数可控的排序问题的讨论 第三章带有学习效应的加工时间可控排序i h - j 题( p 3 ) 第三章带有学习效应的加工时间可控排序问题( p 3 ) 在某些生产实践中，工人连续j j n - r 相同或类似的工件时，被加工的工件越靠 后安排加工，所需的加工时间越少这种现象称为学习效应”b i s k u p 2 7 1 最早提出 了具有学习效应的排序模型跏= 矿，其中厅，口卯分别表示工件以的正常加 工时间、加工位置和学习效应因子在b i s k u p 模型的基础上，不同的学习效应模 型相继被提出：g u r m o s h e i o v 和j e f f r e y b s i d n e y l 2 8 1 提出了与工件有关的学习效应 模型办= 矿，其中a j o 是工件西的学习效应因子：d i r k b i s k u p 和d i r k s i m o n s 【2 9 提出了模型办= 吲1 咖，其中0 x l ，s 为标准学习率，即有a = l 0 9 2 s ；王吉 波等3 0 】提出了模型跏= p j m - ( 1 一m ) r a ，其中o 列s 1 为常数，唧k u o w h 和 y a n g d l 1 3 1 1 提出了一种新的学习效应模型：工件在第，个位置上加工所需的时间 与排在其前面，- 1 个位置上工件的加工时间有关的情况：跏= 以l + p i l l + + p 【，1 1 ) 口，其中p t i ，1s f5 ，一1 为第f 个位置上加工工件的实际加工时间程明宝【3 2 】 提出了另一种新的学习效应模型旨数模型：办= 历矿1 ，其中0 as1 为常数 2 0 0 8 年b i s k u p t 3 3 1 对带有学习效应的排序问题进行了综述 虽然针对学习效应排序问题的研究只是近些年的事，但却取得了丰富的成果 1 3 3 】而将t 学习效应和“可控结合起来的排序模型研究尚不多见，余英等【3 4 1 研究 了问题ll 办= 川1 力l ( p l 乃+ p 2 e + p 3 d + p 4 q ) + 砸) ，0 冬x 0 ，u j ，乃，厂，a 分别表示工件以的，正常加工时间、当获得单位资 源时的加工时间压缩量、获得的资源量、可以获得的资源量上限、获得的加工位 置、和学习效应因子，且满足历一哆五，之0 我们讨论如下的两类( p 3 ) 可控排序问题： 1 i 办= 劬一吩动，吩qi ( 3 1 ) 几个不同参数可控的排序问题的讨论 第三章带有学习效应的加工时间可控排序问题( p 3 ) 1 l 跏= 锄- a j u j ) r = ，z u j _ q1 q( 3 2 ) 其中q 之0 为给定的常数 记r 维向量甜= ( u l ，2 2 ，) 是工件集j 的一个资源分配方案，记兀= 阢l ， 砣，】是工件集j 的一个排序，分别记u ，n 为”和，【的可能取值的全体， 则问题的求解就是要寻求( ”。，兀) ( u ，1 - 1 ) 使得完工费用目标函数达到最小 3 1 问题1i 办= 劬- a j u j ) r d ，吩5qig 甑 引理3 1 问题1i 跏= 矿ic n 越的最优排序可以按乃非降排列得到，即s p t 序为最优序【3 5 】 对于问题( 3 1 ) ，当q = 0 时，由引理3 1 可知，按照力非降排列即为最优序， 且甜= o 当q 之句时，由引理3 1 易知，按照历乃句非降排列即为最优序， 且掰= ( 五i 一，玩) 故我们一般假设0 q a o ( 2 ) 4 ( 。) ， 所以兀+ 所对应的最优资源分配“+ 就应满足按照。的次序优先将各工件的资源上限 量分配资源给各工件直至资源用完，否则： 假设在问题( 3 i ) 最优排序兀的资源分配”= ( “l ，眈，) 中存在两个工 件得到的资源量既不是o 也不是它们的上限，即 甜= ( z 0 ( i ) ，t t o ( 2 ) ，一，( ) ，0 ，0 ) ( 2 h 刀) 且：3 i ，j f 【1 ，h l ，i 歹，0 纵删) 以( n ，0 ) 0 ，有f b 故资源分配方案甜更优 q = 似 口 “ n 凸坌至同参塑旦墼的排序四耍的讨论第三章带有学习效应的加工时间可控排序问题( p 3 ) 若( ，) + 甜f ( 力以( ，) ，我们如下调整资源分配，得到“- - ，b 2 ，u 。) ： 材口( i ) 2 ( i ) 它f ，j ；( ，) 2 ( j ) ； 甜口( ，) 2 ( ，) + ( ) 一( ，) 其中，g jo u 口( j ) 五口( ，) ，o u 口( d 疗口( 知，o ( ) + ( j ) 五。( ，) + 五口( ) 即o ”二r ( ) = “口( 1 ) + 材盯( 力一五旷( o 五口( ) ，贝0 h = 也( ) 吃( t ) = 以( i ) 甜：( 女) + ( 以( f ) 嘭( f ) + 以( ) 嘭( ) ) k - i l ， = 4 ( ) ( ) + ( 4 ( f ) 屯( ) + 以( ) 呓( ) ) i 所以 一丑= 【4 ( 1 ) 呓( i ) + ( 以( f ) 嘭( j ) + 以( ) 吒【p 卜【心( ) “m ) + ( 以( ) ( ) + 以( ，) ( 】 = 【厶i ，) + ( 4 a ，+ 4 彤) u o ( o + 4 哪，) 一4 哪，屯聊) 】一【以”+ m u o ( o + 如，) f 力) 】 ，f t ，j = 厶，) 屯，+ 以，) ，) 一如) 以( - ，一以，) ，) = ( 以( f ) 一以( ( 屯( j ) 一甜口( ，) ) 因为4 ( 0 2 4 ( d ，0 ( d 以( o ，有b 故资源分配方案豁更优 所以在最优排序的最优资源分配中，工件所获得的资源量或者是零或者是其可获 得资源量的上限，至多存在一个工件的资源获得量介于零和其上限口 下面利用问题( 3 1 ) 最优解中资源分配的性质对问题( 3 1 ) 的一些特殊情况 作讨论 当乃= p ，乃= 口时，问题( 3 1 ) 的化为： 1i 办= ( 夕一口材) ，口，吩sq i ( 3 1 1 ) 定理3 1 1 对于问题( 3 1 1 ) ，先按五，非增序排列可得到最优序兀，再按照该 次序依次优先分配资源量上限直至资源用完，即可得到相应的最优资源分配l ， 证明设兀为工件集j 的任意一个排列，则 1 8 几个不同参数可控的排序问题的讨论第三章带有学习效应的加工时间可控排序问题( p 3 ) 月打 c 懈( 万) = 几( ，) = ( p 一口) - ，口 肘r l = p 口- a t j 口“删) j = l= i = p o 口+ 2 口+ + ，2 口) 一口j f 8 “，( ，) = l 由于p ( 1 4 + 2 口+ + 矿) 为定值，要极小化o ( 万) 等同于极大化口( ) ，所以 要按照( 力非增排列而由性质3 1 可知，最优资源分配为吩20 或吻2 句，至多 有一个吩介于0 与乃u = 1 ，2 ，刀) 所以应按照以非增排列得到最优序f ，且 其相应的最优资源