（运筹学与控制论专业论文）带有安装时间的单机成组排序问题.pdf

带有安装时间的单机成组排序问题 摘要 排序问题也称调度问题，是组合最优化中的一个重要分支排序问题的 一大特点是：模型繁多，适用于某一模型的算法，只要将模型的条件稍加变化，该 算法即可能不适用在许多排序问题中，安装时间通常假设为常数，但在现实中， 安装时间往往不是独立存在的，往往需要受加工时间的影响，因而研究和已经 加工完工件的加工时间有关的安装时间的单机成组排序问题显得尤为重要在这 一排序模型中，工件的加工不可中断、工件组的安装时间是和已经加工完工件 的加工时间有关的连续函数本文主要对带有安装时间的单机成组排序问题进 行了讨论 本文首先介绍了排序问题的定义、表示方法及分类，带有有安装时间的排序 问题和单机成组排序问题的研究成果和发展情况然后对带有安装时间的单机 成组排序问题进行了讨论在本文的第二章中，主要讨论了带有安装时间和准备 时间的单机成组排序问题，其中每个工件都具有自己的准备时间，组和组之间具 有安装时间，并且安装时间和已经加工完工件的加工时间有关所有工件在机器 上加工时，一次只能加工一个工件，工件不可中断，组内工件连续加工，组和组之 间需要安装时间，对目标函数为极小化最大完工时间的单机成组排序问题，给出 了求解最优排序的多项式算法，并利用具体例子对算法的应用做出解释第三章 讨论了带有安装时间和加工时间受资源约束的单机成组排序问题，其中包括两个 问题一个问题是在资源消耗量受限条件下极小化最大完工时间的最优排序和资 源分配方法，另一个问题是目标函数在满足资源消耗总量限制条件下极小化最大 完工时间的最优排序和资源分配方法在这两个问题中，同一组内的工件不允许 分开加工，各工件组的加工时间是所消耗资源的线性非增连续函数最后对本文 的内容进行总结，并提出对未来的工作设想和努力的方向 关键词：排序安装时间，准备时间资源约束，成组 s i n g i em a c h i n eg r o u ps c h e d u n gp r o b i e mw i t h s e t u pt i m e a b s t r a c t s c h e d u l i l l gp r o b l e mi s 觚i i n p o r t 锄t b 咖1 c hi i lc 伽【l b 证a t o r i a lo p t i 面z a t i o n 1 k h e d u l i i l gp r o b l e mh 嬲am 萄o rc 1 1 a r t e f i s t i cw l 斌h 舔s 0m a n ym o d e l s o n em o d e l m a ya p p l yt oap a r t i c u l a rm o d e la l g o r i l m a sl o i 培a s 廿l em o d e ll l 璐al i t t l ec h a n g e ， t h ea l g o r i 廿1 mi nt l l a tc o n d i t i o i l sm a y1 1 0 ta p p l yt 0 虹l i sc o n d m o i l s h lm a n ys c k d i l l i l 培 p r o b l e m ，t l l es e t u pt h ei su s i i a l l y 嬲s u 】 i l e dt 0b eac o l l j ；t a l l _ t ，b u ti i ir e a l i 哆，t l l es e t u p t i n l ei s 埘毗e x i s ti i l d 印e n d e n t l y ni si m p a c t e db yp r o c e s s i i l gt i m e s oi ti sm o 佗 i n l p o r t 如tt or e s e a r c h 也es e t u pt i r i l ew 1 1 i c ha r ep r o p o r t i o n a t et 0m el e n g mo f 恤 a l r e a d ys c h e d u l e dj o b s i nt l l i ss o r to fm o d e l ，o n et h ec a np r o c e s s e daj o b 锄l dt ： l ej o b c 觚tb eb r ea ：ko f t t l i sp a p e rm 枷yd i s c u s sn l es i n g l en l a c l l i n e 母- o u p 妣d l j l i i l g p r o b l e mw i t l ls e n l pt i m e i nt l l i sp a p e r ，w e 砷r o d u c ef i 玛t l ym ed e 矗n i t i o no fas c h e 伽i n gp r o b l e m ，吼dt l l e c l 嬲s i f i c a t i o i l ，嬲、e u 嬲s o m er e s e a r c hr e s u l t so fs c h e d u l i n gp r o b l e mw 砒is e n j p 妇 钺l dm es i l l g l em a c l l i n e 母o u ps c h e d u l i l 唱p b l e m t h es i n 哲e m a c l l i n e 目0 u p s c h e d u l i n gp r o b l e m 、7 l ，j 恤s 曲u pt i i n ei sd i s c u s s e ds e c o n d l y i i lt 1 1 es e c o n dc h 印t e r ，w e 呶l d i e s 1 es i n g l e m a c 曲1 es c h e d u l i n gp r o b l e m sw 池r e a d yt i m ea n ds e n l pt i m e e v e 巧 j o bl l a sr e a d y 劬ea n de v e 巧g r o u ph 髂s 咖t m l e s e t u p 血n e sa r ep r o p o r t i o 彻t et ot l l e l e n g t l lo ft l 圮a l r e a d ys c h e d u l e dj o b s o n et i m ec a np r o c e s s e daj o ba n dt l l ej o bc 锄t b eb r e a l 【o t h ef o l l o w i r 唱。场e c t i v e 缸1 c 6 0 ni sc o 璐i d e r e d ：m em a x i l i l 啪c 0 i n p l e t i o n t i i r 伧( m a k e s p a n ) ，a i l dt l l ep 0 1 y t l o m i a la l g o r i t l u n sa r ep r e s e n t e df o rt l l ep r o b l e m ， m e 删l eu s es p e c i f i ce x 锄叩l e st oe x p l a i l lt l l ea p p l i c a t i o no ft h ea l g o r i t i l l i l s i l l 圮 蝴c h a p t e r ，t 1 1 es i i 坞l em 1 1 i n e 圉o u ps c h e d l l l i i 唱p r o b l e mw i t l lr e s o u r c ed e p e n l l e n t p r o c e s st i i l l c 钺l ds e t u pt 妇e i tc o n t a m st 、op r o b l e m s o nt l l eo r 圮i 删1 d ，t l l eo 功e c t i v e i st 0m i l l i m i z e l et o t a lr e s o u r c ec o n s u m p t i o nu r l d e rt 1 1 em a k e s p a nc o n s t r a i l l s ，o n 廿l e 池rl 姗dn l eo 均e c t i v ei st 0m 洫m i z e l em a l 【e s p 趾i nt l l e s ep r o b l e m s ，也ej o b si i l t l l es 锄eg r o u ps h o l l l d n tb es e p a r a t e d ，廿1 es e t u pt i m eo fag r o u pi sal i n e 盯 n o n _ i n c r e a s i l l gm n c t i o no f 1 e 锄o m to fr e s o u r c e sc o i l s u i m d f i i l a l l y ，t h ew h o l e d i s r t a t i o ni ss 岫m 面z e d r e s e a r c hw o f ki i lt l l e 氕n ：u r ei sp o i l l t e do u t k 叠w o r d s ：s c h e d u i i n g ，s i n g i e - m a c h i n e ，s e t u pt i m e ，r e a d y t i m e ，r e s o u r c ec o n s t r a i n e d ，g r o u p ， 学位论文独创性声明 本人所呈交的学位论文是在导师的指导下取得的研究成果。据我 所知，除文中已经注明引用的内容外，本论文不包含其他个人已经发 表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体， 均已在文中作了明确说明并表示了谢意。 作者签名：幺雌日期：上垫堕- 址 学位论文使用授权声明 本人授权沈阳师范大学研究生处，将本人硕士学位论文的全部或 部分内容编入有关数据库进行检索；有权保留学位论文并向国家主管 部门或其指定机构送交论文的电子版和纸质版，允许论文被查阅和借 阅；有权可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后适用本规定。 作者签名： 盈i ) 塾鸳 日期：垫监! ：l 带有安装时间的单机成组排序问题 第一章引言 排序问题( s c h e d u l i n gp r o b l e m s ) 也称调度问题，是组合最优化中的一 个重要分支n 。3 1 其所研究的问题是最优地完成给定的工件或任务在执行 这些工件或任务时需要满足某些限制条件，如工件的到达时间、工件完工 的限定时间、工件的加工顺序影响等等排序论作为运筹学的一个分支，有着 深刻的实际背景和广阔的应用前景，排序论一直受到国际学术界的重视排序问 题产生的背景主要是机器制造，后来被广泛应用于农业、制造业、运输业、管理 计算机科学等领域排序理论的研究是从二十世纪五十年代初期开始的由于研 究排序问题的方法涉及组合最优化的各个分支，如线性规划，整数规划，动态规划， 计算复杂性理论等，因此自从它创立以来就得到运筹学、信息管理、计算机科学 等学科领域的普遍重视 随着现代工业的发展，经典的排序模型已被突破，新模型层出不穷，新模型排 序的特征是突破了经典排序关于资源类型，确定性，可运算性，单目标和正则性等 基本假设，因此吸引了越来越多的理论工作者和实际工作者特别是新模型排序 的丰硕结果，使排序论成为研究活跃、前景诱人的学科领域之一本文所研究的带 有的安装时间的单机成组排序问题，就是一种关于安装时间的新模型的排序 一、排序问题的定义 排序问题是一类重要的组合最优化问题，它是利用一些处理机( p 敝e s s o r ) 、 机器( m a c h i n e ) 或资源( r e s o u r c e ) ，最优的完成一批给定的任务( t a s k ) 或作业 ( j o b ) 在执行这些任务或作业时需要满足某些限制条件，如任务的到达时间、完 工的限定时间、任务的加工顺序、资源对加工时间的影响等最优的完成指的是 使目标函数达到最小，而目标函数通常是对加工时间长短、处理机的利用率的描 述 在排序问题中，由于处理机的数量和种类，任务和作业的顺序、到达时间、完 工限制、资源的种类和性能等情况是错综复杂的，为此我们常常用到如下的基本 参数： 设有忍个工件，记为以，：，l ；有，l 台机器，记为m 。，m ：，肘。 既( 或p f ) ( p 眦e s s i n gt i m e ) 表示工件- ，f 在机器m i 上的加工时间( 简称工时 当巩= p ，时，说明工件的加工时间与选择的机器无关或所研究的问题是单机问 带有安装时间的单机成组排序问题 题 r ( r e l e 弱e 纰) 表示工件j ，的准备( 到达) 时间 d f ( d u e 妣) 表示工件- ，的交工期如果工件在它的交工期之前完成，我 们称之为按期完工的工件( o n t i m ej o b ) ；否则，我们称之为误工的工件( t a | 由 j o b ) 对误工的工件有时需要一定的罚值 w f ( w e i g l l t ) 表示工件，f 的权重 c f ( c o m p l e t i o nt i m e ) 表示工件，的完工时间 三，= c ，一d ，( 1 a t e n e s s ) 表示工件，的延迟 乃= 小锻 o ，q d ，】( 切r d i n e s s ) 表示工件，的误时 弓= m a 】【 o ，嘭一q 】( e 砌i n e s s ) 表示工件的提前完工时间 通常我们规定： ( 1 ) 任务或作业和处理机是有限的； ( 2 ) 工件一旦开始加工，则一直加工到完毕( 除非有允许中断的声明) ； ( 3 ) 每个工件必须在它的到达时间之后加工 排序问题的分类 目前文献通常采用三参数分类法，即口例y ，它们具有下边的含义 口域表示处理机的数量、类型和环境，它可以是 口= 1 ( s i n g l em a c l l i n e ) ：单处理机 口= 己( i d e n t i c a lm a c h i n e si np a r a l l e l ) ：m 台同速机 口= 绒( m a c h i n e s i np a r a l l e lw i t hd i 骶r e n ts p e e d s ) ：m 台恒速机 口= 毛( u n r e l a t e dm a c l l i n e si np a r a l l e l ) ：m 台变速机 口= 巴( n o ws h o p ) ：，l 台处理机，流水作业 口= d m ( o p e n j o b ) ：，l 台处理机，自由作业 口= ，。( j o bs h o p ) ：m 台处理机，异序作业 域表示工件的性质、加工要求和限制，它可以是 = 工件有不同的准备时间( 到达时间) = j ，工件有不同的安装时间 = 施砌表示工件是分批进行加工的分批排序模型按分批方式的不同分 两大类：串行分批和并行分批 在串行分批模型( s _ b a t c h ) 中，机器在每一时刻只能加工一个工件，工件是 按照一个接一个串联的方式形成一批，同批的工件完工时间为该批最后工件的 完工时间，批的加工时间定义为该批中所有工件加工时间之和：在并行分批模 型( p - b a t c h ) 中，机器在每一时刻可同时加工多个工件，同批的工件完工时间相 2 带有安装时间的单机成组排序问题 同，批的加工时间定义为该批中所有工件加工时间最长看 7 域表示要优化的目标函数，它可以是 y = c 眦：时间表 7 = q ：总完工时间 y = m q ：加权总完工时间 y = k ：最大延迟 7 = u j ：延误工件总数 y = 叶u ，：加权延误工件总数 7 = 乙：延误工时总和 三、带有安装时间的成组排序问题 排序问题最早起源于机器制造业，现在已经逐渐发展成为运筹学、系 统科学、控制科学、管理科学和计算机等多个学科领域的交叉学科，广泛 应用于工程技术和经济管理的各个领域作为一门应用科学，它在作业安 排、制造工厂的最优设计、交通枢纽的排序及工程进度的控制等方面有着 深刻的实际背景和广阔的应用前景 典排序问题中是假设每个工件都是独立存在的，但是在实际的生活应用中， 为了提高生产效率，利用工件的某种性质将工件分成若干组再进行加工，这种方 法和原理就是目前比较热门的成组技术如何确定组间顺序和组与组之间的顺序， 就是分组问题的关键由此可见，分组排序是经典排序的推广成组排序问题是重 要的现代排序模型之一，目前在文献中受到了普遍的关注陋1 在成组排序问题中， 工件可以分成“类似”工件的工件组同组工件连续加工时不需要安装时间，不同 组工件连续加工时，需要一定的安装时间n 2 儿1 3 1 张峰对工件的加工时间是开工时 间的简单线性函数的成组排序问题作了讨论，在满足成组技术限制条件下极小化 最大完工时间u 4 1 随着现代工业的发展，经典的排序模型已被突破，新的模型层出不穷，吸引了 越来越多的理论工作者和实际工作者h _ 7 】可控排序、多目标函数、成组分批排 序、同时加工排序、准时排序、资源受限排序、随机排序、模糊排序、应用排序 等等，本文所研究的机器具有安装时间的排序问题就是一种新型排序 在经典排序问题中，安装时间独立存在或非独立存在在许多排序问题中，安 装时间通常假设为常数k b u l a m 弱和k y p 撕s i s 给出了和已经加工完成工件的加 工时间有关的安装时间，这种安装时间的新模型主要存在于高科技的制造业中， 并且由大量的工件组成的一批电子工件，当这组工件被安装到集成电路板上，只 3 带有安装时间的单机成组排序问题 能被机器连续加工当它们被安装到集成电路板上时，机器加工这些电子工件的 任何一个时，对其他准备就绪但还没有被加工的工件会产生不利的影响，这是因 为当电流流过集成电路板时，机器也在工作任何一个没有准备就绪的元件的准 备就绪程度和等待对其加工的时间是成比例的，因此，在机器加工一个元件之前， 需要进行一个调整操作，即安装时间，把没有准备就绪的工件调整到准备就绪的 状态，集成电路板上的所有工件被机器加工完时，则完成了整个制造过程文献 2 3 中主要给出了含有这类安装时间即： 设f = 丑，：，= 1 ，2 ，小) 表示m 个工件组集合，第f 组包含n ；个工件，即 - ，n ，锄， 的加工时间为p ，对每个工件，i f 仅属于一个组b ( j f = 1 ，2 ，甩；) 所有工件在机器上加工按照如下方式进行：机器一次只能加工一 个工件，工件不可中断，组内工件连续加工，组和组之间需要安装时间，且安装时 间和已经加工完工件的加工时间有关，即对任意排序b 。) ，b ：) 一，召( 。) ，& j ) 的安 装时间为： j i 一 墨刀= 易p 蛔 ， _ = 2 ，3 ，m ， 且墨l 】= o = lg = l 其中易o 为已知常数把这类安装时间记做s 叫 在经典排序问题中，安装时间独立存在或非独立存在在许多排序问题中， 安装时间通常假设为常数，但在现实中，安装时间往往不是独立存在的，往往 需要受加工时间的影响，因而研究和已经加工完工件的加工时间有关的安装时间 的单机成组排序问题显得尤为重要，其难度不回低于经典排序 四、本文的工作 有关安装时间的排序模型的研究近年并不多见，因此本文将主要研究两类 带有安装时间的成组排序问题 在本文里，我们考虑的是：工件带有安装时间的成组排序问题在第二章中主 要是对工件带有安装时间和准备时间的单机成组排序问题进行了讨论，其目标函 数为极小化最大完工时间本章的主要工作就是在原模型的基础上增加工件具有 准备时间且成组的问题，既有安装时间又有准备时间，无疑增加了问题的难度性 其结果是依然能给出求解最优排序的多项式算法第三章，主要研究了带有安装 4 带有安装时间的单机成组排序问题 时间和工件的加工时间受资源约束的单机成组排序问题，分别对目标函数是在满 足最大完工时间限制条件下，极小化资源消耗总量，以及目标函数在满足资源消 耗总量限制条件下，极小化最大完工时间，分别给出了最优排序算法和资源的分 配方法 5 带有安装时间的单机成组排序问题 第二章带有准备时间的单机成组排序问题 一、引言 本章主要研究带有安装时间和准备时间的单机成组排序问题在成组排序问 题中，工件可以分成“类似 工件的工件组同组工件连续加工时不需要安装时间， 不同组工件连续加工时，需要一定的安装时间w h i l s o n ，l ( i n g ，h o d g s o n 讨论了不 相似组之间有安装时间的成组流水排序问题n5 1 r a s 眦衄锄l o g e n d r a l l ，s a r a c a r s o n ，e r i kh 锄s o n 讨论了在柔性流水作业中的成组排序问题u 6 1 k | 0 u l 锄a s 和 l 【y p 撕s i sa l l a l l v e r d i ，g u p t a ，舢d o w a i s 锄总结了一些具有安装时间的排序问题n 上述问题所描述的为具有安装时间但无准备时间的排序问题，但在较强的背景下， 工件加工前往往需要准备时间n 8 。2 孙世杰讨论了安装时间为常数情况下，工件 带有准备时间成组排序问题的最优算法瞳钉本章将k b u l 锄弱和k ) ，p 碰s i s 给出的 模型进行了推广，在原模型的基础上增加工件具有准备时间且成组的问题，所以 本章讨论了带有准备时间和安装时间的单机成组排序问题，其中安装时间和已经 加工完工件的加工时间有关 二、问题1 h 州，g 丁i c 一 用三参数表示法将问题记为： 1 l ，s 州，g r l c 呲 ( 1 ) 对于问题1 i ，j 脚，g 丁i 的最优排序由算法2 1 给出 算法2 1 ( 1 ) 把各组中的工件按准备时间不减排列，设第j f 组曰，中工件的排列顺序 为： 乃i ，乃2 ，且0 1 0 2 ，j = 1 ，2 ，m ( 2 ) 对第j 组曰，计算出每组工件的完成时间，即 r 醇p k + 七p 缸i = m a x o l + p j l + p j 2 + + p 一，吩2 + 乃2 + + p 盹，+ p ) ( _ = 1 ，2 ，m ) n ft 一l ( 3 ) 在当前未加工的工件组中，选取吃( d = + 易p 詹一p 由的值为最 6 带有安装时间的单机成组排序问题 小的工件组进行加工其中，为上式中所表示的，茎p 由为第j 组 r l 内所有工件的加工时间和，p 为为第j 组内前七。一1 个工件和。 口- i ( 4 ) 如果所有工件组都已加工完成，则停止：否则转步骤( 5 ) 。 ( 5 ) 待加工工件组的安装时间结束后，如果存在组，其组内的所有工件在加 工前均已到达，即：设f 为待加工工件组安装时间的完成时间，对于组 七一1 内各个工件有 吃( o ，即 万，t l啦f l + 易一p 妇 幺+ 6 如一 将万做如下变动，对调工件组曰，和置的位置，保持其余工件组位置不变，从 而得到另一个排序宠，则按万排序，存在如下几种情况： i ) 在待加工组工件的安装时间完成后，两工件组b ，和b 内各工件都无全 部到达 ”，七一l嘞一l 因为 + 易p 向一p 由 + 易一 所以 + 易羔p 由 一芝p 幻 ( 2 ) 口= l窖= l f - l 又因为 像 l + p 幻 口2 i l 所以 + 6 羔p 由 嘞 口= l “f，一1 鲰“， + p 问+ 易( + p 庙) 口= 埴 = l 口= l鼋= i 7 带有安装时间的单机成组排序问题 得到j n 在加工前已经到达 f _ l 因为 k 2 + p 幻 窖- 2 由( 2 ) 有+ 易羔p 庙 k 一兰p 幻 口- l覃= l 所以 + 易兰p 向 2 一p n 口= l + 兰+ 易( 呈艺+ 兰) + p i l ，：+ + 易( + ) + p i l ，： 俨l _ l 鼋_ l科 得到以：在加工前已经到达 同理可证，e 组内各工件在开始加工前均已到达 按万排序，情况如图( 2 1 ) 所示 图( 2 1 ) 万中组b j 和e 的加工完成时间为( 其中p 为组曰j 和e 之前已加工完组中 各工件的加工时间和) 协协+ l + 一+ p 玛州尸+ 薹p 为) 饥慨+ 一+ ( 3 ) 交换位置后存在两种情况：磊，死 按磊排序，情况如图( 2 2 ) 所示 口园口困固五巫墨互圆 k 图( 2 2 ) 磊中组马和曰j 的加工完成时间为 岔+ 如+ 靠“+ + + 纵p + 否p 幻) + p 丑+ p j ：+ + p 按是排序，情况如图( 2 3 ) 所示 8 ( 4 ) 带有安装时间的单机成组排序问题 死中组e 和曰j 的加工完成时间为 r 礅p 准+ p 扣l 从而，( 3 ) 一“) 的差为 ( 3 ) 一( 5 ) 的差为 图( 2 3 ) i 1 t _ l 像+ 易一一( 像+ 易艺氏一如) 口= l口= 1口= l口= l = 吃( j ) 一) o ( 5 ) 易( j p + p 妇) + p n + p 1 2 + + p 锄 口= l 由于加工时间都为正，且易o ，所以有 一。 易( p + p 妇) + p l l + p 1 2 + + 。 o g = l i i ) 如果组曰j 内各工件在开始加工前均到达，组e 内各工件则没有全部到 达即： 七一l 对曰j 组内各工件有 o 口= - l鼋= lg = l i i i ) 如果噩组内各工件在开始加工前均到达，曰，组内工件则没有全部到达 f _ 1 即：对马组内各工件有 o 口= l 口。l口- 1 ( 8 ) 一的差为 易( p + p 庙) + n l + 鼽2 + + 鼋= 1 由于加工时间都为正，且易o ，所以有 6 ( p + p 妇) + p n + p 2 + + p 魄 o i v ) 待加工工件组的安装时间结束后，组b ，和b 内各工件在加工前均已到 达，相当于各组内工件没有准备时间，由于组内工件必须连续加工，所以组 内各工件可看成一个大工件进行加工，等价于不成组且无准备时间问题，证 明由文献 1 给出 综合以上情况，在假设条件下，显然有 ( ) 膏 ( ) 聋 与万是最优排序矛盾定理证毕 例2 1 考虑排序问题 1 l ，s 删，g 丁i c 一，其中玎= 3 ，易= 2 p l = ( 1 ，4 ，6 ) ，吒= ( 4 ，3 ，8 ) p 2 = b ，1 ，4 ) ，吃= 【2 ，6 ，4 ) p 3 = ( 2 ，7 ，9 ) ，毛= ( 4 ，7 ，9 ) 用算法2 1 求解其最优排序 用算法2 1 求解过程如下： 把各组工件，组内按准备时间不减的顺序排列 带有安装时间的单机成组排序问题 p l = “，l ，6 ) ，_ = ( 3 ，4 ，8 ) p ：= ( 3 ，4 ，1 ) ，r 2 = ( 2 ，4 ，6 ) p ，= ( 2 ，7 ，9 ) ，吩= ( 4 ，7 ，9 ) 先确定各组内工件的加工顺序 且：l i 2jl i l 嘲；3 如：砭lj 瓦3 召3 ：瓦lj & 嵋3 把组内顺序定完后，按新顺序从新定义p l l p 1 2 ，p 1 3 ，p 2 l ，p 2 2 ，p 2 3 ，p 3 l ，p 3 2 ，p 3 3 诗冀r 酊+ p 一+ 日：m a x n l + p l l + p 1 2 + p 1 3 ，吒2 + p 1 2 + p 1 3 ，巧3 + p 1 3 ， = m a ) 【1 0 1 4 ，1 1 ，1 5 ) = 1 5 曰2 ：m a ) 【 r 2 l + p 2 1 + p 勉+ p 2 3 ，屹+ p 2 2 + p 2 3 ，仫+ p = m a ) 【1 c l o ，9 ，7 ) = 1 0 岛：i i 均i ) 【乜l + p 3 l + p 3 2 + p 3 3 ，吩2 + p 3 2 + p 3 3 ，吩3 + p 3 3 ) = m a 】【伫2 ，2 3 ，18 ) = 2 3 吃l = 吒3 + 易( p l l + p 1 2 + p 1 3 ) 一( p i l + p 1 2 ) = 8 + 2 ( 4 + l + 6 ) 一( 4 + 1 ) = 2 5 吃2 = r 2 1 + 6 ( p 2 l + p 2 2 + p 2 3 ) = 2 + 2 ( 3 + 4 + 1 ) = 1 8 吃3 = 吃2 + 易( p 3 l + p 3 2 + p 3 3 ) 一p 3 l = 7 + 2 ( 2 + 7 + 9 ) 一2 = 4 1 所以先加工组风， s 2 = 2 ( p 2 l + p 2 2 + p 2 3 ) = 2 2 加工完组b 2 ，则组e 和组b 内的工件均以全部到达，则f = 1 0 + 2 2 = 3 2 l = f + 易( p l l + p 1 2 + p 1 3 ) = 3 2 + 2 ( 4 + 1 + 6 ) = 5 4 吃3 = f + 易( p 3 l + p 3 2 + p 3 3 ) = 3 2 + 2 ( 2 + 7 + 9 ) = 6 8 所以接下来加工组b ，最后加工组b 3 ，最大完工时间c 一= 9 6 问题1 i r ，j 州l c 一为问题1 i r ，s 州，g 丁i c 一的特殊情况，即1 i r ，s 州，g r i c 一不成 组的情况，故问题 1 2 带有安装时间的单机成组排序问题 1 | 州i c 眦 o d 的最优排序由算法2 2 给出 算法2 2 ( 1 ) 在当前未加工的工件中，选取，+ 助f 值为最小的工件进行加工 ( 2 ) 如果所有工件都已加工完，停止：否则，转步骤 ( 3 ) 待加工工件的安装时间结束后，如有工件在工时间前到达，即：设f 为待 加工件安装时间的完时间，有0 f + p j ，则0 = f ，步骤( 1 ) ：否则转步骤 ( 1 ) 证明方法如算法2 1 证明同 带有安装时间的单机成组排序问题 第三章加工时间受资源约束的单机成组排序问题 一、引言 在经典的排序问题中，通常假设工件的加工时间是常数，且不考虑资源消耗 以及成组技术限制但在某些具有较强实际背景的排序问题中，这些假设可能并 不满足加工时间受资源约束的问题在生产管理领域有着广泛的应用，如得到一 种资源( 如机械加工中的特殊的润滑计，化工产品的催化剂等) ，工件的加工时间 会线性的减少由于这类排序问题在实际生活中的重要作用，所以有很多研究工 作者正在从事这方面的研究 加工时间受资源约束的排序是排序理论的重要组成部分，这类问题在生产管 理领域有着广泛的应用，如得到一种资源( 如机械加工中的特殊的润滑计，化工产 品的催化剂等) ，工件的加工时间会线性的减少由于这类排序问题在实际生活中 的重要作用，所以有很多研究工作者正在从事这方面的研究口4 。嬲1 在资源约束排序问题中，对于工件的准备时间是资源消耗量的函数的情 况，c h e n g 和j 锄i a k 讨论了满足最大完工时间限制条件下，极小化资源消耗总量的 资源最优控制问题晗9 1 ，j 锄i a k 讨论了满足资源限制条件下极小化最大完工时间的 问题湎1 j 锄i a l 【，k b v a l y o v ，m 撕e c l a u d ep o r t m 锄n 讨论了对各工件组分配量相同， 且对每个工件分配资源量相同时，在各工件完工时间受工期限制条件，目标函数 为极小化加权资源和的问题口 本章讨论了带有安装时间且工件的加工时间受资源约束的单机成组排序问 题对目标函数在满足最大完工时间限制条件下，极小化资源消耗总量，以及目标 函数在满足资源消耗总量限制条件下，极小化最大完工时间，分别给出了最优排 序算法和资源的分配方法 二、问题描述 设罗= b ，：厂= 1 ，2 ，珑 表示册个工件组集合，第f 组包含壤个工件，即 - ，n ，j 2 ，毗，- ，玎的加工时间为既，对每个工件，盯仅属于一个组e ( 7 = 1 ，2 ，咒；) 所有工件在机器上加工按照如下方式进行：机器一次只能加工一 个工件，工件不可中断，组内工件连续加工，组和组之间需要安装时间，且安装时 间和已经加工完工件的加工时间有关 工件，牙的加工时间既是一个依赖资源量的线性非增函数即凡= 劬一h ；， 1 4 带有安装时间的单机成组排序问题 其中留 为常数部分，口 是资源消耗率，q 和口 f 都为已知量同一个组的工件分 配的资源相同，分配给工件- ， 的资源“；受到如下限制：o “；瓦( f = 1 ，2 ，小) 其中瓦是工件所能得到的资源上限本文主要讨论了两种问题，一种为目标函数 在满足最大完工时间限制条件下，极小化资源消耗总量，另一种为目标函数在满 足资源消耗总量限制条件下，极小化最大完工时间 三、问题1 i p = 锄一嘞“。，s 州，g ，“， d l 对于问题 1 h = g 一口耵比f ，s 脚，g ，“j d i c o 乃 的最优排序和最优资源分配方法由算法3 1 给出 算法3 1 ( 1 ) 分别计算各组内的p f ，使得只= 艺鼋 ( 扛1 ，2 ，m ) j = 1j 篇l ( 2 ) 组内顺序任意排列，组间顺序按只大小，由小到大的顺序排列， 把排 列好的顺序的工件组记作b ，曰2 ，巩 ( 3 ) 分别计算 l + ( m f ) 易 ( 口j 1 + q 2 + + 口l 。，) ，使得 d j = 1 + ( m f ) 6 ( 口i l + 口i 2 + + 口l 。) ， 其中，j = 1 ，2 ，m ( 4 ) 对f - 1 ，2 ，小，置“；= o ( 5 ) 在当前没有分配资源的工件组中选取g ，使得以= m a ) 【碱 ( 6 ) 置“? = i i l i n 玩，d ，d = 痧一m ； ( 7 ) 如果任务分配资源结束，或者资源痧分配完，停止。否则转( 5 ) 定理3 1 对于问题，算法3 1 给出的排序是最优排序 证明当给定，z 组工件时，有 第一组蜀： p 1 12 儡l 一口1 1 蚝 p l i2 留l ，l - 一口l “l c l ，：艺钆叫羔 - lj = l 1 5 第二组b 2 ： s ：= 易( 艺钆 = l 飞艺) 1 p 2 i = 鸟2 l 一口2 l “2 p 2 2 = 口勉一口2 2 “2 p 2 j 1 2 = 口2 也一口2 j 1 2 “2 ：( 1 + 易) 艺幻+ 兰一( 1 + 易) “。艺口u 一“：艺 j = l，= l ，= lj = l 第f 组e ： ： 1 + o 一1 ) 易) 羔留，j + 1 + ( i 一2 ) 易羔留：j + + ( 1 + 易) 艺g 删+ 羔幻 j = lj - lj - l j = l 一 1 + ( i 1 ) 6 ) “窆口。j j = l 第m 组召。： 一 1 + o 一2 ) 锄2 艺口2 厂一( 1 + 6 ) l 艺口叫1 j 口 f m 啊一- 一 j - l j - lj - l ： 1 + ( m 1 ) 易 艺目。j + 1 + ( m 一2 ) 易艺留：j + + ( 1 + 易) 艺口“j + 艺留， - l户lj = l，= l 一 1 + ( m 一1 ) 6 “艺口。j j - l 一 l + ( 小一2 脚：艺 j = l 监j坠 一( 1 + 6 ) “。一l 口。- l j 吲。 j 1，- 1 由式可以看出，组内的工件可以任意排列，组间要按照窆劬的大小， j = l 巧 口 兰芦 2 ”一 g 羔芦 + 2 s+ 唧 q = h c 带有安装时间的单机成组排序问题 由小到大排列，并且把资源分配给吐最大的，就可得到最优排序 四、问题1 i p = 锄一s 脚，g ，q “； 对于问题 1 l p = 劬一口 “l ，j 州，g ，c 邮c i “i 的最优排序和最优资源分配方法由算法3 2 给出 算法3 2 ( 1 ) 各组之间的排列按组内工件加工时间总和的不减顺序排列 ( 2 ) 各组内的工件排列任意 ( 3 ) 在c 。= c 条件下极小化资源消耗总量 ( 4 ) 对d ；较大的工件组鼠优先分配资源 定理3 2 对于问题，算法3 2 给出的排序是最优排序。 证明不失一般性，假设用b ；表示第f 组，用，。表示组e 中排在第j 个位置加 工的工件因此各个工件的完工时间如下， 第一组b ： c i l2 q l l 一口l l “l c 1 2 = ( 留l l + 留1 2 ) 一( 口1 1 + 口1 2 ) m l ：羔钆飞艺 驴易( 艺飞羔) j = l，= l 第二组b 2 ： c 2 l = q 1 + s 2 + 留2 l 一口2 l “2 c 2 22c l + s 2 + ( 留2 l + 留2 2 ) 一( 口2 l + 口2 2 ) “2 g 如= c l + j ：+ 羔一n ：羔 ，- lj = l s ，：6 ( 艺钆一“。艺) + 易( 艺一“。兰) j = l，= lj = lj - 1 1 7 带有安装时间的单机成组排序问题 最后一组巩： c 膈l = q l i k i + j m + 留辨l 一口棚h m c m 2 = c 。l - l 一i + s 。+ ( 留m l + g 。2 ) 一( 口m l + 口。2 ) “辨 c 棚- = 1 + ( m 一1 ) 易l 芝吼，+ l + ( m 一2 ) 易艺鼋2 j + + ( 1 + 易) - l j + ，l i”2 _ 一l监 j = lj = lj = l j = l 一 1 + ( m 一1 弦) “艺口。厂 1 + 伽一2 灿：羔口：厂 j - l j = l 一 一( 1 + 易) “m - l 艺口。- l j 咄。 j = l ，聋l 因此， c 觚：= 1 + ( m 1 ) 易) 艺口，+ 1 + ( m 一2 ) 易艺q ：j + + ( 1 + 易) 艺口，q j ，= lj = lj = l + 艺口阿一 1 + ( m 一1 ) 易 “。羔口。厂 1 + ( m 一2 ) 玩：艺口2 厂 卢1j = l j - l 一( 1 + 6 ) “。窆口m q 广“m 艺一( 1 + 6 ) “。- 1 口m - l 广“m 口阿 j = lj = l 由表达式第一部分 1 + ( m 一1 ) 易) 窆钆+ 1 + ( m 一2 ) 易艺口：j + + ( 1 + 易) 芝4 j + 艺可以看出， j = l j = lj = lj = i 与组内个工件的排列顺序无关，仅与组与组间次序有关，就可以转化成为 单机巾删i c 一问题由文献 2 3 可知，应按组内工件加工时间总和的不减 顺序排列最后一部分 一 1 + ( m 一1 ) 易 “。艺口j 一 1 + ( m 一2 ) 她：艺口：j 一( 1 + 6 撕。一。艺口川j 吲m 艺口阿 与各组顺序无关因此( a ) 和( b ) 得证在c 蛐c 前提下极小化资源总量 时，可以很容易得出在c 蛳= c 时，可以极小化资源消耗总量，( c ) 得证此时， 因为d i = 1 + ( m f ) 易) ( 口j l + 口i 2 + + 口l 。，) ( 江1 ，2 ，m ) ，在条件己给定时， 应对盔最大的组e 优先分配资源( d ) 得证 1 8 带有安装时间的单机成组排序问题 结论 相对于其它一些学科，排序问题的起源并不早，但是，排序问题的发展速度却 是相当的快排序这一门学科能够发展到今天这样重要的地位，不但是因为它在 理论研究方面具有深远的意义，而且由它产生的结论对指导现实生活中的实践问 题有很大的作用 本篇论文主要是围绕一类排序问题一带有安装时间的单机成组排序问题进 行讨论的第一章简要的介绍了排序的定义、排序问题的表示法和研究现状。第 二章研究了带有安装时间和准备时间的单机成组排序问题，在这里，只研究单 机、工件的加工不可中断、工件组的安装时间是和已经加工完工件的加工时 间有关的连续函数，对目标函数是极小化最大完工时间情况，给出了多项式最优 算法，并给出了算法实例本文的第三章主要对工件带有安装时间和工件的加工 时间受资源约束的单机成组排序问题的情况进行了讨论在这一章中，分别讨论 了在资源消耗量受限条件下极小化最大完工时间的最优排序和资源分配方法和 目标函数在满足资源消耗总量限制条件下极小化最大完工时间最优排序和资源 分配方法本文只是对一类带有安装时间的单机成组排序问题的一个初步研究， 此类问题的许多方面还没