（运筹学与控制论专业论文）加工时间恶化的排序问题的讨论.pdf

摘要 本文研究加工时间恶化的单机排序问题。所研究的模型包含两类：工件加工 时间由于开工时间的延迟而恶化的排序问题被称为第一类加工时间恶化问题；工 件加工时间由于加工顺序的延后而恶化的排序问题被称为第二类加工时间恶化 问题。 对于第一类加工时间恶化问题，本文讨论了加工时间随开工时间线性增加的 情形。我们证明，在某些特殊情况下，这类问题是多项式时间可解的。在无法证 明是否为多项式时间可解时，我们也给出了相应的多项式时间近似算法。 第二类加工时间恶化的最大完工时间和总完工时间问题是多项式时间可解 的。我们证明，这类问题等价于指派问题，从而可用匈牙利算法加以解决。 关键词：排序；加工时间恶化；匈牙利算法 a b s t r a c t t h i sp a p e rd i s c u s s e ss c h e d u l i n ga b o u td e t e r i o r a t i o no fp r o c e s s i n g t i m eo ns i n g l ep r o c e s s o r i ti n c l u d e st w ok i n d so fm o d e l ：i ft h ej o b p r o c e s s i n gt i m ei sa ni n c r e a s i n gf u n c t i o no f i t ss t a r tt i m e ，i ti sc a l l e dt h e f i r s tk i n do fd e t e r i o r a t i o np r o b l e m ；i ft h ej o bp r o c e s s i n gt i m ei sa n i n c r e a s i n gf u n c t i o no f i t sp o s i t i o ni nt h es e q u e n c e ，i ti sc a l l e dt h es e c o n d k i n do f d e t e r i o r a t i o np r o b l e m a st ot h ef i r s tk i n do fd e t e r i o r a t i o np r o b l e m ，t h el i n e a ri n c r e a s i n g p r o c e s s i n gt i m ef u n c t i o no fi t ss t a r tt i m ei sd i s c u s s e di nt h i sp a p e r i ti s p r o v e dt h a tt h ep r o b l e mi sp o l y n o m i a lt i m es o l v a b l ei ns o m es p e c i a l c a s e s w h e nt h ep r o b l e mc a n tb ep r o v e dt ob ep o l y n o m i a lt i m es o l v a b l e ， p o l y n o m i a lt i m ea p p r o x i m a t i o na l g o r i t h mi sg i v e n t h es e c o n dk i n do fd e t e r i o r a t i o np r o b l e mt om i n i m i z em a k e s p a na n d t o t a lc o m p l e t i o nt i m ei sp o l y n o m i a lt i m es o l v a b l e i ti sp r o v e dt h a tt h e p r o b l e mi si d e n t i c a lt oa s s i g n m e n tp r o b l e m ，s oi t c a nb es o l v e db y h u n g a r i a nm e t h o d k e y w o r d ：s c h e d u l i n g ；d e t e r i o r a t i o no f p r o c e s s i n gt i m e ；h u n g a r i a n m e t h o d 第一章引言 1 1 排序问题概述 第一章引言 1 1 1 排序问题 排序论作为运筹学的一个分支，有着深刻的实际背景和广阔的应用领域，它 广泛应用于管理科学、计算机科学和工程技术等众多领域。例如，建造一座公路 大桥需要安排多种不同的人员：有的负责勘测和设计；有的承担具体工程项目， 我们还可以进一步细分其工作内容，这就需要给参与建造大桥的各类人员根据工 程要求安排一个恰当的工作顺序。若再考虑施工设施、材料和气象等因素，其最 优施工顺序可能不会轻易获得，且由于工程要求不同，对应的最优施工顺序也不 尽相同( 有些需要工程尽早完工；有些需要机器空闲时间时间少些；有些则以经 济效果作为衡量指标) 。又如：工厂里的各类机械加工、计算机程序的执行调度 以及机场的各种要素调度等等。凡此种种，有的可凭经验处置，有的则需要事先 周密筹划，甚至用到排序理论和算法。此时，各种属于组合优化的排序问题及关 于它的理论和算法便应运而生。因此，研究排序问题具有很大的理论意义和现实 意义。 概括地说，排序是利用一些机器( 如设备、计算机等资源) ，在执行某些任 务( 如产品加工、程序运算等) 时在某些限制条件下( 如工件的到达时间、完工 截止时间、优先约束、机器对加工时间的影响等) ，寻找一最优加工方式使某或 某些目标函数达到最优。它是“投入最少，产出最优”的一种组合优化过程。由 于排序问题最早是在机器制造领域中提出来的，因而排序问题各要素的描述沿用 了机器制造中的术语，即机器( m a c h i n e ) 、t 件( j o b ) 和目标函数( o b j e c t i v e f u n c t i o n ) 这三要素组成了各种排序问题。 排序问题先由c o n w a y 等人( 1 9 6 7 ) 首创四参数法表示，而后由g r a h a m 等人 ( 1 9 7 9 ) 改为至今仍在沿用的下述三参数法表示：口i iy 。其中，口域表示机 器的数量、类型和环境；口域表示工件的性质、加工要求和限制，资源的种类、 数量和对加工的影响等约束条件；，域表示要优化的目标函数。关于排序问题这 加工时间恶化的排序问题的讨论 三个域的具体内容请参看 1 2 。 1 1 2 排序类型 排序问题可以分为排序的理论部分和应用部分。其理论部分又可分为经典排 序和现代排序。现代排序的特征突破了经典排序的基本假设，正逐渐成为排序研 究的主流方向。经典排序有四个基本特征： ( 1 ) 资源类型( 如加工工件的机器) 台机器在任何时刻最多只能加 工一个工件，且一个工件在任何时刻至多在一台机器上加工。作为推 广，有成组分批排序、同时加工排序、不同时开工排序和资源受限排 序等。 ( 2 ) 确定性决定排序问题实例的所有参数都是事先知道和完全确定的。 这一性质的推广有可控排序、随机排序、模糊排序、在线排序和半在线 排序等。 ( 3 ) 可运算性排序问题通常都是在可以运算和计算的程度上进行的。 若考虑实际应用中的情况和因素，那是属于应用排序问题，如人员排 序、智能排序等。 ( 4 ) 单目标和正则性( 单) 目标函数是工件完工时间的非降函数，即 所谓正则目标函数。这方面的推广有多目标函数、准时排序和窗时排 序等。 上述经典排序及其四个基本特征的推广( 即现代排序) 构成了排序的主要 内容和类型。 若要对排序问题分类，则有多种分法。如按静态( s t a t i c ) 和动态 ( d y n a m i c ) 、确定性( d e t e r m i n i s t i c ) 和随机性( s t o c h a s t i c ) 等可分成四 大类，甚至还有介于两者之间的。又如按机器分类，有单机( s i n g l em a c h i n e o rs i n g l ep r o c e s s o r ) 和多机( m u l t i p r o c e s s o r ) ，多机又可分为平行机 ( p a r a l l e lm a c h i n e ) 和专用机( d e d i c a t e dm a c h i n e ) 等。 1 1 3 排序问题的简短发展史 二十世纪5 0 年代，人们对一些简单的排序问题找到了一些简单最优算法， 2 第一章引言 其典型工作有三个：解问题f 20 c 一的j o h n s o n 算法( 1 9 5 4 ) ，解问题l | l k 的 b z 坂e a r l i e s td u ed a t ef i r s t ) 规则( 1 9 5 5 ) 和解闯题l l i 叶q 的j s 颅w e i g h t e d s h o r t e s tp r o c e s s i n gt i m ef i r s t ) 规则( 1 9 5 6 ) 。 基于5 0 年代一些简单算法的出现，许多人在6 0 年代投入对排序问题的研究， 期间出现了解问题li | u ，的m o o r e - h o d g s o n 算法( 1 9 6 8 ) ，该算法与上述三个 算法直至现在仍然是许多算法的基础。有些人想模仿5 0 年代出现的单纯形那样， 将排序问题化为整数规划来解。由于即使相对较小的排序问题化成整数规划也需 要非常多的o - l 变量和约束，而解整数规划的有效酸法迟迟未出现，因而进展不 大。还有些人转向各种启发式算法。总体上说，6 0 年代成果不多但发现了许多 问题。 7 0 年代随着计算复杂性理论( 由c o o k ( 1 9 7 1 ) 和k a r p ( 1 9 7 2 ) 二人开创) 的问世，大大推动了排序问题的研究。有些学者开始依据困难程度即计算复杂性 对排序问题进行分类，发现除为数不多的问题具有多项式时问算法( 户，外，大 部分为肛妇耐的，且从尸到 脚a 耐的过渡呈现明显的特点。这一时期，人们 已开始利用计算复杂性的有关理论对排序问题及其算法展开多种研究。整个7 0 年代，排序的研究成果颇丰。 基于7 0 年代的成果，8 0 年代对排序问题有了更深入和更广泛的研究。而9 0 年代，随着现代工业的发展，经典排序的模式己逐渐被突破，出现了各种各样的 新型排序，并不断吸引计算机科学、数学、管理和机械等方面领域的学者加入到 排序问题理论及应用的研究队伍中来。从1 9 5 4 年j o h n s o n 的论文( 普遍认为它 是研究经典排序问题的第一篇论文) 发表以来，至今全球已经发表排序论文两千 多篇，中外排序书籍达五十本以上。 在我国，对排序问题的研究较晚，二十世纪5 0 年代末只有一些宣传普及工 作。1 9 6 0 年，越民义先生编写了国内第一本排序理论讲义。到了7 0 年代，才有 人对这一问题开始研究。8 0 9 0 年代，搞排序的研究人数渐渐多了起来，且研 究内容日趋丰富，1 9 8 7 年国内出版了第一本排序论的专著排序的原理与方法 ( 陈荣秋) 。目前，排序问题的研究已经从经典排序的内容逐步扩展到现代排序 的各个方向，显示出一种新兴景象。 加工时间恶化的排序问题的讨论 1 2 本文所研究的问题 1 2 1 问题的背景 在经典排序中，工件的加工时间是一个常数，但在一些实际的排序问题中， 情况并非如此，工件的加工时间是可以变化的。例如，机器在工作了一段很长的 时间后，其运行速度会逐渐减慢，效率会变得低下。这种情况可以表述为同一工 件在后面加工比在先前加工所花的时间多，即工件加工时间恶化( d e t e r i o r a t i o n o fp r o c e s s i n gt i m e ) 。 本文所研究的就是在工件加工时问恶化的情况下，如何合理安排工件的加工 顺序，使得目标函数达到最优。 工件加工的先后可有两种方法来描述：工件开工时间的早晚和加工顺序的先 后。本文中，工件加工时间由于开工时间的延迟而恶化的排序问题称为第一类加 工时间恶化问题；工件加工时间由于加工顺序的延后而恶化的排序问题称为第二 类加工时间恶化问题。 另外，工件加工的难易程度也会对加工时间产生影响：越难加工的工件所需 要的加工时间也越长。本文中工件的加工时间有两个因素决定，即工件加工的先 后和加工的难易程度。 1 2 2 问题的模型 本文考虑的都是单机排序问题。设有n 个工件，工件集j = 1 , 2 ，n ) ；又有 集合“，口：，) ，其中a s 称为加工难度系数，表示工件i 的加工难易程度。用口。 表示这类工件中加工难度最低的，显然，在现实的问题中口。是客观存在的。 在第二章中，我们先讨论第一类加工时间异件异速恶化问题 1 l p 】( q ，t ) l c 。 其中，p l ( 口) = 鼢篡r k ( 1 + a m 儿表示加工难度她的工临 时刻开工所需要的加工时间，所有的工件在时刻“( t o o ) 2 _ 后2 n i 。 再考虑第一类加工时间异件同速恶化问题 4 第一章引言 1 i p 2 ( q ，f ) i c 一 和l l p d a , ，f ) l q 其中，p 2 ( d ，f ) = a , + b t , t o ) 之后加工。 在第三章中，我们讨论第二类加工时间恶化问题 i i p ( q ，川c 一 和 1 i p ( a j ，j ) l q 其中，p ( a 。，d 表示加工难度为a ，的工件在第，个加工时所需要的加工时问， p ( a ，j ) 分别是日，和，的递增函数。 在这一章的最后，给出p ( a ，) 的某些特殊形式时，相对应的目标函数的最 优排序。 加工时间恶化的捧序问题的讨论 第二章第一类加工时间恶化问题 2 1 概述 本章考虑加工时间线性恶化问题，即加工时间烈q ，t ) 为t 的线性函数，称 蔓丛：也为加工时间恶化速度。如果不同加工难度的工件加工时间的恶化速度不 a 同则称为异件异速恶化问题；不同加工难度的工件加工时间的恶化速度相同称为 异件同速恶化问题。 目前，关于异件异速恶化问题已经有了一些研究i 酬。【2 】研究了这种类型的 排序问题，假定工件i 在时刻r 开始加工的加工时间p ，= p ? + 口，f ，考虑最小化最 大完工时间的排序问题( 10c 一) ，作者给出的最优排序的条件是( p ? 屈，) 的非降 序。【3 】讨论了最小化总完工时间的排序问题( 10 q ) ，当每个工件的基本加工 时间( b a s i cp r o c e s s i n gt i m e ) p o 都相等时，最小化总完工时间的排序问题 ( 1 l i q ) 具有y 一型的最优排序。【4 】讨论了工件加工时间是简单线性恶化，即 工件i 在时刻f 开始加工的加工时间a = a , t 的排序问题，作者证明了最大完工时 间问题( 10 1 ) 、总完工时间问题( 1 q ) 、最大延误问题( 1 l i 乙) 以及延 误工件个数问题( 10 u ) 是多项式时间可解的。 在上述的成果中可以看到，工件加工时间随开工时间增加，且可无限增大， 这显得有些不符合现实情况。因此，下面两节考虑工件加工时问随开工时间增加， 但工件加工时间不是无限增大，而是有一个限制，在某时刻以后工件的加工时间 不再增大，e p ：自n 工时间的恶化趋向稳定。 2 2异件异速恶化问题 设有盯个工件，工件集j = 1 ，2 ，”) ，对应加工难度系数集合 口l ，口2 ，以) ， 用d 。表示这类工件栅工难蒯m 舡时嘲忙鼢至篓亿眈 第二章第一类加工时间恶化问题 t k ( 1 + 口一) 丁，所有的工件在时刻f o ( t o o ) 之后加工，f o 可以看作机器工作 了一段很长的时间后，其运行速度逐渐减慢，效率开始变得低下的时刻。工件i 的 完工时间为c ，设盯= ( a o ) ，盯( 2 ) ，盯( ) ) 是工件 1 , 2 ，n 的一个排序，则 c ( 1 ) = t o + a a 0 ) ，o = t o ( 1 + 口，( 1 ) ) c 。( 2 ) = c 0 ( 1 ) + a ，( 2 ) c 州1 ) = t o ( 1 + 口口( 1 ) ) ( 1 + 口，( 2 ) ) c ，( ”= f 。兀( 1 + 口，o ) ，( l - i ( 1 + a o ，) ) x ) t = l扭l tk c ，( “1 ) = “i - i ( 1 + 玎，( ，) ) + 口。( 女+ 1 ) 丁，( f 0 1 - i ( 1 + d ，( ) ) 置) k c 咖) = f o 兀( 1 + 口叩) ) + r 口巾) i = li = k + l ( 2 2 ) 我们讨论的目标函数是最大完工时间c 。= m a x g ，c 2 ，c 。，即要寻找最 优排序盯，使得c 麟( 盯+ ) = 呼c 眦( 盯) = 吵c 。 如t o k ，则工件i 的加工时间为a , t 是一个固定的常数，这是经典排序 n 问题。如果“兀( 1 + q ) k ，则我们所讨论的问题就是 4 中讨论的情况。因此， 月 我们总是假定f o k 。特别地，我们将排序盯中第七个工件 i 一1 盯( _ j ) 称为排序盯的临界工件，如果工件仃( 七) 满足c ，) = f 0 1 7 i ( 1 + 口，( ，) ) x ， i g ”= “兀( 1 + 口呻) ) x 。 i ；l 对于任何排序盯= ( 盯( 1 ) ，盯( 2 ) ，盯( 玎) ) ，如果a ( k ) 是排序盯的临界工件，则 由式( 2 2 ) 可知，在排序o r 中前k 一1 个位置上的任意排法都不会改变第k 1 个工 l - l 件的完工时问g ( = f 。兀( 1 + a a o ) ，当然也就不会改变第甩个工件的完工时间； 7 加工时间恶化的排序问题的讨论 同样在排序盯中后，一k 个位置的任意排法都不会改变第 个工件的完工时间。 于是我们有下面的结果： 引理2 1 任一最优排序盯经过重新排列总能得到排序盯，盯也是最优排 序，且满足 ( 1 ) 口口( 1 ) 口口( 2 ) n 口( 一1 ) ， ( 2 ) 口，( ) 口，2 ) 口，( ) 。其中盯( t ) 是最优排序盯的临界工件。 从式( 2 1 ) 中可以看到，当k = r 时，工件i 的加工时间持续恶化一段时问后 趋于稳定，但稳定后恶化程度未见好转；当丁 k 0 + a r ) t 时，工件i 的加工 时间恶化趋于稳定后，恶化程度比稳定前略有好转。上述两种情形显然有本质上 的区别，因而我们将对两种情形分别进行讨论。 2 2 1k = t 的情形 我们讨论此时最优排序的性质。引理2 1 分别给出了最优排序中临界工件前 后的工件问的关系。下面我们讨论最优排序中，临界工件与其前后工件的关系。 引理2 2 如果盯= p ( 1 ) ，盯( 2 ) ，盯0 ) ) 是最优排序，工件仃( 七) 是临界工件， n 必 ：f fa ，( i ，a 口( t “) 。 证明：用反证法。 设口叫) 口础+ i ) ，令m = f o 兀( 1 + 口巾) ) ，显然肘 丁。交换工盯( 七) 和盯( 后+ 1 ) 的位置，n n - - n n 黼，g a = j = a ，( ” 0 这与盯是最优排序矛盾。证毕。 引理2 3 任一最优排序经过重新排列总能得到排序盯，工件a ( k ) 是临界工 件，满足口，( ) 口，1 ) ，且仃是最优的。 8 第二章第一类加工时间恶化问题 k - 2 证明：设排序疟为最优捧序，且q ( i - 1 ) 0 ( 2 3 ) ，= l 这与万是最优排序矛盾。 i 2 如果，。( 1 + 以( i ) ) l q ( 1 + 口巾) ) r ，交换万( 七一1 ) 和石( j i ) 得符合条件的排序盯； j = 1 如果( 1 + 口椰) ) 兀( 1 + 口砷) ) = t ，则由式( 2 3 ) 知万也是最优排序，视万( 七一1 ) 和 y t ( 七) 的关系而决定是否交换，可得符合条件的排序盯。证毕。 利用引理2 1 、2 2 和2 3 ，我们易得以下结论： 定理2 4 问题1 i p l ( a ，f ) i c o 当k = t 是多项式时间可解的，按工件加工 难度系数h ，a ：，a n 从大到小排列是其最优排序。 2 2 2 t r 时， 必t m a o ( ”a o ( ) 。 否则交换a ( k ) 与盯( 七十1 ) 的位置，可得一更优的排序，这与盯是最优排序矛盾， 盯即是符合要求的排序万。当吖= t ，视a ( k ) 与a ( k + 1 ) 的关系决定是否交换， 可得符合要求的排序石。定理的后半部分显然成立。证毕。 定理2 6 如果问题1 i p l ( 口。，f ) i c 一在丁 k ( 1 + ) 丁时的最优排序o r i t - i 中，始终有m = f o 丌( 1 + a 0 0 ) ) t ，则按工件加工难度系数“，口2 ， 从小到 大排列是其最优排序。 证明：任取一最优排序，相邻两工件加工难度系数不是从小到大排列，就交 换位置，由式( 2 2 ) 的讨论和定理2 6 知，这种交换不会破坏其最优性，从而保 证交换过程中m t 。反复利用( 2 2 ) 的性质和定理2 6 ，就可得到按工件加工 难度系数溉，口：，a n ) 从小到大排列的最优排序。定理得证。 i 一1 2 ) 存在最优排序盯，使得m = f o 兀( 1 + ( ，) ) 丁 i = 1 我们用巳表示问题1 i p l ( 口，r ) l 气在r k ( 1 + 口m ) r 时的最大完工时 间，c ：表示问题1 i p l ( 口，f ) l c 一在足= t 时的最大完工时间。显然，对任何排序 盯都有c k ( 盯) c 一2 ( 盯) ，因而可以得到 c k ( f ) = m i n c ( f ) m i n c 二( 盯) = c ：p ) ( 2 4 ) f口 记石为按工件加工难度系数 口l ，口：，a 。) 从大到小排列的排序，万( 七) 为问题 1 i p ( a ，f ) i c 一在t k ( 1 + 沙时的临界工件。 定理2 7 排序万为问题l a ( 口，f ) i c o 在丁 k ( 1 + 口劬沙时的最优排序， 或者为近似最优，且误差情况界小于l + 口m 。 证明：如果m = t o n ( 1 + 口巾) ) t ，则有c 二( 石) = c 怎( 石) ，由定理2 4 知 l o 第二章第一类加工时间恶化问题 排序石为问题1 i p l ( q ，t ) l c 一在k = t 时的最优排序，结合式( 2 4 ) 得到排序石也 是问题l f a “，t ) l c m 在r 丁，x ( k 1 ) 为问题l i p ( a ，f ) i c 一在k = t 时的临 i = 1 界工件，则司得 竺二! ! ! 竺二! ! ! ：竺二! ! ! ：1 + 二! ! ! 二二! ! ! c l ( ) 一c l ( 盯+ ) c l ( 万) 1 c l ( 刀) ，o 兀( 1 + q 1 ) ) 一t o 兀( 1 + ( j ) ) 一( 。， ( 1 + a x ( k ) ) r 小竺塑兰尘：! 。攀坐型幽 = l + 兰l _ 一 1 + 竺芏二_ 二竺二二 ( 1 + a n - ( k ) ) r( 1 + 口，( i ) ) r = 1 + a 枷a x c k ) 1 + 口n 血 1 十z ( t ) 定理证毕。 综合情况1 ) 和2 ) 可知，按工件加工难度系数如，口：，a 。 从大到小或者从 小到大排列，两者取其优，就能得到1 i a 0 ，t ) i c 一在t k ( 1 + 口m f 时的最 优排序或者近似最优，且误差情况界小于1 + 口。 实际上，我们可以假定口 1 。如果口曲1 ，则有口自“t o ，这就是说， 加工一个最简单的工件所花时间不少于机器从开始工作到效率降低的时刻。若加 工时间恶化到这种地步，那还不如停机休息一段时间再开工来得更有效率一些， 这种情况不在我们的考虑范围之内。 2 3异件同速恶化问题 设有力个工件，工件集t ，= 1 , 2 ，卵) ，对应加工难度系数集合 口。，口：， ， 加工时间p ：( 口j ，f ) = 三+ + 6 b l t , t f o ) 之后加工。 如果“量，则工件f 的加工时问为口，+ 6 r 是一个固定的常数，这是经典捧 序问题。因此，我们总是假定“ k ，特别地，若存在排序盯中第k 个工件满足 c ( ) c z ( ，) ，c ，e 。 证明：c 巾) g ( j ) 显然成立。令c ( h ) = m ，分情况讨论g ( j + 1 ) 和q ( 1 + 1 ) 的 关系。 ( 1 ) 巳( f ) 0 ( 2 ) q ( ，k ，c ( h ) - - m x ，即盯( f ) 为临界工件。若交换盯( d 和盯o + 1 ) 后，c r ( i + 1 1 不为临界工件，则有 c ( ，+ 1 ) 一g ( ) = 口州n + 6 i f + d 。( j + l ，+ b t 一口口i 川) 一b m a 口( ，一b a 口j + 1 ) + ( 1 + 6 ) 彳】 = b t a 。( ，+ 1 ) 一( 1 + 6 ) ，】 此时，e ( o = 口。( 1 + 1 ) + ( 1 + 6 ) 肘 g “1 ) 。若交换仃( f ) 和 盯o + 1 ) 后，a ( i + 1 ) 为临界工件，则有 c o o + 1 ) 一c f ( + 1 ) = a ，) + 6 1 ，+ 口，( + i ) + b t a 。1 + i ) 一b m a ，o ) 一b t = 0 ( 3 ) g ( ，_ 1 ) = m k 时，显然q ( ) = c ( h 1 ) 。 1 2 第二章第一类加工时间恶化问题 定理证毕。 给定一个捧序仃= p ( 1 ) ，叫臣吼，盯( 砌，最大完工时间c i 。( 田= c 1 ) ，总完 工时间c j = c 帕) ，利用引理2 8 和2 9 ，我们得到： j = l 定理2 1 0 问题1 l p 2 ( 口，t ) l c 麟和1 i p 2 ( a , ，f ) i e 是多项式时间可解的， 按工件加工难度系数“，口：，口。) 从小到大排列是其最优排序。 加工时间恶化的排序问题的讨论 第三章第二类加工时间恶化问题 3 1 概述 本章讨论如下问题 1 i p ( a 。，川c 一 和 1 i 烈q ，_ ，) | c ， 其中，p ( q ，) 表示加工难度为a ，的工件在第_ ，个加工时所需要的加工时间。为 了能够准确表述第二类加工时间恶化问题，工件加工时间函数p ( a ，力的必须满 足以下条件： p ( a ，1 ，_ ，) p ( a j 2 ，_ ，)当且仅当a z l q 2 ( 3 1 ) p ( a ， ) p ( a 。， )当且仅当 办 ( 3 2 ) 条件( 3 1 ) 表明处于同一加工顺序的工件，加工难度系数越大所需要的加工 时间越多。条件( 3 2 ) 表明同样加工难度的工件，加工顺序在后所需要的加工时 间不少于加工顺序在前的加工时问。这两个条件合在一起就满足了第二类加工时 间恶化问题最基本的假设和要求。 我们先就加工时间函数p ( a ，) 的一般形式展开讨论。 3 2 函数p ( a 。_ ，) 的一般形式 3 2 1 问题1 l p ( a ，_ ，) i c 一 设盯= ( 盯( 1 ) ，盯( 2 ) ，盯( ，z ) ) 是工件 1 ，2 ，刀) 的一个排序，我们讨论的目标函 数是最大完工时间c o = m a x c ，c 2 ，g ) ，即要寻找最优排序仃，使得 c u ( o ) = m i n c 一( a ) 2m i n c ，( 将g ( 。) 用p ( q ，d 的形式表达，则有 1 4 第三章第二类加工时间恶化问题 i 巳( 。) = c ：n _ 1 ) + p ( 口。( 。) ，刀) = c 口( 。一2 ) + p ( 口。( 。一1 ) ，n 1 ) + p ( 口口( 。) ，拧) = p ( a 螂f ) = x v p ( a ，) ( 3 3 ) 鼽以= 器嚣m 川一珈在排序汛球放在第，个位置当且 仅当x ，= l 。可以看到，一个排序盯和一组乃是一一对应的因此，问题 l p ( a ，川c 。与如下整数线性规划问题等价： p ( a ，j ) x ， 豇= 1 ，i = l ，2 ，刀 ，= l x g = l ，j = l ，2 ，行 = o 或l ，i , j = 1 , 2 ， 上述整数线性规划问题是典型的指派问题，求解此类问题有匈牙利算法【5 1 。 于是我们得到： 定理3 1问题1 ip ( q ，_ ，) ic 一是多项式时间可解的。 下面运用匈牙利算法求解问题1ip ( a j ，力lc 一。 作加工时间矩阵名。，其第f 行第_ ，列元素只= p ( a ，_ ，) ，对矩阵p 做以下运 算： l 、每行减该行最小数。 2 、每列减该列最小数。 3 、从含0 最少的行( 或列) 开始，圈出一个0 ，划去其所在的行或列。 4 、重复步骤3 ，直到所有的0 划去或圈出为止。 加工时间恶化的排序问题的讨论 5 、如果已经圈出疗个0 ，即得到最优排序，否则转步骤6 。 6 、对没有圈0 的行打幸号，对打宰号的行上所有o 对应的列打宰号，再对打宰 号的列上所有圈0 的行打书号，直到打不出新的$ 号为止。 7 、将没有打术号的行与打木号的列划上直线，这是覆盖所有0 的最少直线。 8 、找出没有被直线覆盖掉的所有元素中最小者，记为p ( a ，_ ，) 。 9 、将打木号的行减去多( q ，d ，对打木号的列加上( 口，d 得一新矩阵，返回步 骤3 。 所有被圈出的0 在矩阵中所处的位置就指明了问题的最优排序。例如，被圈 出的0 在第纤f 第_ ，列，说明工件i 在第，个加工。 例：求解排序问题1 i p ( a ，川c 。，其中n = 4 ，口4 a 3 0 这与盯是最优排序矛盾。定理得证。 2 )