（基础数学专业论文）平行批在线排序问题.pdf

摘要 在线排序是现代排序的一个重要组成部分在经典的离线排序问题中，我们总是假 设决策者在做决策之前已经获知所有工件的信息事实上，在实际生产过程中很多时候 决策者在没有获得所有工件信息之前就必须做出决策于是出现了在线排序人们通常 把在线排序问题分为三类： 列表在线( o n l i n e - l i s t ) ：工件是排成一个序列到达的前面的工件必须被安排到机器 上后面的工件才会被释放出来工件一旦被释放，工件的信息即被获知工件的安排方 式一一日确定就不可以再改变 时间在线( o n l i n e - t i m e ) ：丁件是随着时间到达的前面到达的工件即使没有被安排 也不会影响后面工件的到来工件的信息在工件的到达时刻才能获知，工件在到达之前 不可以被安排工件被安排之后不能再改变 不可预测的时间在线( o n l i n e - t i m e - n c l v ) ：工件是随着时间到达的工件的加工时间 只有在工件完工之后才可获知，而在工件的到达时刻无法得知或预澳i ( n o n c l a i r v o y a n c e ) 工件在到达之前不可以被安排，一旦安排就不可以改变 在本学位论文中，我们主要研究的是时间存线排序问题我们考虑一台或两台平行 批处理机的排序模型平行批处理问题起源于半导体制作工业、制鞋业、金属铸造工业 等方面在后文中我们将会详细叙述一台平行批处理机在不超过批容量的情形下，可 以同时加工多个上件批的加工时间是由该批中最长的工件确定的同一批的工件具有 相同的开工时间和相同的完工时间在本文所研究的排序模型中，我们均假设批容量是 无界的，即机器可以同时加工任意多个工件同时，我们还假设存在多个不可相容的工件 组或者假设批是允许有限次重启的 不可相容的工件组是指，每个t 件可能属丁不同的组，组与组之间是不可相容的( 比 如，不同的组具有不同的化学性质) 因此，不同组的工件不町以被安排在同一批加t 考虑到重启是一种有限的资源或者重启会带来一定的负面影响，因此我们提出了有 限次重启的概念批允许有限次重启是指，如果一批中不包含有已经被重启过的工件，就 可以被重启批重启之后，批中的工件被释放出来，成为各自独立的未加工工件再次加 工被重启过的工件时必须重新开始加工，并且加工过程不可以被扣断直到其完工 重肩与中断是两个不同的概念中断的工件再次被d n l 时是接着已经被加工的部分 继续加工的；而重启的工件再次被加工时是从头开始加工的，前面已经加工的部分全部 作废重启只有在在线排序问题中才有意义因为在离线排序中，我们完全町以等到适当 的时候再加工工件，而不用做无用功而在在线排序中，因为缺乏未来工件的信息，所以 利用重启可以帮助决策者得到更优良的在线算法 我们用竞争比来衡量一个在线算法的优良程度对于一个最小化目标函数的 在线排序问题，我们说在线算法a 是p 竞争的( p 1 ) ，如果对于任意的实例互都 有a ( z ) p o p t ( z ) ，其h h a ( z ) 是在线算法a 生成的目标函数值，o p t ( z ) 是最优的离线算 法生成的目标函数值( 对最大化目标函数的在线排序问题，如果a 是户竞争的( p 1 ) i ff o ra n yi n s t a n c ez ，w eh a v e a 口) p o p t ( z ) ，w h e r ea ( z ) i st h eo b j e c t i v ev a l u eg i v e nb y a l g o r i t h maa n do p t ( s ) i st h eo b j e c t i v ev a l u eg i v e nb ya no p t i m a lo f f - l i n ea l g o r i t h m f t o am a x i m i z a t i o no n l i n es c h e d u l i n gp r o b l e m ，a l g o r i t h ma i sp - c o m p e t i t i v e ( p 1 ) m e a n s t h a ta ( 刁p o p t ( z ) ) i tc a nb eo b s e r v e dt h a tt h ev a l u eo fp i sm o r ec l o s e l vt o1 ，t h e a l g o r i t h mi sm o r eb e t t e r f o ra no n l i n es c h e d u l i n gp r o b l e m ，i ft h ec o m p e t i t i v er a t i oo f a da l g o r i t h mm a t c h e st h el o w e rb o u n do fc o m p e t i t i v er a t i o ，w es a yt h ea l g o r i t h m i sb e s t p o s s i b l e t h i si m p l i e st h a tt h ep r o b l e mi ss o l v e dt h o r o u g h l y i nt h i st h e s i s ，w ec o n s i d e rs i xp r o b l e m s i nc h a p t e r 2a n dc h a p t e r3 ，、s t u d yo n l i n e s c h e d u l i n go nas i n g l ep a r a l l e lb a t c hm a c h i n et om i n i m i z em a k e s p a nw i t hi n c o m p a t i b l e j o bf a m i l i e s ；i nc h a p t e r4a n dc h a p t e r5 ，w es t u d yt w op a r a l l e lb a t c hm a c h i n e s ：i nt h e 1 a s tt w - 0c h a p t e r s ，w ei n v e s t i g a t eo n l i n es c h e d u l i n go np a r a l l e lm a c h i n e ( s 1 u s i n gl i m i t e d r e s t a r t i nd e t a i l ，t h em a i nr e s u l t sa r ea sf o l l 0 、s 1 i nc h a p t e r2 ，w es t u d ya no n l i n es c h e d u l i n gp r o b l e mo na s i n g l ep a r a l l e lb a t e h m a c h i n et om i n i m i z em a k e s p a nw i t ht w oi n c o m p a t i b l ef a m i l i e s w ef i r s t p r o v et h a tt h e v i l o w e rb o u n do fc o m p e t i t i v er a t i oo fa n yo n l i n ea l g o r i t h mi s 牮1 7 8 0 8 t h e nw e p r o v i d eab e s tp o s s i b l eo n l i n ea l g o r i t h mw i t hc o m p e t i t i v er a t i o 华 2 i nc h a p t e r3 ，b a s e do nt h er e s e a r c ho fc h a p t e r2 ，w ee x t e n dt h ek n o w nr e s u l t w ea s s u m et h a tt h en u m b e ro ff a m i l i e sfi sa ni n p u td a t a w ep r o p o s eab e s tp o s s i b l e o n l i n ea l g o r i t h mw i t hc o m p e t i t i v er a t i oe x p r e s s i o no nf ，w h i c hi s1 + v 历- f 2 + l 一1 2 y w h e n ，2 ，t h er e s u l tm a t c h e st h ek n o w nr e s u l t s n o t et h a tw ep r o p o s ean e wb e s tp o s s i b l e o n l i n ea l g o r i t h m ，w h i c hi sd i f f e r e n tw i t ho t h e rk n o w na l g o r i t h m 3 i nc h a p t e r4 ，f o ro n l i n es c h e d u l i n go nt w op a r a l l e lb a t c hm a c h i n e st om i n i m i z e m a k e s p a n ，w ef i r s tp r o v et h el o w e rb o u n do fc o m p e t i t i v er a t i oi s 、2 t h e nw ep r o p o s ea b e s tp o s s i b l eo n l i n ea l g o r i t h mw i t hc o m p e t i t i v er a t i om a t c h i n gt h el o w e rb o u n d 4 i nc h a p t e r5 ，w ei n v e s t i g a t ea no n l i n es c h e d u l i n gp r o b l e mo nt w op a r a l l e lb a t c h m a c h i n e st om i n i m i z em a k e s p a nw i t ht w oi n c o m p a t i b l ej o bf a m i l i e s ，w eu s ea d v e r s a r y s t r a t e g yt op r o v et h a tt h el o w e rb o u n do fc o m p e t i t i v er a t i oi s 递掣1 6 1 8 t h e nw e p r o v i d eab e s tp o s s i b l eo n l i n ea l g o r i t h mw i t hc o m p e t i t i v er a t i o 造掣 曩i nc h a p t e r6 ，w es t u d ya no n l i n es c h e d u l i n gp r o b l e mo nas i n g l em a c h i n et o m i n i r a i z em a k e s p a nw i t hl i m i t e dr e s t a r t w cp r o v et h el o w e rb o u n do fc o m p e t i t i v er a t i o i s3 ：r t h e nw ep r o p o s eab e s tp o s s i b l eo n l i n ea l g o r i t h m w i t h o u tl i m i t e dr e s t a r t ，t h e b e s tp o s s i b l eo n l i n ea l g o r i t h mi s 华一c o m p e t i t i v e s or e s t a r th e l p su st og e tab e t t e r o n l i n ea l g o r i t h m 幢i nc h a p t e r7 ，w ec o n s i d e ro n l i n es c h e d u l i n go nt w op a r a l l e lb a t c hm a c h i n e st o m i n i m i z em a k e s p a nu s i n gl i m i t e dr e s t a r t w i t h o u tl i m i t e dr e s t a r t ，w eh a v ep r o v e di n c h a pl e r3t h a tt h eb e s tp o s s i b l eo n l i n ea l g o r i t h mi s 2 一c o m p e t i t i v e h e r ew ef i r s tp r o v e t h a tt h el o w e rb o u n do fc o m p e t i t i v er a t i oi s1 2 9 8 u n d e rs e c o n d r e s t a r ta s s u m p t i o n ( w e u s er e s t a r ta tt h e s ep o i n t st h a tt w om a c h i n e sa r eb l m ya n dw eo n l yr e s t a r tt h eb a t c hw i t h l a t e rs t a r t i n gt i m e ) ，t h el o w e rb o u n di s 华1 3 6 6 w ep r o v i d ea no n l i n ea l g o r i t h m w i t hc o m p e t i t i v er a t i o 掣，w h i c hi sb e s tp o s s i b l eu n d e rt h es e c o n d r e s t a r ta s s u m p t i o n k e y w o r d s ：p a r a l l e lb a t c h ，o n l i n es c h e d u l i n g ，i n c o m p a t i b l ej o bf a m i l i e s ，l i m i t e d r e s t a r t ，p a r a l l e lm a c h i n e s ，m a k e s p a n v i i 原创性声明 本人郑重声明：所呈交的学位论文，是本人存导师的指导下，独寺进行研究所取 得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发 表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体，均已在文中以明 确方式标明。本声明的法律责任由本人承担。 学位论文作者： 彳移象 醐：下占月工日 学位论文使用授权声明 本人在导师指导下完成的论文及相关的职务作品，知识产权归属郑州大学。根据 郑州入学有关保留、使用学位论文的规定，同意学校保留或向国家有关部门或机构送 交论文的复印件和电子版，允许论文被查阅和借阅：本人授权郑州大学可以将本学位 论文的全部或部分编入有关数据库进行检索，可以采用影印、缩印或者其他复制手段 保存论文和汇编本学位论文。本人离校后发表、使用学位论文或与该学位论文直接相 关的学术论文或成果时，第一署名单位仍然为郑州大学。保密论文在解密后应遵守此 规定。 学位论文作者：孑触 日期：砟占月f 日 i 1 1引言 第1 章绪论 排序是运筹学的一个重要组成部分排序论的研究目的是合理地利用有限的资源 去完成一些任务，使一一个或多个目标达到最优大部分的排序模型是从现实生产中遇 到的实际问题提炼出来的因此，资源和任务表现在实物上，有很多种小同的形式比 如，有限的资源有可能是工厂里的机器，飞机场的降落点和起飞点，港口的码头，电脑 的c p u 等；任务可能是等待运输的物资，工厂里面等待加工的原材料，即将降落或起飞的 飞机，码头靠岸或启航的船只，需要电脑处理的程序等通常我们用机器来代表资源，用 工件来代表任务排序的日标代表着决策者的利益比如单个目标的有，最小化最大完工 时间，最小化所有工件( a n 权) 完工时间之和，最大化提前完工工件的个数等多目标的情 形也有很多比如在最小化最大完工时问的前提下，最小化总的完工时间和决策者需要 制作尽可能好的解决方案( 如何让机器加工工件) 使利益达到最大化排序能够得到长足 的发展，是由于它在生产中的广泛的应用背景以及对经济产生的重要影响排序论方面 的专著有很多，比如8 ，5 a 早期的排序学者们研究的都是比较经典的排序模犁例如，工件不带有到达时 间且一台机器每次只能加工一个工件的离线排序模型很多问题都被证明存在多项 式时问的最优解法比如，s m i t h 【6 2 1 解决了单机最小化总的加权完j 二时间和的排序 问题，给出了一个多项式时问的最优算法w s p t 序( w e i g h t e ds h o r t e s tp r o c e s s i n gt i m e ) ， 即把所有工件按照各自的加工时间与权重的比值大小，从小到大排成一个序列，然后 逐个加t j a c k s o nf 3 a 最优地解决了单机最小化最大延迟的排序问题，所用的方法 是e d d 序( e a r l i e s td u ed a t e ) ，即所有工件按照工期从d , n 大的顺序排列，然后顺序加工 这些算法的运行时间都是多项式的事实上，经典的排序通常都是假设，决策者在制定排 序方案之前已经知道工件的所有信息，包括有工件的加工时问、到达时间、交工期限等， 我们也称这种排序是离线排序 随着社会的发展和生产的需要，新的排序模犁也不断涌现，从而更加促进了排序的 1 第1 章绪论 蓬勃发展在线排序足二十世纪七八十年代提出的一类新的排序在线排序相比较离线 排序而言，最显著的特点足决策者对丁件信息的未知性，也就是决策者在制定排序方案 之前，不知道工件的所有信息，也无从预测p r u h s 等人在文献【5 9 】中，把在线排序分为三 大类，具体如下： 时问在线( o n l i n e - t i m e ) 排序：工件是随着时间到达的工件的信息，比如，工件的加 工时间、到达时间、期限、权重等在工件的到达时刻才可获知工件在到达之前不可以 被安排，一旦被安排就不可以冉改变 列表在线( o n l i n e - l i s t ) 排序：工件是排列成一个序列( 或者表) 到达的前面的工件到 达后必须马上被安排( 安排并不等于加工，安排只是确定工件在哪台机器上加工，每台机 器上工件的具体加工顺序可以不用立且i j 确定) ，否则后面的工件就无法达到 不可预测的时间在线( o n l i n e - t i m e n e l v ) ：工件是随着时间到达的，但是工件 的加工时间只有在工件完工之后才可获知，而在工件的到达时刻无法得知或预 澳1 ( n o n c l a i r v o y a n c e ) 在在线排序中，决策者需要在刁 0 ，算法a 都是( 1 + e ) 一近似的，并且当e 是一个常数时，算法的运行时间是 输入的一个多项式，那么我们称a 是该排序问题的一个近似方案( p t a sp o l y n o m i a l t i m ea p p r o x i m a t i o ns c h e m e ) 如果算法的运行时间也是关于1 e 的一个多项式，那么 我们称a 足该问题的一个完全近似方案( f p t a sf u l l yp o l y n o m i a lt i m ea p p r o x i m a t i o n s c h e m e ) 我们用竞争比来衡量在线算法的优良程度对于最小化目标函数的排序问题，我们 说在线算法a 是p 竞争的，如果对该排序问题任意的实例z ，都有a ( z ) p o p t ( z ) ，其 中a 江) 是在线算法a 生成的目标函数值，o p t ( z ) 是最优的离线算法生成的目标函数值 ( 对最大化目标函数的问题，如果a 是p 竞争的( p 1 ) ，则有a ( z ) p o p t ( z ) ) 山此可见， p 的值越趋于1 ，则在线算法得到的目标函数值就越趋于离线情形下最优的目标函数值， 3 第1 章绪论 在线算法也更优良对某个在线排序问题来说，如果它的一个在线算法的竞争比与该问 题的竞争比的下界相吻合，那么我们就说该算法是最好可能的在线算法，这也就意味着 该排序问题彻底被解决 在研究一个在线排序问题的时候，我们首先要找到该问题任一在线算法竞争比的下 界，然后再来设计算法寻找下界的方法通常是，用对手策略设计一系列实例( 坏例了) ， 使得任意的在线算法作用在该实例上得到的目标函数值与最优的目标函数值的比值尽 可能大( 针对最小化目标函数的排序问题) 在我们设计在线算法的时候，竞争比的下界的 证明中坏例子的构造可以给予我们很多设计在线算法的原始思想，从而尽可能找到竞争 比与下界相吻合的最好可能的在线算法 本学位论文我们研究的模型或者带有不可相容的工件组，或者是批允许有限次重启 的在线平行批排序问题 所谓不可相容的工件组，指的是属于不同组的工件是不可相容的，不可以放在同一 批加工的这种假设具有一定的现实意义比如，- - 件是化学药品，它们具有彳i 一的化学 性质，如果放在一起储存或加工，就有可能产生化学反应使药品变质；再比如不同组：j ：件 可能需要不同的操作方法等等 在介绍批允许有限次重启之前，我们首先来介绍晕启的概念一个工件允许莺扁指 的是工件在加工的过程中可以被中断中断加工的工件已经被加t 的部分作废，工件恢 复到原始状态再次加t 该工件时必须重新开始加t f u 等人【2 3 1 提出了批允许重启的 概念批允许重启和工件允许重启性质基本相同，不同的是一个被重启的批中可能含有 多个工件，那么批中的所有工件都被释放出来，变成独立的未加工工件 考虑到重启是一种有限的资源或者重启会带来定的负面影响，因此我们提出了有 限次重启的概念批允许有限次重启是指，如果一批中不包含有已经被重启过的工件，就 可以被重启批重启之后，批中的工件被释放出来，成为各自独立的未加工工件再次加 工被重启过的工件时，必须重新开始加工，并且加工过程不可以被中断直到其完工 重启与中断是两个不同的概念工件允许巾断指的是，工件加工过程巾可以被中断， 中断的工件再次被加工时，是接着已经被加工的部分继续加工的；如果工件允许重启，那 么被重启的工件再次被加工时，是从头开始加上的，前面已经加工的部分全部作废重启 只有在在线排序问题中才有意义因为在离线排序中，我们完全可以等到适当的时候再 加工工件，而不用做无用功在在线排序中决策者冈为缺乏未来工件的信息，所以利用重 启可以帮助决策者得到更好刈能的在线算法下面我们举例来说明在在线排序模型中， 4 1 2 基本定义与符号 工件允许蕈肩乘i 中断的不同，以及蕈肩和中断对排序产生的不同影响 例子：考虑单机在线最小化总的完工时问的在线排序问题给定三个不同的贪婪的 在线算法，设为日。，吼，凰，它们的主要思想如下 算法风：不允许中断或重启工件当机器空闲时，把等待加工的工件按照加工时间 从小到达的顺序# - ：l b 歹l 好选择排在最前面的工件进t t d n t ； 算法- 2 ：允许中断工件当机器空闲或有新工件到达时，把等待加工和未加t 完的 工件按照剩余加工时间( 原来的加工时间减去已经被加工的部分) 从小到达的顺序排列 好，不满足该顺序时就中断当前正在加工的工件，选择最前面的工件加工 算法- 3 ：工件允许重启机器空闲或有新工件到达时，把等待加工和未加工完的工 件按照剩余加工时间从小到达的顺序排好，不满足该顺序时就重启当前正在加工的工件， 选择排在最前面的工件加工 我们给出以下例子来说明三个算法生成排序的不同 d i o 时刻，工件以，如到达，其加工时间分别是p 1 = 5 和p 2 = 6 三个算法都在0 时刻立 即开始加工工件以在时刻点l ，工件以，山到达，它们的加工时问分别是p 3 = 1 和m = 2 工件序列终止则生成的排序分别如下图所示： h k 竺生成删游ij,ij31以i j = i一5 目标值：+ 6 + 8 + 1 4 = 3 3 o568r 竺牛成刚防匝亚 二口 目标值：2 + 4 + 8 + 1 4 = 2 8 扩专广卜 目# 鲁生成喇孵i = j ：匝互 玉二工二口 目标值：2 + 4 + 9 + 1 5 ：3 0 。十专广气言 从上面的例子，我们可以更清楚地了解重启与中断之间的不同另外我们需要说明 的是，对允许巾断的排序模型，离线情形下最优的排序也是允许中断的。而允许重启的在 线模型，离线情形下的最优排序是4 、= 允许中断的( 重启在离线环境中没有意义) 对于上述 实例，离线情形下允许中断的最优的排序方式是算法凰生成的排序；离线情形下不允许 中断的最优的排序方式足算法风产生的排序 5 第1 章绪论 g r a h a m 等人【2 8 】创立了用三参数表示法来代表排序问题，即a 例，y ，其中q 域描述的 是机器的运行环境，比如，单机、平行机、同类机等；p 域描述的是工件的性质和排序的 一些限制条件等，比如，工件是在线到达的，t 件是甲行批处理的，批的容量等；，y 域代表 的是目标函数，有可能是单一的目标函数，也有可能是多目标函数，比如，最小化最大完 工时间，最小化最大延迟等等下面我们介绍以下排序中经常用到的一些符号 o 域： 1 单台机器，o p m m 台平行机，其中m 是一个固定的数； p 多台平行机，平行机的个数是任意的； q具有不周运行速度的多台机器； 冗 相关机，工件放在不同的机器上具有不同的加工时间 g 域： 我们用以代表一个工件， q代表工件以的到达时间； 鳓代表工件乃的加工时问； o n l i n e ，巧时问在线排序，丁什随时间到达； o n l i n e l i s t 列表在线排序： s e m i - o n l i n e , a x知道最长工件的加丁时间的半在线排序； p - b a t c h ，b工件可以平行批处理，批的容量是b ； ff a m i l i e s 有厂个不可相容的工件组，的取值足任意的； p m t n工件在加工的过程中允许被中断： l i m i t e dr e s t a r t 工件或批足允许有限次重肩的： r e s t a r t 工件或批允许任意多次重肩 ，y 域： c m 戤最小化最大完工时问； 6 1 3 相关文献 三m 戤最小化最大延迟； q 最小化总的完工时问和 屿0 最小化总的加权完工时间和 1 3相关文献 分批排序问题分为两种：平行批和序列批本学位文我们主要研究的是甲行批 方面的排序问题关于序列批方面的文献，请参考【3 ，1 6 ，7 0 】在平行批排序问题中， a h a m a d i 等人i i 研究了两台机器流水作业中的批处理问题作者研究的包括：两台机器 中一台每一次只能加工一个工件，另一台机器是批处理机一次可以加i b ( 批的容量) 个 工件月批容量有限：或者两台机器都是容晕有限的批处理机目标函数主要是最小化最 大完工时间和最小化总的完工时问和的排序问题因为是流水作业，所以分了三种类型 进行研究：第一种是工件先在批处理机上加j 二，然后再在只能加上单个上件的机器上加 工；第二种是工件在机器上的加工顺序刚好跟第一种情形反过来：第j 种是两台都是批 处理的情形对于最小化最大完工时间上的问题，三种不同类型的流水作业都存在多项 式时间的最优算法对最小化总的完- 丁时间和的问题，作者对后两种流水作业给出了多 项式时间的动态舰划算法，第一种流水作、i k 证明是n p 一凼难的对单台甲行批处理机最 小化总的完工时间和的问题，d e n g 等人在文献f 1 7 1 对批容量无界，工件具有到达时问的 情形给出了一个多项式时间的近似方案( p t a s ) ；在文献f 1 8 1 中，作者对批容量有界，到 达时间固定的情形给出了一个p t a s l i 等人f 4 0 k 考虑了工件到达时问和期限一致的批 排序问题不同的深刻的研究结果数不胜数，如 1 0 ，2 6 ，3 2 1 等，更全面的介绍见综述性文 章【5 7 ，4 5 ，7 】 本文我们研究的主要日标函数是最小化最大完工时间的批排序问题，包括单台批 处理机和多台平行批处理机在离线情形下，没有到达时问，批容量b 有限，最小化最大 完工时间的排序问题，最优的排序方式是f b l p t ( f u l lb a t c hl a r g e s tp r o c e s s i n gt i m e ) 规 则：把所有工件按照从大到小的顺序依次排列，然后从最大的工件开始，每b 个工件 组成一批，批形成之后以任意顺序加t 都能得剑最优的排序如果加入到达时间，变 成问题l i p - b a t c h ，b ，r j l c m 。当b 3 的情形，至今未能找到最好可能的在线算法文献f 2 9 ，6 1 ，1 2 】研究的也是关于列 表在线排序问题，作者给 了一些精彩的结果有。系列的半在线排序问题是在列表在 8 1 3 相天文献 线的基础上提出的比如，研究的排序模型足在列表在线的前提之下，同时决策者还已知 最长t 件的加t 时问，或者工件总的加t 时间和，义或者工件按照加t 时间从小剑大的 顺序到达半在线排序问题通常研究的排序模型中机器的类型是多台相关机，多台不相 关机，多台平行机等，见【6 0 ，6 4 ，2 0 】 本学位论文中，我们研究的都是时间在线排序问题，以下我们简称为在线排序问题 v c s t j e n s 在他的博士论文【6 6 1 中研究了一系列的在线排序问题，涉及的领域非常广泛，包 括有随机性的和确定性的在线排序问题，单机和平行机，流水作业、开放作业和车问作 业，研究的目标函数有最小化最大完工时间、最小化总的完工时间和、最小化最大运 输时问等等，给出了丰富的结果下面我们简单地列举几个该文献中的结果：对单机最 小化总的加权完工时问和问题，作者给出了一个最好可能的2 竞争的确定性算法；证明 了随机的在线算法的竞争比的卜界是1 5 8 2 ，从而证明了c h e k u r i 等人1 1 1 】给出的竞争比 是1 5 8 2 的随机的在线算法是最好可能的随机算法：在允许重启的情形f ，作者证明了该 问题任意在线算法竞争比的下界约为1 1 1 2 ，没有进一步给出允许重启的在线算法；在多 台- 甲行机上同样的目标函数，作者证明了任意确定性在线算法的竞争比的下界是1 3 0 9 对多台平行机最小化最大完工时间的问题，作者证明了在线的l p t ( 1 a r g e s tp r o c e s s i n g t i m e ) 算法的竞争比不大于3 2 ，证明了任意在线算法的竞争比的下界是1 3 4 7 3 如果机器 的台数m = 2 ，问题的下界是譬乎1 3 8 2 作者发表的论文【1 3 】中详细叙述了这一结果 作者对允许重启的排序问题也进行了探讨，给出并证明了很多在线排序问题允许重启的 任意在线算法的下界，除了上面介绍的结果之外，作者还对允许重启的平行机，目标函数 是最小化最大完工时间的在线问题进行了研究，证明了该问题任意的允许重启的确定性 在线算法的竞争比不会小于、6 2 对允许重启的在线排序问题，e p s t e i n 矛i s t e e 在文献f 2 1 1 中对很多允许重启的排序模 型给出了下界的证明作着提供了在研究允许重启的问题时，任意在线算法( 包括随机的 与确定性的) 的竞争比的下界的证明方法和思想允许重启能够使决策者得到更好可能 的在线算法，这一点在文献 2 ，3 1 ，1 5 ，6 3 】中都能得到证明有些在线排序问题在不允许重 启的情彤下，不存在常数竞争比的在线算法，加上重启这一条件结果完全不同，比如文 献| 3 1 1 中，对于目标函数是最大化提前完工工件的个数的单机在线排序问题，在允许重 启的情形下，作者给出了一个竞争比是1 2 的最好可能的在线算法同样的排序问题在不 允许重启时不存在常数竞争比的在线算法其它相关文献的结果我们将在第六章做详细 的介绍 关于平行批在线排序问题方面的研究，c h e n 等人【1 4 1 研究了单台平行批处理机，目 9 第1 章绪论 标函数足最小化总的加权完工时间和的在线排序问题在批容量无界的时候作者给出了 一个竞争比是1 0 3 的在线算法当批容量有界时给出了( 4 + e ) 竞争的在线算法，其中e 是 任意的一个正数z h a n g 等人【7 1 1 研究了单台甲行批处理机最小化最大完工时间的在线 排序问题同一篇文章中作者还研究了多台平行批处理机的在线排序问题作者对批容 量无界的单机情形给出了一个最好可能的在线算法算法的竞争比是耸竽为了避免重 复，这方面更多的文献知识我们将在后文相关的章节中给出详细介绍 1 4 本文结果 在本学位论文中，我们主要考虑了六个在线排序问题在第二章和第三章中我们研 究的是单台半行批处理机带有不可相容的工件组的在线排序问题第四章和第五章研究 的是两台平行批处理机的问题后面两章我们主要探讨了带有有限次重启的平行批排序 问题，同样包括单机和平行机具体地，本文主要结果如下： 1 在第二章中，我们研究了排序问题1 i p b a t c h ，6 = 0 0 ，o i l l i n e ，7 f ，t w o ：a m i l i e s l o m 舣 对于单机带有多个不可相容的工件组的在线排序问题，虽然有被研究，但是当组的个数 有限的时候，并没有得到最好可能的在线算法鉴于问题的难度，我们首先考虑了只有两 个不可相容的工件组的情形对于该问题，我们用对手策略构造出一系列实例，证明该问 题任意在线算法作用在该实例上得到的目标函数值都不会小于离线情形下最优的目标 函数值的牮1 7 8 0 8 倍也就是说，该问题的下界是业竽然后我们给出一个在线算 法算法的主要思想是：如果机器空闲时，有两个等待批( 属于不同的工件组) ，那么我们 总是优先选择加工时间较长的一批先开工，并且，根据两等待批批长的比值的不同，批的 开工时刻也有所不同当只有一个等待批的时候，批的开工时间只与等待批本身的加工 时问有关我们分析证明出所提供的在线算法的竞争比是掣也就是说，该算法是最 好可能的在线算法 2 在研究了工件组个数为2 的情形之后，很长时间我们致力于研究该问题一般的 情形，希望能够推广我们发现，在同样的机器环境之下，当工件组的个数足1 时，最 好可能的在线算法是鸡掣竞争的，如果我们假设q ，= 掣，a 2 = 边，那么它们分 别满足方程q 1 2 + q l 一1 = 0 和2 口2 2 + q 2 2 = 0 于是我们猜想：当工件组的个数 是，的时候，如果设该问题最好可能的在线算法的竞争比是1 + q ，那么q ，应该是满足方 程，- q 1 2 + q ，一f = 0 的一个正根在第三章中，我们证明了这一猜想的正确性对于 排序问题l i p - b a t c h ，b = 。o ，o n l i n e ，r j ，f a m i l i e s i a x ，设工件组的个数是，我们首先证明 1 0 1 4 本文结果 了问题的下界是l + 2 2 ，+ 1 - - 1 进而，我们给出一个最好可能的在线算法该算法即使 在，= 1 ，2 时也与已知的在线算法有所不同 3 在第四章中，我们研究了在线排序问题p 2 1 p - b a t c h ，b = o o ，o n l i n e ，7 f l c m a x 在我 们研究之前，n o n g 等人f 5 1 1 已经给出了一个竞争比不大于讵的在线算法，但是并没有证 明该算法是不是最好可能的在线算法我们在做进一步的研究时，首先找到了该问题任 一在线算法的竞争比的下界正是讵，也就是说文献f 5 1 1 中给冉的算法是最好可能的在线 算法但是该文献中算法竞争比的分析及其复杂进而，我f | j 找到了了一个更为简洁的 新的在线算法，简化地证明了该问题最好可能的在线算法的竞争比是讵 4 在第五章中，我们考虑了平行机上带有不可相容工件组的排序问题，即排序问 题p 2 1 p - b a t c h ，b = o o ，o n l i n e ，t w of a m i l i e s i c m 觚我们首先证明了该问题任意在线算法 的竞争比的下界足耸掣1 6 1 8 进而，我们给出了一个最好可能的在线算法，并证明的 算法的竞争比就是耸掣进一步，我们猜想当批处理机的个数与不可相容的t 件组的个 数相同的时候，最好可能的在线算法是耸斗一竞争的目前这一猜想还没有得到汪明 在最后两章中，我们主要考虑了批允许有限次重启的的在线排序问题有限次重启 这一概念的提出，主要源于一个比较现实的考虑一方面，重启可能是一种有限的资源， 凶此不可以任意次地大量使用；另一方面，排序过程中使用重启可能会造成机器的损伤 和能源的浪费所以我们提出每个工件只允许被重启一次，含有重启过的工件的批就不 可以再次被重启我们分单台平行批处理机和多台平行批处理机两种不同的环境分别使 用有限次重启 5 在第六章巾，我们研究了问题1 i p - b a t c h ，b = c o ，o n l i n e ，r j ，l i m i t e dr e s t a r t i a x 我们首先证明该问题竞争比的下界是3 2 ，然后给出了一个竞争比是3 2 的最好可能的在 线算法在不允许重启的情形下，最好可能的在线算法是造芦一竞争的，因此批允许重肩 使得我们得到了更好的在线算法 6 在第七章中，我们研究的两台平行批处理机，允许有限次重启的在线排序问 题，甚p p 2 l p - b a t c h ，b = 。，o n f i n e ，r s ，l i m i t e dr e s t a r tl c m a x 在不允许重启的情形下，最好 可能的在线算法是 2 一竞争的文中我们提出了一个新的概念：s e c o n d - r e s t a r t 它的 含义是，如果当前时刻有机器是空闲的，那么我们就不使用重启，只有当机器都是忙 碌的时候，我们才考虑使用重启，并且我们每一次重启的批都是当前时刻开工比较晚 的正在运行的一批在s e c o n d - r e s t a r t 的假设之下，我们首先证明了问题的下界是霉芒， 对一般的情形，任意在线算法竞争比都不小于1 2 9 8 然后我们给出了个在线算法， 1 1 第1 章绪论 该算法是满足s e c 彻d r e s a r t 这。假设的我们证明了算法的竞争比是掣也即是， 在s e c o n d - r e s t a r t 的假设下，我们给出的在线算法是最好可能的，但是对于一般的情形，目 前我们还没有找到最好可能的在线算法 1 2 第2 章带有两个工件组的单台平行批在线排序问题 2 1 引言 本章主要考虑的是单台平行批处理机，带有两个不可相容的工件组，最小化最大 完工时间的在线排序问题一个正在运行的批不可以被中断，也不可以被重启我们 假设批处理机的批容量是无界的，也就是说，每一批都可以安排任意多个工件一起加 工不同组之间的工件不相容也就是说，来自不同组的工件不可以放在同一批进行 加工这主要是考虑到不同组的工件具有不同的性质，如果放在一起可能会引起诸 如化学反应等不良影响应用g r a h a m 等人f 2 8 1 的记号方法，我们考虑的模型可以记作： 1 1 p - b a t c h ，b = 。，o n l i n e , r j ，t w of a m i l i e s c m 懿 目前，已经有很多平行批处理排序问题被大家所研究比如，对于离线排序 问题l i p - b a t c h ，b n l c m a x ，b a r t h o l d i ( 见l e e 和u z s o y 【3 8 】) 给出了一个最优的排序方 法耶l p t ( f u l lb a t c hl o n g e s tp r o c e s s i n gt i m e ) 如果在上述模型中加入一般的工件到 达时问，问题即转化成l p - b a t c h ，b o 是方程( 1 + 风) “= z m + 2 的一 个解；在批有界的情形下，他们证明了最好可能的在线算法的竞争比是( 5 + 1 ) 2 带有不可相容工件组的单台平行批处理机问题也得到了广泛的关注和深入的研究 对目标函数是最小化加权完丁时间和的排序问题，u z s o yf 6 5 提出了很多有效的算法 p o t t s 和k o v a l y o vf 5 7 对批处理工件分组的相关文献进行了综述，并详细给出了一些基本 算法a z i z o g l u 和w e b s t e rf 4 1 考虑了工件分组