（运筹学与控制论专业论文）工件可选择的平行机在线排序.pdf

摘要 平行机排序是应用非常广泛的一类排序模型本文主要研究的是一类平行 机在线排序问题，并且工件是可以选择的用三参数法表示我们的模型即是： p m l o n l i n e ，吩，d i 乃 其中d 指机器的使用期限，厶为工件以的加工利润，目标函数是使得在机器 的使用期限内所获得的总利润最大 我们在本文所讨论的模型是一种新模型：一种背包问题( k n a p s a c kp r o b l e m ) 的在线排序形式在现有文献中还未见有此类模型的研究工作在本文中所谓 的在线，是指工件集是按时( o v e r - t i m e ) 到达的，工件的所有性质( 包括到达 时间) 在它到来之前都是未知的，工件在到来之前不能被安排加工平行机 是指模型中的机器环境，指m 台类型相同、速度相同的机器同时投入作业 由于我们所讨论的模型目标函数值为求最大，故我们所用的竞争比p 定义为 p = 瓣 船 ，其中对任意一个实例a ，盯为算法得到的排序，r 为离线最优 序显然这里的p 满足0 ps1 本文模型的最显著特点是：工件具有可选 择性并且必须即时加工所谓可选择性，是指在工件到达之时，决策者可以接 受加工而获得利润，也可以拒绝加工而失掉利润，即到来的工件并非都要安排 加工，可以选择抛弃其中的某些工件所谓即时加工，是指工件不允许等待加 工，每一个到达的工件或者被选择在它的到达时刻开始加工，或者被抛弃掉， 不存在某一个被选择的工件的开工时间大于它的到达时间这种模型在现实生 活中有着很广泛的应用，例如公司或企业投资一批相同类型的机器进行生产活 动，定单的到来时间及内容事先是不知道的，且决策者可以接受定单也可以拒 绝定单由于市场竞争激烈，接受的定单必须立刻开工，而拒绝的定单很可能 立刻被别的企业接手，故被拒绝的定单以后也不可再接手加工 此模型的离线情形中当取r 1 = o ( j = 1 ，n ) 且允许工件在到达时间之后加 工时，它即是一个背包问题因而可以证明该模型的离线情形( 工件在到达时 刻立即加工或抛弃) 是p 一困难问题而对于本模型中工件的利润后与加工 时间p 1 不相关的情形，问题会比较困难故在本论文中我们主要讨论该模型 中一些较为特殊的情形：工件的利润办与加工时间功呈线性关系本文的内 容主要分两大部分：第一章，我们主要给出了排序论的介绍、一些用到的基本 概念、排序的记号以及模型的介绍等第二章中，我们首先在第一节中给出了 该模型中乃= 1 情形的所有在线算法竞争比的上界l 2 ，力= p j 的一般情形 ( 工件加工时间任意) 不具有竞争比为常数阶的在线算法，进而可知模型中 与砌呈线性关系乃= 心+ 如功( 脚， 0 ) 的一般情形也不具有竞争比为常数阶 的在线算法然后在第二节里，给出了厶= 1 且工件序列只包含两类工件情形 ( 小工件加工时间为1 ，大工件加工时间为d ) 的在线算法包括：只有两台 机器，大工件加工时间d 2 时，找到了一个竞争比为1 2 的在线算法4 1 ，且 此算法为最具竞争性的；当有任意m 台平行机时，找到了一个在线算法4 2 ， 证明了对于m = 2 k ( 仇为偶数) ，d k + 1 的模型此算法的竞争比为1 2 ，且 为最有竞争性的；对于m = 2 k + 1 ( m 为奇数) ，d 2 k + 2 的模型，此算法的 竞争比为k ( 2 k + 1 ) ，为渐近意义下最优的最后在第三节中，对于f j = 乃， 工件的加工时间只有两种( 小工件加工时间为1 ，大工件加工时间为d ) ，有任 意m 台平行机的情形，找到了一个在线算法同样证明了对于m = 2 k ( m 为偶数) ，d k + 1 的模型此算法的竞争比为1 2 ，且为最有竞争性的；对于 m = 2 k + 1 ( m 为奇数) ，d 2 k + 2 的模型，此算法的竞争比为k ( 2 k + 1 ) ，为 渐近意义下最优的 关键词：平行机，在线算法，工件可选择性，竞争比。 a b s t r a c t p a r a l l e lm a c h i n es c h e d u l i n gi so n eo ft h es c h e d u l i n gm o d e l sb e i n gu s e de x t e n s i v e l y i n t h i sp a p e rw ec o n s i d e ra no n - l i n ep a r a l l e lm a c h i n es c h e d u l i n gp r o b l e mi nw h i c h j o b sc a r l b ec h o s e n o u rm o d e lc a i lb er e p r e s e n t e da s ： p m o n l i n e ，巧，d i 厶， i nw h i c hdi st h et i m el i m i to fm a c h i n e s ，| ii st h ep r o f i tb yp r o c e s s i n gj o bj t h eg o a l i st os e l e c tj o b ss oa st om a x i m i z et h et o t a lp r o f i to fa l lp r o c e s s e dj o b sd u r i n gt h ep e r i o d t h a tm a c h i n e sc a nb eu s e d t h em o d e lw ec o n s i d e ri nt h i sp a p e ri san e wt y p e i ti sa no n - l i n es c h e d u l i n gf o r mo f t h ek n a p s a c kp r e b l e m w eh a v en o ts e e na n ys t u d yo i ls u c hm o d e le l s e w h e r e h e r e ，o n - l i n em e a n st h a tj o b sa r r i v eo v e rt i m e ，a n da l lj o bc h a r a c t e r i s t i c s ( i n c l u d i n ga r r i v i n gt i m e s ) a r eu n k n o w nb e f o r et h e i ra r r i v a lt i m e s j o b sc a n n o tb es c h e d u l e db e f o r et h e ya r r i v e d p a r a l l e lm a c h i n er e f e r st ot h em a c h i n ec o n d i t i o ni nt h i sm o d e lw h i c hm e a n st h a tt h e r ea r e mm a c h i n e so ft h es a m et y p ea n dt h es a m ew o r k i n gs p e e d s i n c et h eo b j e c t i v eo fo u rm o d e l i st 。b em a x i m i z e d ，t h ew o r s t _ c a s er a t i 。i sd e f t n i t e db yp = 瓣 篇) ，f o ra n yi n s t a n c ea ， 盯i sas e q u e n c eo b t a i n e db yt h eo n l i n ea l g o r i t h m 7 ri sa no f f - l i n eo p t i m a ls e q u e n c eo fa h e r e ，0 p 1 j o b si nt h i sm o d e lc a nb ec h o s e n i tm e a n st h a tw h e naj o ba r r i v e s ，i t c a nb ee i t h e ra c c e p t e dt og a i np r o f i to rr e j e c t e dt ol o s ep r o f i t n o ta l lt h ej o b st h a th a v e a r r i v e dm u s tb es c h e d u l e do nt h em a c h i n e s ，r a t h e r ，8 l lt h ej o b st h a th a v eb e e nc h o s e n m u s tb e g i np r o c e s s i n ga tt h e i ra r r i v a lt i m e s i faj o bc a n n o tb ep r o c e s s e di m m e d i a t e l ya t i t sa r r i v a lt i m e ，i th a v et ob er e j e c t e d n oj o bc a nw a i tf o ra n yt i m e ，a f t e ri t sa r r i v a l ，t ob e p r o c e s s e d t h i sl 【i n do fm o d e li sw i d e l ya p p l i e d f o ri n s t a n c e c o r p o r a t i o n so re n t e r p r i s e s p u r c h a s es o m em a c h i n e sw i t ht h es a m et y p e t h ea r r i v a lt i m e sa n dc o n t e n t so fo r d e rf o r m s a r eu n k n o w nb e f o r et h e i ra r r i v a l w h e na no r d e rf o r ma r r i v e s ，d e e i s i o n m a k e rm a ya c c e p t i to rr e j e c ti t w ea r ea w a r et h a tt h ec o m p e t i t i o no fm a r k e ti sv e r yi n t e n s e o r d e rf o r m s a c c e p t e dm u s tb ep r o c e s s e da to n c e h o w e v e r ，t h o s er e j e c t e dm a yb ea c c e p t e db yo t h e r e n t e r p r i s e s ，a n dc a n n o tb ea c c e p t e da l t e r n a t e l yi nt h ef u t u r e i i j w h e n 巧= 0 ( j = 1 ，n ) a n dj o b sc a nb ep r o c e s s e da ts o m et i m ea f t e ri t sa r r i v a l t h eo f f - l i n ep r o b l e mo ft h i sm o d e li si nf a c tak n a p s a c kp r o b l e m w ec a n p r o v et h a tt h e o f f - l i n ep r o b l e mi sn p h a r dw h e n j o b sm u s tb ep r o c e s s e do rr e j e c t e dj u s ta ti t sa r r i v a lt i m e i no n rm o d e l ，t h ec 8 s et h a tp r o f i t | sa n dp r o c e s s i n gt i m ep lo fj o b3 3h a v en or e l e v a n c e i sv e r yd i f f i c u l t w ec o n s i d e ras p e c i a lc a s ei nt h i sp a p e r ：t h ep r o f i ta n d p r o c e s s i n gt i m e a r el i n e a r l yd e p e n d e n t ，t h i s p a p e rm a i n l yi n c l u d e st w op a r t i nc h a p t e r1 ，i n t r o d u c t i o no f t h et h e o r yo fs c h e d u l i n g ，s o m ef u n d a m e n t a lc o n c e p t i o n st h a tw em a yu s e ，s o m en o t a t i o n o fs c h e d u l i n ga n dt h ed e s c r i p t i o no fo u rm o d e l i nc h a p t e r2 ，f i r s t ，w eg i v ea nu p p e r b o u n d1 2 趟c o m p e t i t i v er a t i of o rt h ec a 8 ef j = 1a n dp r e s e n ta ni n s t a n c et os h o wt h a t t h e r ei sn oo n - l i n ea l g o r i t h mw h i c hh a sac o n s t a n tc o m p e t i t i v er a t i of o rt h ec a s e 5 = p 3 t h e n ，f o ra l lt h ec a s e s ，i nw h i c hj o b s p r o f i ta n dp r o c e s s i n gt i m ea r el i n e a r l yd e p e n d e n t ， 乃= 如+ 聊( 如， o ) ，t h e r ei sn oo n l i n ea l g o r i t h mw h i c hh a sac o n s t a n tc o m p e t i t i v e r a t i o s e c o n d ，o n - f i n ea l g o r i t h m sa r ep r e s e n t e df o rt h ec a s e 矗= 1a n dj o b sh a v eo n l y t w ok i n d so fp r o c e s s i n gt i m e ( s m a l l - j o b s p r o c e s s i n gt i m ei s1a n dl a r g e - j o b s p r o c e s s i n g t i m ei sd ) f o rt h es u b c a s et h a tt h e r ea r eo n l yt w om a c h i n e s ( m = 2 ) a n dd 2 ，o n - l i n e a l g o r i t h ma 1h a sac o m p e t i t i v er a t i oo fa tl e a s t1 2a n di t i st h eb e s tp o s s i b l e f o rt h e s u b c a s et h a tm = 2 ka n dd k + 1 ，o n - l i n ea l g o r i t h m4 2h a sac o m p e t i t i v er a t i oo fa tl e a s t 1 2a n di st h eb e s tp o s s i b l e t h e nf o rt h es u b c a s et h a tm = 2 k + la n dd22 k + 2 ，0 n ，l i n e a l g o r i t h ma 2h a sac o m p e t i t i v er a t i oo fa tl e a s tk ( 2 k + 1 ) a n di st h ea s y m p t o t i c a l l yb e s t p o s s i b l e f i n a l l y , f o rt h ee a s e | i = 粥a n dj o b sh a v eo n l yt w ok i n d so fp r o c e s s i n gt i m e ( s m a l l - j o b s p r o c e s s i n gt i m ei s1a n dl a r g e - j o b s p r o c e s s i n gt i m ei sd ) ，a no i l l i n ea l g o r i t h m a 3i sp r o p o s e d f o rt h es u b c a s em = 2 ka n dd k + 1 ，i th a sac o m p e t i t i v er a t i oo fa tl e a s t 1 2a n di st h eb e s tp o s s i b l e a n df o rt h es u b c a s et h a tm = 2 k + la n dd 2 k + 2 ，i th a sa c o m p e t i t i v er a t i oo fa tl e a s tk ( 2 k + 1 ) a n di st h ea s y m p t o t i c a l l yb e s tp o s s i b l e k e yw o r d s ：p a r a l l e lm a c h i n e ，o n - l o n e ，s e l e c t i v ej o b s ，c o m p e t i t i v er a t i o ， i v 第一章概述 1 1排序论介绍 排序理论是组合最优化学科的一个重要组成部分它被广泛的应用于管理 科学、计算机科学、工程技术等很多领域排序问题随着近代工业的发展即生 产规模和产品更新的迅速变化逐渐突显出来，如生产的组织、市场的管理、交 通运输的安排，以至战场的指挥等等排序问题的一大特点是：模型繁多不 同的模型需要用不同的方法去处理有时即使是同一模型，由于参数取值范围 不同，问题的难度就有天壤之别 排序问题的研究起源于二十世纪五十年代初期由于排序问题的研究方法 涉及组合最优化的各个分支，故自它创立以来得到了运筹学、管理科学、计算 机科学等多种学科的重视在二十世纪八十年代以前，对排序问题的研究主要 集中在一些经典模型上所谓经典排序，是指有四个基本假设：资源类型、确 定性、可运算性及单目标正则性的排序近年来更多类型的模型相继出现，与 经典排序的假设相矛盾，于是现代排序便应运而生现代排序是相对于经典排 序而言，也就是非经典的、新型的排序现代排序的特征是突破经典排序的四 个基本假设，主要有可控排序、成组分批排序、在线排序、同时加工排序、准 时排序和窗时排序、不同时开工排序、资源受限排序、随机排序、模糊排序、 多目标排序等十种 排序问题本身就是一类组合最优化问题，我们通常求解排序问题的基本思 路是，应用或借鉴求解其他组合最优化问题的方法，并利用排序问题本身的特 殊性质，以确定满足约束条件的最优排序如果排序问题具有多项式算法，从 实际应用角度来看，我们说问题已经解决了然而很多重要的排序问题是n p 一 难的对这类问题找到一个多项式算法求得它的精确排序是非常困难的我们 采用的方法通常是在较短的时间里求出实际上能够接受的近似最优排序，即找 一个近似算法所谓近似算法就是这样一些算法，他们给出的不是最优解，而 是保证偏离真正最优解有固定百分比的解下面我们将介绍一些有关近似算法 的概念： 一个多项式时间算法4 称为最优化问题p 的一个绝对近似算法，若存在 一个常数k ，使得对p 的任意实例j 都满足1 4 ( ，) 一o p t ( i ) l k 其中4 ( ，) 为 实例，由算法4 得到的目标值；o p t ( i ) 为实例，的最优序所得的目标值 设p 是一各具有非负权的最优化问题，七1 一个多项式时间算法4 称 为7 0 的一个k 一因子近似算法，若对p 的任意实例，都满足 o p t ( i ) a ( j ) a o p t ( i ) 我们也称k 为算法4 的竞争比 设p 是一各具有非负权的最优化问题，k 1 一个多项式时间算法4 称 为p 的一个渐近k 因子近似算法，若存在一个常数c ，使得对p 的任意实例 ，都满足 o p t ( i ) 一cs4 ( j ) k o p t ( i ) + c 我们称k 为算法4 的渐近竞争比 设p 是一各具有非负权的最优化问题一个算法4 称为p 的一个近似方 案，如果4 以p 的一个实例，及e 0 为输入，使得对每一个给定的e ，a 是p 的一个( 1 + e ) 一因子近似算法多项式时间的近似方案我们通常简称为 p t a s 更进一步，如果算法4 的运行时间以及算法中出现的最大值的输入长 度以s i z e ( i ) + s i z e ( e ) + ；的多项式为界，则4 称为p 的一个全多项式近似方 案，简称f p a s 由于现实生活中许多情况是在所有信息知道之前就必须进行排序，因此在 线排序问题越来越多地受到人们的关注与重视在线排序分为按时在线和按序 在线两种这两种情况中工件安排以后就不能够再改变了，工件的加工要求在 工件开始加工时已经清楚地给出因而上述两种模型称为可预测的在不可预 测的情况下，工件的加工要求只有到加工完成后才知道所以在线排序共有四 种：可预测的按时在线排序，可预测的按序在线排序，不可预测的按时在线排 序和不可预测的按序在线排序h o o g e v e e n 和v e s t j e n s 1 0 证明了最大延迟问题 的按时在线排序1 l 帆一l i n e ，q i l 。不存在竞争比小于( 1 + v 信) 2 的在线算法， 并且证明了改进的e d d 算法的竞争比为( 1 + v 信) 2 ，因而是最具竞争性的同 一篇文章中，他们还证明了总完工时间问题的按时在线排序1 i o 凡一l i n r ，巧i g 不存在竞争比小于2 的在线算法并提出了竞争比为2 的算法有关平行机的按 2 时在线排序问题p l m l i n e ，q i g 。，陈礴和v e s t j e n s 2 】给出竞争比是3 2 的在 线l p t 算法，且这个界是紧的g z h a n g ，x c 砸和c k w o n g 8 ，以及x d e n g 和 y z z h a n g 1 9 】这两组人对于按时在线批加工问题1 i 一l i n e ，巧，p 一6 0 缸 i g 。各 自分别给出一个竞争比为( 1 + 娟) 2 的在线算法，并都证明了算法为最有竞争 性的 介于在线排序和离线排序之间是半在线排序，即不允许对已经安排的工件 重排，但是在排序之前知道后面就绪的工件的部分信息根据半在线排序问题 中所知道的工件信息的不同可以大致分为： l 、不知道各个工件的加工时闯，但知道工件是按加工时间非增的次序就 绪的，这种情况记为o r d i n a l ； 2 、有一个存储器可用来存放至多个工件，因此可以不必立即决定当前工 件的安排而把其放入存储器中，记为b u f f e r ； 3 、已知所有工件的加工时间之和，记为t o t a lp r o c e s s i n gt i m e ； 4 、已知所有工件中最大的加工时间，记为l a r g e s tp r o c e s s i n gt i m e ； 5 、已知所有工件的加工时间属于一个区间防，剜，并且p 0 ，r 1 ，记为 i n t e r v a l 对于平行机半在线问题p l o r d i n a l l c m 。，l i u ，s i d n e y 和v l i e t 1 3 提出竞争 比为1 + 一1 ) ( m + 罟1 ) 的算法对于平行机最小完工时间为最大的半在 线排序问题p 2 o r d i n a l l c m i 。，何勇 17 】提出竞争比是2 3 的算法，并证明了 此算法是最有竞争性的k e l l e r e r ，k o t o r ，s p e r a n z a 和t u z a 1 2 】对于2 台同型机 半在线排序问题p 2 t o t a l p r o c e s s i n g i m e i g 一提出竞争比是4 a 的算法并证 明了它是最有竞争性的对于平行机最小完工时间为最大的半在线排序问题 p 2 1 t o t a lp r o c e s s i n gt i m e c , 饥，何勇 17 】提出一个最有竞争性的算法，其竞争 比为2 a 除此之外，还有越来越多的人加入到在线排序和半在线排序的领域中，并 取得了丰硕的成果 3 1 2基本概念 在排序论中，工件是被加工的对象，是要执行的任务；机器是提供加工的 对象，是完成任务所需要的资源；安排时间表是在一定约束条件下对工件和机 器按时间进行分配和安排次序，使得某一个或某些目标值达到最大或最小排 序是安排时间表的简称这样我们就从各色各样的实际问题中抽出具体的模型 来下面我们将介绍一下在线排序和平行机排序的概念 在介绍在线排序的定义之前，我们先来看一下离线排序的定义所谓离线 排序是指工件在被排在机器上之前，它的所有信息，包括到达时间、加工时间、 权重、截止日期等，均已知晓经典排序都是离线排序而在现实生活生产中， 往往排序问题中工件的信息在它到来之前是不知道的，也是不可预测的这就 产生了现代排序中的在线排序所谓在线排序，就是工件信息是逐个释放的， 工件的所有信息( 包括到达时间) 在它到来之前都是未知的，工件在到来之前 不能安排作业，只有在工件到来以后才可以安排，而且一旦被安排加工就不能 再改变同时在线排序又分为两种： ( 1 ) 按序( o v e rl i s t ) 在线排序：工件是排列成一定序列逐个出现的一个 工件只有当序列中排在其前面的工件都安排后才知道这个工件的相关信息。 ( 2 ) 按时( o v e rt i m e ) 在线排序：工件是随着时间到达并进行安排的，任何 工件的信息是在它到达的那一时刻才知道的 因为在线排序中工件的信息只有在它到达后才能知道，所以在线排序问题 通常没有多项式时间的精确算法那么对于一个在线算法，我们通常用竞争比 来衡量它的好坏对一个使目标函数达到最大的在线排序问题，竞争比p 定义 为对问题所有实例的比值州p 的下确界，其中f 和p 分别代表在线排序算 法得到的目标函数值和相应的离线情形下的最优值我们用构造实例的方法找 到在线排序问题的上界，如果一个在线排序算法的竞争比p 恰与该问题的上界 相吻合( 相等) ，或者说，不存在其他的在线算法的竞争比大于p ，我们就说 该算法是最具竞争性的 下面我们将给出有关平行机排序的一些概念所谓平行机指的是机器的状 4 况通常机器的状况分为三种：单机( s i n g l em a c h i n e ) 、平行机( p a r a l l e lm a c h i n e ) 、 串联机( s h o pm a c h i n e ) 其中单机是各种机器状况中的特殊情形 平行机又可具体分为三种不同的机器状况：p m ( i d e n t i c a lm a c h i n e si np a r - a r i e l ) 表示m 台速度相同的平行机器( 简称恒同机) q m ( m a c h i n e si np a r a l l e l w i t hd i f f e r e n ts p e e d s ) 表示m 台一致的平行机器( 简称一致机) ：若机器舰的 速度为矾，工件乃的加工时间为功，则工件以在机器坛上加工时的实际加 工时间为p t j = p j v t 如果所有机器的速度都相同，此即为p m 的情形r m ( u n r e l a t e dm a c h i n e si np a r a l l e l ) 表示m 台无关的平行机器( 简称无关机) 此类 机器随加工工件的不同而加工速度也不同：若机器尬的速度为，则工件以 只在机器舰上加工时的实际加工时间为p i j = p j v 玎此情形是q m 的推广 串联机也可分为三种更细致的机器状况： f m ( f l o ws h o p ) 表示m 台机器 的流水作业，每个工件以特定的相同机器次序在这些机器上加工o m ( o p e n s h o p ) 表示m 台机器的自由作业，每个工件在机器上加工的次序不事先假定 ，m ( j o bs h o p ) 表示m 台机器的异序作业，每个工件以各自特定的机器次序 进行加工，这个次序是事先给定的 本论文中我们主要研究的模型为工件到达状况是按时在线到达的，而机器 状况是平行机中的恒同机，目标值为求最大 1 3排序的记号 根据1 9 7 9 年g r a h a m 等人提出的排序问题的三参数表示法，我们使用a 矧，y 来表示一个排序问题在这里，a 表示机器的数量，类型和环境；p 表示工件 的特征和约束；7 表示要优化的目标下面我们对它们作出说明： ( 1 ) 域： a = 1 表示单台机器； a = 尸m 表示m 台恒同机； a = q m 表示m 台一致机； o = r m 表示m 台无关机； 5 o = f m 表示m 台机器的流水作业； n = o m 表示m 台机器的自由作业； 口= j m 表示m 台机器的异序作业 ( 2 ) p 域： p = r j 表示工件以的到达时间； p = 也表示工件也的工期； p = “胁= p ”表示所有工件具有相同工时； 卢= p r e c 表示工件间有序约束； p = p m t n 表示工件允许中断抢先； p = o n - l i n e - l i s t 表示工件是按序在线； = o n 一n e ，吩表示工件是按时在线； 卢= d 表示机器的使用时间为d ( 3 ) 7 域： 我们先来介绍一些常见符号的含义： 0 ：工件易的完工时间； 易= g 一奶：工件以的延迟时间； 乃：工件五的延误时间； u j ：工件乃的误工计数； 乃：工件以的加工利润 下面我们介绍一些常见的优化目标目标函数： ，y = g 一 最大完工时间，此处g 。= m a x g f l js 礼 ； 7 = 三。m 最大延迟，此处l 。= m a x 岛1 1 j n ； ，y = 0 完工时间和； 7 = 钍。c j加权完工时间和； 7 = 乃误工时间和； ，y = 嘶乃加权误工时间和； ，y = v j 误工工件数； 7 = w j u j加权误工工件数； 6 ，y = 办工件加工总利润和 1 4模型特点和主要结果 本节我们将给出本论文中所讨论模型的具体描述给定相同类型的m 台 平行机，所有机器都有一个公共的作业期( 时间区间) 【0 ，d 】这里d 可以是 机器的使用寿命，也可以是经济核算期限或作业周期现有n 个在线到达的 工件 ，如，厶，其中工件乃的到达时间为巧，开工时间为勺，加工时间 为功，利润值为厶( 1sj n ) 按照按时( o v e r - t i m e ) 在线的含义，在到达 时间q 之前，工件的加工时间乃及利润乃是未知的在这个作业系统中，工 件有可选择性，即在工件到达之时，决策者可以接受加工而获得利润，也可以 拒绝加工而损失利润而且该系统中的工件必须即时加工，即被接受的工件必 须在它到达的那一时刻有机器空闲并开始加工，所以对每个被接受的工件如 均有s 。= r 1 此作业系统的问题是在给定的作业期内，如何决定到来工件的 取舍，使得获取的总利润f = 以。a 乃为最大( 这里a 表示接受加工的工件 集) 我们称之为工件可选择的平行机在线排序问题；按照习惯，此问题简记 为p m l a n l i n e ，r 1 ，d f 办 此模型与传统排序问题不同之处在于：传统排序问题中，每个到达的工件 都必须被加工，其开工时间可以是它的到达时间也可以是之后的某一时刻而 在此模型中，工件到达之时可以安排加工，也可以拒绝加工，以作业期限内取得 最大经济效益为目标且模型中的工件不允许等待加工，即每个工件的到达时 刻为其决策时刻，工件或者在它的到达时刻开始加工，或者被抛弃，不可以保 留在以后的某一时刻再来加工这种新模型在现实生活的企业管理中有广泛的 应用例如工厂或投资商对到来的加工定单是权选择的，可以接受或拒绝，视 经济效益而定 在本论文中我们讨论一种正常的情形：工件一旦被接受或被拒绝，则不能 改变选择决策，即对接受加工的工件必须在机器上加工至完成，对拒绝的工件 则永远不能再安排加工此种情形我们也称之为。不允许反悔”的在现实生 7 活中也有“允许反悔”的情形，与前一种情形的不同之处在于，已接受加工的 工件在其加工过程中遇到更有利的工件时也允许中途拒绝( 退单) 这种更复 杂的情形可作为进一步的研究课题此外，在工件的利润厶与加工时间乃不相 关的情形，问题会比较困难在本文中我们只讨论二者呈线性关系的情形，即 乃= 助+ 聊( 心， 0 ) 它可齐次化为乃= 知功的情形，因为可以令( 心肠+ ) 为新的系数自然，这也包括特殊情形乃= p j ( ；b = 1 ) 及厶= 1 ( = 1 胁) 另一方面，由于可以适当选择时间单位，所以不妨假设d m ，并且口为正 整数 根据我们所讨论的模型，工件可选择的平行机在线排序的特点：机器具有 使用期限 o ，d 】，工件如除有到达时间巧和加工时间聊，还附带有加工利润 办，目标函数求总利润最大等我们可以看出其离线情形实际上是在一个背包 问题中添加一个到达时间参数r 所谓背包问题( k n a p s a c kp r o b l e m ) 是指： 给出一些非负整数c l i 一，w 1 i 一，和彤找到一个子集s 1 ，礼 ，使 得邑。s w j w 且邑。s 勺为最大背包问题是一个n p - 困难问题当本模型 的离线情形中取巧= 0 0 = 1 ，几) 并且允许工件在到达时间之后加工时，它即 是一个背包问题，故其离线情形( 工件在到达时间立即加工或抛弃) 应该也可 以证明是一个n p 一困难问题因此我们所讨论的在线模型将更为复杂 在本论文中我们给出的主要结果有： 首先我们通过构造实例的方法分别给出了该模型中 = 1 情形的所有 在线算法竞争比的上界1 2 ，矗= p j 的一般情形( 工件加工时间任意) 不 具有竞争比为常数阶的在线算法，进而可知模型中办与聊呈线性关系乃= 心+ 功( 助， 0 ) 的一般情形也不具有竞争比为常数阶的线算法 其次我们给出了厶= 1 且工件序列只包含两类工件情形( 小工件加工时 间为1 ，大工件加工时间为d ) 的在线算法其中包括：当m = 2 ( 只有两台机 器) ，大工件加工时间d 2 时，我们找到了一个竞争比为l 2 的在线算法4 1 ， 且可知此算法为最有竞争性的；当有任意m 台平行机时，我们找到了一个在 线算法4 。，并证明了对于m = 2 k ( m 为偶数) ，d k + 1 的模型此算法的竞 争比为1 2 ，且可以推知此算法对此模型为最有竞争性的；对于l i f t = 2 k + l ( m 8 为奇数) ，d 22 k + 2 的模型，此算法的竞争比为k ( 2 k + 1 ) ，为渐近意义下最 优的 最后对于后= 巧的情形，我们通过前面构造的实例说明当工件序列中工 件的加工时间胁可以任意长时不存在竞争比为常数阶的在线算法这使得我们 考虑工件的加工时间只有两种( 小工件加工时间为1 ，大工件加工时间为d ) 的特殊情形对于有任意m 台平行机只含两类工件的情形，我们找到了一个 在线算法同样证明了对于m = 2 k ( m 为偶数) ，d k + 1 的模型此算法的 竞争比均为1 2 ，并且推知此算法对此模型为最有竞争性的；对于m = 2 k + l ( 仇为奇数) ，d 2 k + 2 的模型，此算法的竞争比为k ( 2 k + 1 ) ，为渐近意义 下最优的 9 第二章工件可选择的平行机在线排序 本章我们将具体讨论有关排序模型p m o n l i n e ，巧，d i 乃的相关结果首 先在第一节里我们将给出厶= 1 ，p j ，b 秘，u j + 功( 0 ) 等情形的所有在线算法 竞争比的一个上界；在第二节里我们将给出后= 1 情形下具有两类工件的在线 算法及其证明；在第三节里我们将讨论乃= p j 情形下具有两类工件时的在线 算法及其证明 我们用如表示工件j ，用r 1 ，功分别表示工件以的到达时间和加工时间， 其中r j o ，p j 1 ，用d 表示机器的可使用时间，假设d 为整数，用m 表示平 行机的机器台数，在本文的讨论中对d 选择适当的时间单位使得对所有模型 均满足d m 对于一个排序实例a ，用。和丌分别表示实例a 由在线算 法得到的排序和所对应的离线情形下的一个最优排序记f ( 盯) 和f ( 丌) 分别为 实例a 由在线算法得到的目标值和离线情形下的最优值一个在线算法4 优 劣通常由它的竞争比来衡量在本文所讨论的最大目标值的问题中，在线算法 4 的竞争比p 可以定义为 ，f f 盯1 、 p 2 错t 肃而， 其中a 取遍所有可能的实例显然，0 p 1 其竞争比p 越接近1 ，在线算 法4 越好 2 1竞争比的上界 1 疗= 1 当无论工件加工时间长短，对其加工所获利润均相同时，我们可以将每加 工一个工件所获的利润看作1 ，此时求总利润的目标值f = 办最大即可看作 求机器加工工件的总个数最多 对于任意一个在线算法4 ，我们构造实例如下：现有m 台平行机，机器 可使用时间为【0 ，d 】，在0 时刻有m 个加工时间为d 的工件j y ( j = l ，m ) 1 0 到达算法a 若在此时刻开始加工的工件个数n os 【孑j ，则不再有新工件到 来，工件序列到此终止；若在此时刻开始加工的工件个数n o 【罟j + 1 ，则在 e + i ( i = 0 ，1 ，d 一1 ) 时刻分别有m 个加工时间为1 的工件芬+ 1 0 = 1 ，m ) 到达( 本文中的e 均为任意小的正数) ，无论算法4 对其加工情况如何均不再 有新工件到达，工件序列到此终止即有工件 霉：窍= d ，巧0 = o ；巧+ 1 ：萨1