（运筹学与控制论专业论文）加工时间随开工时间线性递减的排序问题.pdf

加工时间随开工时间线性递减的排序问题 摘要 排序问题是一类具有广泛实际背景的组合最优化问题，广泛应用于管理科 学，计算机科学和工程技术等众多领域。随着现代工业的发展，经典的排序模型 不断被突破。经典排序中通常假设，工件的加工时间是固定不变的常量，而且工 件只能在机器上顺次逐个加工。然而在实际问题中，有的工件的加工时间随其开 工时间变化而变化，而且有些工件可以作为一批一起加工，因此对这类排序模型 的研究具有重要的意义。本文主要研究工件加工时间随开工时间线性变化的平行 机排序问题及串行工件同时加工排序问题。 首先介绍了排序问题的定义、分类及表示方法，以及工件加工时间依赖开工 时间的排序问题和串行工件同时加工排序问题的研究现状。然后分别对工件加工 时间随开工时间线性递减的平行机排序问题和串行工件同时加工排序问题进行 了讨论。第二章主要讨论了两个具有两台处理机的排序问题：一是平行机排序问 题，另一个是每批恰为后个工件的串行工件同时加工排序的平行机排序问题。在 这两个问题中，工件加工时间均为开工时间的线性递减函数，目标函数均为极小 化总完工时间。对于第一个问题，证明了其最优排序可由工件按基本加工时间不 减排列得到，由此得出其最优算法，并指出了该结论对于相应的加工时间随开工 时间线性递增的情况不成立。对于第二个问题，根据其与第一个问题在某些性质 上的相似性，给出了其最优算法。最后指出本章所讨论的两个问题的结论均可推 广到川台处理机的情况。第三章讨论了一些工件加工时间随开工时间线性递减的 串行工件同时加工排序问题。分别就单机和流水作业的情况给予了讨论。对于单 机排序问题，讨论了目标函数为极小化最大完工时间、总完工时间、最大延误等 问题的最优排序的性质，同时就这些性质对相应的加工时间随开工时间线性递增 的情况成立与否给予了讨论。对于流水作业排序问题，主要考虑了两种特殊情况。 讨论了每批恰为七个工件、极小化最大完工时间问题的最优算法。论文最后对本 文的内容作了总结，并提出了未来工作的努力方向。 关键词：排序，串行工件同时加工排序，线性递减 s c h e d u n gp r o b i e mw i t h n e a r i yd e c r e a s i n g p r o c e s s in gt im e s a b s t r a c t s c h e d u l i n gp r o b l e mi sac o m b i n a t 砸a lp b l e mo f 舢i 蒯o nw m c hh 嬲a 谢d e 啪g eo fp r a c t i c a lb a c k g r o u i l d ，、杭d e l yu s e d 证m a i 塌g e m e n ts c i e n c e ，c o m p u t e rs c i e n c e 觚de n g i n e e r i n gt e c l l l l 0 1 0 9 y ，a n dm 锄yo t b 钉f i e l d s w i t l lt i l ee i e v e l o p m e n to fm o d e m i i l d u s 廿y ，l cc l 弱s i c a li n o d e l so ft h es c h e d u l i n gp r o b l e ml m r eb e e na d v a i l c e d c o n 北啪_ t l y 1 1 1 e c 1 嬲s i c a ls c h e ( 1 u l i n gp r o b l e mi s u s u a l l ys u p p o s e d t l l a t t l 地j o b p r o c e s s i n gt i i l l ci saf i e dc o 碰妇n t ，a n dt l l ej o b sc a no i l l yb ep r o c e s s e db yt h em a c h i 鹏 o n eb yo i 圮h o w e v e r ，i l lp r a c t i c e ，t 1 1 ep r o c e s s i l l g 缸eo fs o i n ej o b sd e p e n do nm e i r s t | r t h l gt i i n e s ，鲫ds 伽j o b sc 雒b ep r o c e s s e da sab 蹴h s o 也ef e s e a r c ho nt h e m o d e l so fs c h e d u l 崦p r o b l 锄i st 谢b l ys i 蛐f i c 趾t 1 1 1 ep 印e rm 血l yd 同s 谢t 1 1 p a r a l l e “d e n t i c a lm a c h i n e 蚓d _ i l l i n gp r o b l e ma n d 刚a lb a t i h i n gp r o b l 锄s 诵t h 也e j o bp r o c e s s i n gt i m ei sal i l l e 盯劬c t i o no fi t ss t a r t i n gt i m e a tf i r s tw ei i l n d d u c e 恤d e f i l l i t i o i l c l 硒s i 行c a t i o n 锄de x p r e s s i o no fs c h e d u l i i l g p m b l e m ，赳1 db a c k g r o u n do fs c h e d u l i i l gp r o b l e m 、肮mm ej o bp r o c e s s 协gt i m e 、 ，：i l i c h d 印e n d so ni t ss t a r t i i l gt i i n ea i l ds e r i a lb a t c l l i n gp m b l e m s t h e nw ed i s c u s st h e s c h e d u l i n gp r o b l e mo fp a r a l l e l i d e m i c dm a c m n ea n ds 耐a 1b a t c h i n gp r o b l 锄s 谢m n l ej o bp r o c e s s i i 培t 妇ew 1 1 i c hi sal i n e a rd e c r e a s i l 唱龟n c t i o no fi t s s t a r t i l l gt i l l l e ， 他s p e c t i v e l y i i lt h ec h a m e r2 ，、em a i l l l yd e a l 谢t 1 1t w os c h e d u l i n gp r o b l e m s 、 ，i m 伽o m 配e s ：o n ei s s c h e d u l i i l gp r o b l e mo fp a r a l l e li d e n t i c a lm a c l l i n e ，t l l eo t l l e ri s p a r a l l e l i d e n t i c a lm a c _ l l i n es c h e d u l i n gp r o b l e mo fs 嘶a 1b 批g p r o b l e m s 诵t l le 砒 b a l c hc o m 蛐g e x a c t l y后j o b s 1 1 1t l l e s e 铆op b l e m s ，t h ej o bp r o c e s s i n gt i m ei sa h n e 孤d e c r e a s i n g 如n c ： t i o no fi t ss t a r 曲gt i i i l e t h eo b j e c t i v ei st om i l ：1 i m i z e 廿1 et o t a l c o m p l e t i o nt i m e f 0 rm ef i r s tp r o b l e m ，、ep r o v et 1 1 a tt 1 1 eo p t i m a ls c h e d u l ec a nb e o b t a i n e db ys e q u e n c i i l gj o b si nn o n d e c r e 邪i i l go r d e ro ft h en o m l a lp r o c e s s i i i gt i i n e s ， o nn l i sb a s i s ，w e 西v ea no p t i l l l a la l g o r i 也mf o ri t ，a n dp o i n to u tt 1 1 a tt 1 1 es c h e d u l ei sn o t o p t i m 2 l lf o r 廿l ec o n s e q u e n t i a lc o n d i t i o nt l l a t l ej o bp r o c e s s i n gt i m ei sal i i 把髓 i i l c r e 鹊i n g 鼬c t i o no fi t ss t a r t i n gt i m e f o rt l l e c o n dp r o b l e m ，b 嬲e do nt l l e s i i i l i l a r 时o fs o i l l ep r o p e m e sb e 铆e e nt l l et 、op r o b l e m sd i s c u s s e di i l 也ec k 唾) t e bw e a l s og i v ea no p t i m a la l g o r i 衄f o ri t a t l ee i l do fc h a p i t e r2 ，w ep o i l l to u t 也甜t h e c o n c l u s i o i l so f l et 、op r o b l e m sm s c u s s e di i lt h ec h a p t e ra r eb o lt r u ef o rt 1 1 ec a s eo f mm a c t l i n e s h lt t l e c h a p t e r3 ，、耽d e a jw i ms e r i a jb a t c l l i n gp r o b l e m s 谢mj o b p 翩x 冶s s i l l gt 妇ew h j c hi sal i n e a r 她c r e a s i n gf h n c t i o no fi t ss 缸疆恤gt i i n e ，a n dc o n s i ( 1 e f m e 咖c o n d i t i o 璐o fs i n 酉em 批e 锄df 1 0 ws h o p f 0 rn 圮s 埘em a c h i n ep b l e m s ， w ed i s c u s sm ep r o p e n i e so f 廿l eo p 缸a ls c h e d u l e 、析mt ：h eo 场e c t i v e st 0m i i l i j i l i z e 也e m a l 【e s p a l l 也et o t a lc o m p l e t i o nt i i l 舱a n d 也em a x i m u m1 a t e r 圮s s ，粗dp o i i l to u t w h e t l l e rn l ep r o p e m e si sm l eo rn o tf o rt h ec o n s e q u e n t i a lc o n m t i o n 也a tt h ej o b p r o c e s s i n gt i l ：i l ei sal i i l e a ri n c r e 嬲i i 培如n c t i o no fi t ss t a r t i i l gt i n 圮f 0 rt h en o ws h o p p f o b l e m s ，w em a i l l l yc o 璐i d e r 佃os p e c i a jc o n d i t i o n s w | ed i s c u s st h eo p t i m a l a l g o r i t l l mf o rm ec o n d i t i o n 也a te a c hb a t c he x a c t l yc o n t a i l 塔七j o b s 锄d 廿l eo b j e c t i v e i st o1 1 1 j 嘶m i z em em a k e s p a l l i nn l el a s to ft l l ep a p e r w c ：m a l ( ea 姒田m a 巧o ft h e c 咖to f 恤p a p 锄d p u tf i o 删t l l e 抵砸o no f e 侬i r t sf o rt h e w o r k k e y w o 喇s ：s c h e d u n g ， s e a b a t c h i n gp r o b i e m s ， d e c r e a s e n e a y 学位论文独创性声明 本人所呈交的学位论文是在导师的指导下取得的研究成果。据我所知， 除文中已经注明引用的内容外，本论文不包含其他个人已经发表或撰写过 的研究成果。对本文的研究做出重要贡献的个人和集体，均已在文中作了 明确说明并表示了谢意。 作者签名：垒刍釜：丕。日期：丝星：支：墨1 学位论文使用授权声明 本人授权沈阳师范大学研究生处，将本人硕士学位论文的全部或部分 内容编入有关数据库进行检索；有权保留学位论文并向国家主管部门或其 指定机构送交论文的电子版和纸质版，允许论文被查阅和借阅；有权可以 采用影印、缩印或扫描等复制手段保存、汇编学位论文。保密的学位论文 在解密后适用本规定。 作者签名：垒互笙：垒。日期：婴呈：茎：墨l 加工时间随开工时间线性递减的排序问题 第一章引言 排序论又称时间表理论，是运筹学的一个分支，是组合最优化学科的一个重 要组成部分，广泛应用于管理科学，计算机科学和工程技术等众多领域。排序问 题是工业生产中一类带有普遍性的问题，将原材料通过各种机器加工成所需要的 零件需要排序；将生产出来的许多零件组装成某种产品需要排序；一个大型的工 程在兴建当中，必须对各类人员进行安排，对各种器材的供应进行调度，都需要 排序。这类问题，何时何地都可以看到。对于大型的、复杂的工作，排序的好坏 对工程费用的大小影响很大。这使得排序问题具有深刻的实际背景和广阔的应用 前景。 对于排序问题，不同的模型需要不同的方法去处理。有时，只要将模型的条 件稍加变化，原算法就将不再适用，这也是排序问题的一大特点，同时也使得排 序问题模型繁多。随着现代工业的发展，经典的排序模型已经被突破，新的模型 层出不穷，因此排序理论可分为经典排序和新型排序 1 。新型排序是相对于经 典排序而言，即非经典的排序。新型排序的特征是突破了经典排序关于资源类型、 确定性、可运算性、单目标和正则性等基本假设，主要包括可控排序、成组分批 排序、在线排序、同时加工排序、准时排序和窗时排序、不同时开工排序、资源 受限排序、随机排序、模糊排序、多目标排序等。 近些年来，从实际背景中提出的许多新的排序模型，使得排序论成为研究活 跃，前景喜人的学科之一。 一、排序问题的定义和分类 在排序问题中，工件( 作业) 是被加工的对象，是要完成的任务；机器是提 供加工的对象，是完成任务所需要的资源：排序问题是在一定的约束条件下对工 件和机器按时间进行分配和安排次序，使某一个或某一些目标达到最优。也就是 利用一些处理机、机器或资源，最优的完成一批给定的任务或作业( 工件) ，并 且在执行这些任务或作业时需要满足某些限制条件，如任务的到达时间、完工的 限定时间、任务的加工顺序、资源对加工时间的影响等。其中使目标最优或最好 的完成指的是使目标函数达到最小。而目标函数通常是对加工时间的长短、处理 机的利用率的描述 2 。 在排序问题中，处理机的数量和种类，任务或作业的顺序、到达时间、完工 限制，资源的种类和性能等情况是错综复杂的，很难用精确的数学描述给出一般 的排序定义。为此，我们用下列方式来描述排序问题。 加工时间随开工时间线性递减的排序问题 给定珂个任务的任务集，= 正，以，以 朋个处理机的处理机集肘= m ，鸩，帆 和s 种资源的资源集r = 是，恐，置) 排序问题指的是在一定的条件下，为了完成各项任务，把m 中的处理机和r ( 如果有) 中的资源分配给歹中的任务，使目标函数达到最优。排序问题基本上 是由处理机的数量、种类与环境以及任务或作业的性质和目标函数所组成。 排序问题按静态和动态，确定性和非确定性可以分为4 大类。本文所讨论的 问题是静态的确定性排序。确定性排序是指在排序问题中，所有的数据在进行决 策之前都是已知的。静态是指在加工开始时做出的安排，不随时间而改变。本文 所讨论的排序问题属于静态的确定性排序的范畴，因此下面我们主要讨论静态的 确定性排序的分类。 处理机、任务或工件和目标函数三要素组成了排序问题。由于这三要素具有 多种情况，故在此不将各种排序问题一一列举，只给出三要素的常见的几种情况。 处理机 单处理机：在排序问题中只有一个处理机。 多处理机：在排序问题中有多个处理机。 同类机( 平行机) ：在多处理机排序问题中，所有的处理机都具有相同 的功能。 同速机：所有的处理机都具有相同的速度。 恒速机：处理机的速度不同，但每个处理机的速度都是常数，不依 赖被加工的任务。 变速机：处理机的速度依赖被加工的任务。 多类机：掰个处理机具有不同的功能。 同顺序作业( 流水作业) ：每个作业需要在每个处理机上加工，而 且在处理机上的加工顺序相同。 异顺序作业：每个作业需要在每个处理机上加工，每个作业有自己 的加工顺序。 自由顺序作业( 开放作业) ：每个作业需要在每个处理机上加工， 每个作业可按任意顺序加工。 柔性流水作业：有s 类处理机，第，类有j ，个平行机，每个作业有s 道 工序，每道工序需要在每类平行机中的一个处理机上加 工，且每个作业的加工顺序相同。 任务或作业( 工件) 任务或作业( 工件) 的不同主要是由于其具有不同的性质和约束条件，下面 2 加工时间随开工时间线性递减的排序问题 只列举几种加以说明。 到达时间或准备时间：任务以已经准备好可以被加工的时间。如果所有的 任务的准备时间相同，取乃= 0 ，l = l ，2 ，狞。 工期z ：表示对任务正限定的完工时间。如果不按期完工，应受到一定的惩 罚。绝对不允许延误的工期称为截止期限。 优先因子m ：是一个权，它表示任务z 相对于其他任务的重要程度。 可中断或不可中断：可中断是指在排序问题中，每一个任务在加工时的任一 时刻都可暂停加工，加工该任务的处理机可去加工任何其他任务，以后可在任何 时刻在任意处理机上重新继续加工；不可中断是指在排序问题中，任何任务都不 允许中断。 优先约束：任务之间的优先约束是任务集上的一个偏序关系 0 。对于该模型的单机和流水作业的情况已经得到了充分讨论，而在 平行机和串行工件同时加工排序问题中的情况还没有研究，因此本文分别在第二 章和第三章对工件加工时间随开工时间线性递减的平行机排序问题和串行工件 同时加工排序问题给予讨论。 在第二章讨论工件加工时间随开工时间线性递减的平行机排序问题时，主要 解决的问题有： l 、证明问题j p 2 l p ，= q ( 1 6 f ) f c ，的最优排序可由工件按基本加工时间不 减排列得到，并由此得出其最优算法。并用数值例子说明这一结论对问题 尸2 i p 。= 口，( 1 + 所) i c ，不再成立。 2 、根据问题p 2 怍砌一1 ，a = q ( 1 6 f ) i c ，与问题p 2 l p ，= 口，( 1 6 r ) f c ，在 某些性质上的相似性，给出该问题的最优算法。 在本章最后指出上述问题的结论均可推广到朋台处理机的情况。 在第三章讨论工件加工时间随开工时间线性递减的串行工件同时加工排序 问题时，主要解决的问题有： 1 、给出问题1 p 一施砌，只= q ( 1 6 f ) ，曰i c l 腿的最优排序的性质，并据此给出 该问题的最优算法。 2 、证明问题1 b 一6 融，忍= q ( 1 6 f ) i q 的最优排序满足基本加工时间的 s p t 序。 6 加工时间随开工时间线性递减的排序问题 3 、证明问题1 l s 一6 础，只= q ( 1 6 f ) ，嚷i k 的最优排序满足工期的不减排 序。 4 、对两个特殊流水作业问题f ( 斗回l 珊，七一切一1 ，p ，= q ( 1 6 r ) ，吼= g i c 觚和f ( 万一夕) i 凇，七一切一1 ，a = q ( 1 6 f ) ，吼= g i c o 的最优算法给予讨论。 7 加工时问随开工时间线性递减的排序问题 一、引言 第二章平行机排序问题 本章讨论工件加工时间随开工时间线性递减的模型阢o ) = 绣( 卜6 r ) ，口，6 均 为非负常数。w a n g 等在文献 1 4 中主要讨论了该模型的单机和流水作业的情况。 本章主要对目标函数为极小化总完工时间的平行机情况给予讨论。对于目标函数 为极小化总完工时间、工件加工时间与开工时间有关的平行机排序问题的结论较 少。问题砌1 只= 即l c f 是n p 难的 1 8 ，问题砌i p 。+ 酬c f 的最优排序满 足工件基本加工时间的s p t 序 1 9 。 串行工件同时加工排序问题是同时加工排序问题中的一类问题，其主要特点 是工件在加工前首先被分成若干批，再逐批进行加工，同批工件在加工过程中不 允许被打断，也不允许被移走或加入新工件，工件的加工时间为其所在批包含的 所有工件的实际加工时间和，其完工时间为其所在批的最后一个工件的完工时 间。串行工件同时加工排序按照批容量( 一批所包含的最多工件数) 曰的大小可 以分为两类：第一类是b 0 是工件正的基本加工时间，6 0 是工件 的加工时间随开工时 间递减的速率。 为了保证p t o ) o ，我们假定6 ( 善口j 一口疵) 口，设以在时刻r 开始加工， 现交换工件。和j ，的位置，其余工件的位置不变，得到一个新的排列乃，在乃 中，的开始加工时间仍是f ，显然万与磊中只有z 和，的完工时间改变， 在万中，以和j ，的完工时间和为 ，+ q ( 1 6 ，) + r + q ( 1 6 ，) + 口，【1 6 0 + q ( 1 6 r ) ) 】 = 2 f + 2 q ( 1 6 r ) + 口，( 1 6 f ) 一口f 口，6 ( 1 6 ，) 在而中， 和j ，的完工时间和为 ，+ 口，( 1 6 ，) + ，+ 口，( 1 一所) + q 1 6 ( ，+ 口，( 1 6 f ) ) 】 = 2 ，+ 2 口f ( 1 6 r ) + q ( 1 6 f ) 一口f 口，6 ( 1 6 f ) 从而在万和乃两顺序下总完工时间之差为 ( 口l 一口，) ( 1 6 f ) 0 与万是最优排序矛盾，引理证毕。 定理2 1 对于问题尸2 b = q ( 1 6 r ) l c ，将工件按基本加工时间不减顺序 排列可以得到最优排序。 证明我们证明任何最优排序均可在总完工时间不增的条件下转化为满足 s p t 规则的排序。 设石是一个最优排序，由引理2 2 可知，在万中，同一处理机上的工件必然 满足s p t 规则，故在万中只有不同处理机m 。和m ，上的工件才可能不满足s p t 规则。设排在处理机m 上的工件z 与排在处理机m ：上的工件，是不满足s p t 规则且开工时间最小的两个工件，正和，的开工时间分别为f 1 和如，不妨设 l 口，处理机m 。上排在工件以后面的工件有珥个： z ，l ，正2 ，以 ，基本加工时间分别为口j l ，q 2 ，q ，处理机m ：上排在工件后 面的工件有一个：l 2 ，一，基本加工时间分别为乃 1 ，乃，2 ，口，。 1七 由g = 妻( 1 一n ( 1 6 q ) ) 可得，两处理机上排在以和前面的剩余工件的 ， j = 1 1 6 口，的乘积分别为1 一m 和1 一所，。 工件以，以l ，以2 ，以 的完工时间和为 妄h + 1 一( 1 一配) ( 1 一地) ( 1 + 兀( 1 - 她，) ) 】 ( 1 ) ， 七= l ，= l l o 加工时间随开工时间线性递减的排序问题 工件， l ， 2 ，一，的完工时间和为 力，i 圭n + l 一( 1 一鸲x 1 一鸭) ( 1 + 兀( 1 一鸭j ) ) 】 ( 2 ) 如果兀( 1 一她j ) o 对于其它不满足s p t 规则的工件可以同样处理，经过有限次互换工件位置 后可以使最优排序在完工时间和不增的条件下转化为满足s p t 规则的排序，定 理得证。 由此我们可以得到问题p 2 i n = 口l ( 1 6 r ) i c ，的算法如下： 算法2 1 s t e p l 将工件按基本加工时间不减排列，即q q + l ( 待1 ，2 ，玎一1 ) ； s t e p 2 当f = o 时，取前两个工件依次排在两台处理机上，以后每当有处理机 加工完某工件，则取排在最前面的工件排在处理机上，直到全部排完。 显然算法的时间复杂性为伏行l o g 疗) 。 在大多数情况下，加工时间随开工时间线性变化的问题结论对递减和相应递 增的情况同时成立，但定理2 1 的结论对于线性递增的情况并不成立，问题 p 2 i p ；= q ( 1 + 6 f ) l c ，的最优排序不满足s p t 规则。 例2 1 考虑问题p 2 i p 。= 口i ( 1 + 6 f ) i c ，其中疗= 5 ，6 = 2 ，q = 1 ，呸= 2 ，口3 = 3 ， 口4 = 4 ，岛= 5 ，岛= 0 按s p t 规则排为：排在第一台处理机上的工件顺序为，以；排在第二台 处理机上的工件顺序为厶，以； 此时，c l = 1 ，c 2 = 2 ，c 3 = 1 0 ，c 4 = 2 2 ，c 5 = 1 1 5 ，q = 1 5 0 如果排列为：排在第一台处理机上的工件顺序为z ，：，以；排在第二台处理 机上的工件顺序为山，以。 此时，c l = 1 ，c 2 = 7 ，c 3 = 5 2 ，c 4 = 4 ，c 5 = 4 9 ，q = 1 1 3 显然，s p t 排序不是问题尸2 i p ，= q ( 1 + 所) l c ，的最优排序。 四、问题p 2 卜加一1 ，a = q ( 1 一圳c 引理2 3 在工件数为以= 概的问题1 i 七一伽一1 ，b = q ( 1 6 ，) i c 中，如果第 一批的开始加工时间气= 0 ，且第f 个加工的批忍所包含的工件为 ，q ) “，正，q ) “：，正，q ) t “，( j = 1 ，2 ，嚷) ，则c ，= 詈【一兀( 1 6 q ) 】，并 ， m ， 且最优排序满足工件基本加工时间的s p t 序。 证明现用c f 表示第f 批工件的完工时间，扛1 ，2 ，则 c l = 吉【1 一枣( 1 也) 】 加工时间随开工时间线性递减的排序问题 c 2 = 扣尊( 1 圳】； = 扣鳟”蛐 总完工时间为 c ，= 后c i + 南c 2 + + 后q z 七2|i，kx七 = 詈魄一兀( 1 一眠) 一n ( 1 一蛔) - 兀( 1 一蚝) ：掣腓 扣1扣1 = 争仇一兀( 1 6 口1 ) 】 我们证明任二最优排序均可在总完工时间不增的条件下转化为满足工件基 本加工时间s p t 序的排序。 设万是一个不满足基本加工时问s p t 顺序的最优排序，则在此排序中至少 有两个相邻工件以，以排在前，但q 口，如果以，以在同一批中，由前 面的证明可知交换两工件以，的位置，总完工时间不变。如果以，在相邻的两 批j 9 i ，b ，中，设排在尽前面的批中所有工件的1 一帆乘积记为n 。，尽中除以外 其余工件的1 6 q 乘积记为兀：，交换两工件的位置，使之满足s p t 规则，显然 只有置的完工时间改变，交换前尽的完工时间为 1 【1 一兀ln 2 ( 1 6 口；) 】 交换后置的完工时间为 1 【1 一兀l 兀2 ( 1 6 口，) 】 所以交换前后总完工时间减少为 七n l n 2 ( q 口，) 0 对于其它不满足s p t 规则的工件可以同样处理，经过有限次互换工件位置 后可以使最优排序在完工时间和不增的条件下转化为满足s p t 规则的排序，引 理证毕。 在下面的讨论中，用n ，表示批垦中工件1 一她的乘积，也就是说，如果垦中 工件为山，l ，以 2 ，以乒，基本加工时间分别为口f l ，口啦，口啦，则兀，= 兀( 1 6 q ，) 。 引理2 4 对于给定分批方式( 每批工件数均为七，下同) ，极小化总完工时 间的两台处理机的平行机排序问题的最优排序可由各批兀。的不增排列得到。 证明将各批中工件1 6 q 的乘积看成一个工件的1 6 口；，易由定理2 1 的证 明得出该引理的正确性。 1 3 加工时间随开工时间线性递减的排序问题 引理2 5 对于给定分批方式，极小化总完工时间的两台处理机的平行机排序 问题的最优排序可由下列时间复杂性为d 0 l o g 刀) 的算法2 2 得到。 算法2 2 & 印l 计算每批中工件的1 6 口f 的乘积，即n 。，将批按兀。不增重新编号； s t 印2 取前两批依次排在两台处理机上的第一个位置，次两批依次排在两台 处理机上的第二个位置，依次取下去，直到取完为止。 引理2 5 证明根据引理2 4 ，显然骂，及排在两台处理机的第一个位置，马 排在墨后，由6 ( 口，一口硫) 1 ，可知o n ， l ，又兀l 兀2 n 3 ，故 n 。兀， c 也，故日排在岛后，同理可得岛j + l ，垦m 依次排在b ( 小岛( “卜2 后， 引理得证。 现在我们设计问题尸2i 七一切一1 ，p l = 口j ( 1 6 f ) i c ，的算法如下： 算法2 3 s t 印1 将刀= 概个工件按基本加工时间q 不减重新编号： s t 印2 取前七个为第一批，次七个为第二批，依次取下去，直到取完为止； 乳印3 将前两批依次排在两台处理机上的第一个位置，次两批依次排在两台 处理机上第二个位置，如此下去，直到排完为止。 定理2 2 算法2 3 产生问题p 2 i 七一切一1 ，a = q ( 1 6 f ) i c ，的最优排序。 证明我们证明任一最优排序均可在其总完工时间不增的情况下转化到满足 算法2 3 的排序。 假设某最优排序万不满足算法2 3 的分批排列方法，显然万中批的排列满足 引理2 5 ，且其中必有某批不满足算法2 3 的分批方式，现将批按兀i 不增重新编 号，将工件按基本加工时间不减重新编号。设第f 批是第一个不满足算法2 3 分 批方式的批。现应用引理2 3 将排在两处理机上的工件重新分批，再根据引理2 5 重新排列批，反复上述操作可以得到一新排列。在新排列中，排在处理机m 。上 第j 个位置的批的n ；不小于排在处理机m ：上第f 个位置的批的兀，排在处理机 m ：上第f 个位置的批的兀，不小于排在处理机m ，上第f + 1 个位置的批的兀。排 在处理机m 上的批数与排在处理机肘，上的批数相等或比排在处理机膨，上的 批数多1 。而且前f 一1 批的分批及排列方式与万中相同，且工件 正h 灿。，h m 2 ，h m i 均排在除前f l 批外每台处理机上最前面的批中。设 正h 渺，h 弦+ 2 ，正“) “ ，h ) 州岛，巴与色中其余工件分别记为 ，l ，一，厶 和，2 3 ，将两处理机上排在批和岛前面的批的 n 。的乘积分别记为么和刀，其后面的批分别为易，乓2 ，& 与 1 4 加工时间随开工时间线性递减的排序问题 色l ，反 2 ，乓一：，在下面的讨论中，工件的基本加工时间口与工件，的下标相同， 批中工件l 一6 口j 的乘积n 的下标也与批b 的下标相同。 如果兀p 兀g ，岛与色位置关系有两种情况( n p = 兀孽时，其它情况可在 总完工时间不变条件下转化到下面情况) ：( 1 ) b p 与乓排在相对同一含位置，b p 排在处理机m 上；( 2 ) 吃排在目的相对前一个位置，& 排在处理机m 上。此 时交换以，与州灿的位置，显然。口( “m j ，将乃与色中除以，与正f - l 灿外 其余工件1 6 口j 的乘积分别记为芦和兀茸，两种情况的变化情况类似，下面就第 一种情况给予讨论，此时，l l = 吃或啊= ，1 2 + l ，彳召，n 芦兀虿，交换后，总 完工时间减少 l 詈【+ 1 一( 么n 芦( 1 一抚o ) + 彳n 卢( 1 一& ) 兀砧+ + 彳兀声( 1 6 ，) n 兀，) 】+ 詈【啦+ 1 一( 曰n 孽( 1 一呶，一1 ) i u ) + 丑兀4 ( 1 6 q ，一1 ) + j ) 兀g ，l + + 召n 4 ( 1 6 & 卜1 ) i + ，) r l n g 。，) 】一 詈【+ l 一( 彳兀j ( 1 6 口( j 1 ) + ) + 彳n p ( 1 6 口( “) 七+ ，) n + + 么n 声( 1 6 口( 埘) 兀n ) 卜詈魄+ 1 一( 刀兀季( 1 6 。，) + 曰n i ( 1 6 郎，) 兀们+ + b n 口( 1 6 ，) n n g ，) 】 = 七( 一口( j - 1 ) 七+ _ ，) ( 彳兀卢+ 4 兀卢n p ，l + + 么n 芦r l n p 一 一b n 口一曰n 毒n 叮，1 一丑兀4ii 兀 ) o 如果兀p 0 是工件正的加工时间随开工时 间递减的速率。在下面讨论的问题中，我们始终假设工件的开始加工时间能够使 得a ( f ) o 。目标函数是极小化最大完工时间、总完工时间、最大延误等，当目 标函数为极小化最大完工时间时，对于批容量无限时的讨论没有意义，故只讨论 批容量b 有限的情况。这三个问题用三参数法表示为 1 l s 一6 口幻办，b = 珥( 1 6 r ) ，曰i c - m 珏； 1 i s 一6 口纪办，b = q ( 1 6 f ) i c j ； 1 i j 一6 口纪办，b = q ( 1 6 r ) ，4 i 厶掘。 2 流水作业问题 1 7 加工时间随开工时间线性递减的排序问题 设有拧= 饥个相互独立不可中断的工件以，以，以要在包含离散处理机和 批处理机两台处理机的流水作业系统中加工，所有工件在零时刻到达。对于批处 理机，工件在加工前首先要被分成拧。批，每批工件数恰好为七，每批工件在加工 前都有一个独立的安装时间j ，同批工件在加工过程中不允许被打断，也不允许 被移走或加入新工件，工件的加工时间为其所在批包含的所有工件的实际加工时 间和，其完工时间为其所在批的最后一个工件的完工时间。工件z 的加工时间a 的定义同上。目标函数是极小化最大完工时间。 在此流水作业问题中主要研究两种情况。现在我们用文献 3 0 中使用的记 号，用万表示离散处理机，即每个工件单独加工，加工完即可移走，用代表批 处理机，即工件成批加工，每批加工完后其所包含的工件方可移走，用专表示 流水作业流通方向，则万专表示先在离散处理机上加工，后在批处理机上加工， 用珊表示构成一批的所有工件都到达时才能安装，用阢和譬。分别表示工件z 在 批处理机和离散处理机上的加工时间，则我们要考虑的两种情况用三参数法可表 示为： f ( 夕专回i ，醇，七一加一1 ，b = 口j ( 1 6 r ) ，吼= g i c k ； f ( 万一历i 凇，七一切一1 ，a = q ( 1 6 f ) ，吼= g i c k 。 三、单机问题 引理3 1 在问题1 i 忍= q ( 1 6 f ) l c 眦中，最大完工时间与顺序无关，当开始 加工时间f o o 时，最大完工时间为c o = 瓴一扣珥( 1 6 口j ) + 吉 证明( 数学归纳法) 不失一般性，我们考虑排序万= 【以，以，以】。 c l = 岛+ 们一= f o + q q 纸= 瓴一( 1 一蛔) + 丢 c 2 = g + 口2 ( 1 6 c 1 ) = ( 一争( 1 一呐) + 吉+ 口2 【1 6 ( 瓴一( 1 一蛔) + 】odoo = 瓴一( 1 - 地) ( 1 一慨) + 吉 假设对于五成立，也就是说 q 娟一争珥( 1 山口j ) + 吉 g + 1 = q + q + l ( 1 6 q ) = 瓴一冉( 1 6 口f ) + 吉+ + l 一6 ( 魄一枣( 一地) + 妇 加工时间随开工时间线性递减的排序问题 = 纯一分珥( 1 一地) + 吉一嘎+ - 6 纯一争珥( 1 一帆) = 瓴一旁耳( 1 一地) + 砉 引理3 2 在问题1 l b = q ( 1 + 6 r ) l c 蛳中，最大完工时间与顺序无关，当开始 加工时间f o o ，最大完工时间为c 雠= ( 气+ 旁珥( 1 + 她) 一吉 ( 一) 问题1 p 一反始咖，a = 口f ( 1 一所) ，曰l e k 引理3 3 在问题巾一6 砌，a = q ( 1 6 f ) ，召i c | 雠的最优排序中，工件按基本 加工时间的s p t 序排列。 证明我们证明任一最优排序万均可在最大完工时间不增的条件下转化为满 足引理3 3 的排序。假设最优排序刀不满足工件基本加工时间的s p t 序，则必有 两相邻工件以，以排在，前，且q 口，当以，f 位于同一批时，交换两工件 的位置，显然工件最大完工时间不变，当z ，分别排在尽，曰，两批中时，交换工 件以与，的位置，设e 的开始加工时间为岛，墨，b ，中除以，j ，外其余工件1 一帆 的乘积分别记为4 ，彳，则曰，的完工时间减少为 1111 【瓴