（管理科学与工程专业论文）批处理机调度问题的模型与优化方法研究.pdf

，卜 u n i v e r s i t yo fs c i e n c ea n dt e c h n o l o g yo fc h i n a ad i s s e r t a t i o nf o rd o c t o r sd e g r e e r e s e a r c ho nm o d e l sa n d o p t i m i z a t i o nm e t h o d s f o r sche dulin gb a t c hp r o c e s s in g m a c hi n e s a u t h o r sn a m e ： s p e c i a l i t y ： s u p e r v i s o r ： f i n i s h e dt i m e ： d ub i n g m a n a g e m e n ts c i e n c ea n de n g i n e e r i n g p r o f h u a p i n gc h e n m a y5 m ，2 0 1 1 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均己在论文中作 了明确的说明。 作者签名： 签字日期： 兰! 出： 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入中 国学位论文全文数据库等有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内 容相一致。 保密的学位论文在解密后也遵守此规定。 日公开 口保密( 年) 作者签名： 签字日期： 导师签名： 签字日期： 摘要 摘要 批处理机调度是调度问题的一个重要分支。不同于经典调度问题，在批处 理机调度问题中，一台机器可以同时加工多个工件。由于这类调度问题不仅需 要将工件指派到机器上，还包含将工件分批的决策问题，因此比经典调度问题 更为复杂，很多己知的批调度问题均是n p 难解问题。 批处理机调度在现实生产环境中有着广泛的应用，包括半导体芯片生产， 钢铁制造，货物运输等。合理的调度方案可以大幅提高生产效率，节省生产成 本，因此对批处理机调度问题的研究有着重要的现实意义。 尽管当前己有不少文献对批处理机调度问题进行研究，但这些研究仍然有 着不足之处。一是研究的问题主要侧重于工件具有相同尺寸的较简单情形，较 少涉及不同尺寸工件情况。二是求解方法多是设计精确求解算法解决小规模问 题或是用简单启发式算法获得近似解，对于复杂的构造式方法较少有入研究。 三是研究的目标集中在以m a k e s p a n 为代表的生产效率型目标，而对于调度问题 中的能源效率则鲜有关注。 针对当前研究中存在的问题，本研究主要做了以下工作： ( 1 ) 从聚类视角下研究了不同尺寸工件批处理机调度问题。论证了差异工 件单机环境下的批调度问题实质为一种广义聚类问题，为求解该问题提供了一 个新的途径。提出了批的空间浪费比的概念，将最小化c n 。的目标函数变换为 最小化批的加权空间浪费比，从而可以更容易地寻找启发式信息指导分批过程， 两者的等价性也在文中给出了证明。此外，以批的空间浪费比为基础，进一步 定义了批间的距离度量，提出了批的约束凝聚聚类算法c a c b ，并通过实验验 证了算法的有效性。 ( 2 ) 将不同尺寸工件的批处理机调度问题推广到工件动态到达的并行机环 境，提出并证明了该问题的两个不同下界。在此基础上设计了两种智能优化算 法。一是基于工件序列编码的遗传算法，通过工件序列和b e s t f i t 规则生成分 批，并设计了一个e r t - l p t 算法来安排批在机器上的加工。另外一种是基于构 造式分批的蚁群算法，算法同时考虑工件在尺寸和加工维度的特点作为启发式 信息，指导蚂蚁不断寻找适合的工件加入当前批，直到所有分批构造完毕。对 两种算法的性能及偏好，通过大量仿真实验进行了比较。 ( 3 ) 将能源效率问题融入调度领域的研究中。构建了在分时电价条件下， 以最小化电力成本和m a k e s p a n 为目标的柔性流水车间批调度问题的模型。设计 了三种不同的多目标优化算法来求解该问题：即偏好向量蚁群系统p v a c s ，基 于n s g a i i 和基于s p e a 2 的进化算法，并比较了三种算法在不同评价指标下 的性能。 i 摘要 关键词：调度批处理机聚类蚁群优化多目标优化能源效率电力成 本 a b s t r a c t s c h e d u l i n go nb a t c hp r o c e s s i n gm a c h i n e s ( b p m ) i sa ni m p o r t a n te x t e n s i o no f c l a s s i c a ls c h e d u l i n gp r o b l e m s a sab a t c h p r o c e s s i n gm a c h i n ec a np r o c e s sag r o u po f j o b ss i m u l t a n e o u s l y , t h e r ea r et w oi n t e r d e p e n d e n td e c i s i o n st ob em a d ef o rs o l v i n 2a b p ms c h e d u l i n gp r o b l e m ，i c ，f o r m i n gb a t c h e sa n ds c h e d u l i n gb a t c h e s o nb p m t h e r e f o r e ，s c h e d u l i n go nb p mi sm u c hm o r ec o m p l e xt h a nc l a s s i c a ls c h e d u l i n 2 p r o b l e m s ，a n dm a n yo ft h e s eb p ms c h e d u l i n gp r o b l e m sh a v eb e e ns h o w nt ob e n p h a r d b a t c hp r o c e s s i n gm a c h i n e sa r ee n c o u n t e r e di nm a n yr e a l w o r l d a p p l i c a t i o n s s u c ha sb u m 。i no p e r a t i o n si ns e m i c o n d u c t o ri n d u s t r y , s t e e lm a n u f a c t u r i n ga n dt r u c k d e l i v e r y ag o o ds c h e d u l i n gm e t h o dm a y s u b s t a n t i a l l yi m p r o v ep r o d u c t i o ne f f i c i e n c v a n dr e d u c ep r o d u c t i o nc o s t ，i ti st h e r e f o r eo f p r a c t i c a ls i g n i f i c a n c et os t u d vb p m s c h e d u l i n gp r o b l e m s a l t h o u g he x t e n s i v ew o r kh a sb e e nd o n ei nt h ep a s td e c a d e st oa d d r e s sb p m s c h e d u l i n gi s s u e s ，s o m es i g n i f i c a n ta s p e c t so fb p m s c h e d u l i n gh a v en o tv e tb e e n s u f f i c i e n t l ye x p l o r e d t ob e g i nw i t h ，m o s tp r e v i o u sw o r kf o c u s e do nt h ed r o b l e m s w i t hi d e n t i c a lj o bs i z e ，w h i l en o n i d e n t i c a lj o bs i z e sh a v es e l d o mb c e nc o n s i d e r e d s e c o n d ，t h ea p p r o a c h e sd e s i g n e df o rb p m s c h e d u l i n gp r o b l e m sa r em a i n l ve x a c t a l g o r i t h m so rs i m p l eh e u r i s t i cr u l e s ，w h i l ec o m p l e xc o n s t r u c t i v ea p p r o a c h e s a r e r e l a t i v e l yf e w e r t h i r d ，r e s e a r c h e r si nt h i sf i e l da r em o s t l yc o n c e r n e dw i t hi m p r o v i n g p r o d u c t i o ne f f i c i e n c ys u c ha sm i n i m i z i n gm a k e s p a n h o w e v e r , e n e r g ye f f i c i e n c y i s s u e si n s c h e d u l i n g a r eo fe q u a l i m p o r t a n c ed e s p i t et h e yh a v es e l d o mb e e n a d d r e s s e d t h el a c ko fr e s e a r c hi nt h ea b o v ea r e a sn e c e s s i t a t e sf u r t h e ri n v e s t i g a t i o n si n t o b p m s c h e d u l i n gp r o b l e m s i nt h i ss t u d y , t h ef o l l o w i n gw o r kh a sb e e nd o n e ： ( 1 ) t h ep r o b l e mo fs c h e d u l i n gb p mw a sc o n s i d e r e df r o ma c l u s t e r i n g p e r s p e c t i v e i tw a sd e m o n s t r a t e dt h a tt h a tm i n i m i z i n gm a k e s p a no nas i n g l eb a t c h i n g m a c h i n ew i t hn o n 。i d e n t i c a lj o bs i z e sc a nb er e g a r d e da sas p e c i a lc l u s t e r i n gp r o b l e m ， p r o v i d i n gan o v e li n s i g h ti n t os c h e d u l i n gw i t hb a t c h i n g t h ed e f i n i t i o no fw r b ( w a s t er a t i oo fb a t c h ) w a st h e np r e s e n t e d ，a n dt h eo b j e c t i v ef u n c t i o no fm i n i m i z i n g m a k e s p a nw a st r a n s f o r m e di n t om i n i m i z i n gw e i g h t e dw r b s oa st od e f t n et h e d i s t a n c em e a s h r eb e t w e e nb a t c h e si nam o r eu n d e r s t a n d a b l ew a y t h e e q u i v a l e n c eo f t i f a b s t r a c t t h et w oo b j e c t i v ef u n c t i o n sw a sa l s op r o v e d i na d d i t i o n ，ac l u s t e r i n ga l g o r i t h m c a c b ( c o n s t r a i n e da g g l o m e r a t i v ec l u s t e r i n go fb a t c h e s ) w a sp r o p o s e db a s e d o nt h e d e f i n i t i o no fw r b c o m p u t a t i o n a le x p e r i m e n t ss h o w e dt h ee f f e c t i v e n e s so ft h i s a l g o r i t h m ( 2 ) t h ep r o b l e mo fs c h e d u l i n gb p mw a se x t e n d e d t oap a r a l l e lb p m e n v i r o n m e n t t h i sp r o b l e mi sn p h a r di nt h es t r o n gs e n s e ，a n dh e n c et w ol o w e r b o u n d sw e r ep r o p o s e dt oe v a l u a t et h ep e r f o r m a n c eo fa p p r o x i m a t i o na l g o r i t h m s a n e r t _ l p th e u r i s t i cr u l ew a sn e x tp r e s e n t e dt oa s s i g nb a t c h e st op a r a l l e lm a c h i n e s t w om e t a h e u r i s t i c s ，aj o bs e q u e n c eb a s e dg e n e t i ca l g o r i t h m ( g a ) a n da na n tc o l o n y o p t i m i z a t i o n ( a c o ) a p p r o a c hg u i d e db yh e u r i s t i ci n f o r m a t i o nt h a tw a sc o n s t r u c t e d u s i n gw r ba r ef u r t h e rp r o p o s e du s i n ge r t - l p tt o m i n i m i z em a k e s p a n t h e p e r f o r m a n c e s o ft h et w oa p p r o a c h e sw e r ec o m p a r e db yc o m p u t a t i o n a le x p e r i m e n t s ( 3 ) e n e r g ye f f i c i e n c yw a sc o n s i d e r e di nab p ms c h e d u l i n gp r o b l e m an e w m o d e lw a sc o n s t r u c t e dt om i n i m i z em a k e s p a na n de l e c t r i cp o w e rc o s ti naf l e x i b l e f l o ws h o pw i t ht h ep r e s e n c eo ft i m e o f - u s ee l e c t r i c i t yp r i c i n g t h r e em u l t i o b j e c t i v e o p t i m i z a t i o na p p r o a c h e s ，n a m e l y , p r e f e r e n c ev e c t o ra n tc o l o n ys y s t e m ( p v a c s ) ， n s g a i ia n ds p e a 2b a s e de v o l u t i o n a r ya l g o r i t h m sw e r ep r o p o s e da n dc o m p a r e d u s i n gd i f f e r e n tp e r f o r m a n c em e t r i c s k e yw o r d s ：s c h e d u l i n g ，b a t c hp r o c e s s i n gm a c h i n e ，c l u s t e r i n g ，a n tc o l o n y o p t i m i z a t i o n ，m u l t i o b j e c t i v eo p t i m i z a t i o n ，e n e r g ye f f i c i c e n y , e l e c t r i c p o w e rc o s t lllillliiliiiiiiiliiiii 目录 目录 摘要i a b s t r a c t ：- - - ，1 i i 目录 插图目录i x 表格目录一x i 第一章绪论1 1 1 引言l 1 2 调度问题的基本描述与求解方法3 1 2 1 调度问题的基本描述3 1 2 2 调度问题的求解方法5 l - 3 批处理机调度问题的研究现状6 1 3 1 单机环境批处理机调度问题6 1 3 2 并行机环境批处理机调度问题：8 1 3 3 车间环境批处理机调度问题8 1 3 4 现有研究的特点及存在的问题9 1 4 本文的主要研究工作与结构l o 1 4 1 主要研究工作l o 1 4 2 结构与内容安排l l 第二章聚类视角下不同尺寸工件批调度问题研究1 3 2 1 不同尺寸工件批调度问题的基本描述1 3 2 2 分批问题与聚类问题的比较1 4 2 3 批的空间浪费比的概念1 6 2 4 分批约束凝聚聚类算法( c a c b )1 9 2 5 仿真实验：2 3 2 5 1 实验设计2 3 v 目录 2 5 2 算法参数设置2 4 2 5 3 实验结果与讨论e o*c m 2 5 2 6 本章小结3 2 第三章工件动态到达批调度问题的遗传算法研究3 3 3 1 工件动态到达批调度问题的基本描述3 3 3 1 1 单机环境下的模型o o*dr0*bggt o * o 3 3 3 1 2 并行机环境下的模型3 4 3 2 工件动态到达问题的两个下界3 5 3 3 遗传算法及其在调度问题中的应用3 9 3 4 基于工件序列的遗传算法4 0 3 4 1 安排批加工的e r t - l p t 规则4 0 3 4 2 种群初始化4 l 3 4 3 选择操作4 l 3 4 4 交叉操作4 2 3 4 5 变异操作4 2 3 5 本章小结4 4 第四章工件动态到达批调度问题的蚁群算法研究4 5 4 1 蚁群算法介绍4 5 4 2 构造分批的蚁群算法4 6 4 2 1 算法初始化4 6 4 2 2 解的构造过程4 7 4 2 3 信息素更新4 9 4 3 仿真实验5 l 4 3 1 实验设计5 l 4 3 2 两个下界的测试5 2 4 3 3 算法的参数设置5 2 4 3 4 实验结果与分析5 4 4 4 本章小结5 8 第五章考虑电力成本的多目标柔性流水车间批调度问题研究5 9 5 1 能源效率问题产生的背景5 9 v i 目录 5 2 问题描述及数学模型6 2 5 3 多目标优化的基本概念6 3 5 4 p v a c s 算法6 4 5 4 1 解的编码和解码6 4 5 4 2 信息素表示6 7 5 4 3 启发式信息6 7 5 4 4 解的构造过程6 8 5 4 5 减少e p c 的r i g h t s h i f t 过程6 9 5 4 6 信息素更新 7 0 5 5 基于n s g a i i 的优化算法7 1 5 5 1 n s g a i i 介绍7 l 5 5 2 边界集的构造7 3 5 5 3 聚集距离的计算7 4 5 5 4 选择，交叉和变异操作7 5 5 6 基于s p e a 2 的优化算法7 6 5 6 i s p e a 2 介绍7 6 5 6 2 适应度分配7 6 5 6 3 环境选择7 7 5 7 仿真实验：7 9 5 7 1 实验设计7 9 5 7 2 算法评价指标7 9 5 7 3 算法参数设置8 1 5 7 4 实验结果与分析8 l 5 8 本章小结8 8 第六章总结与研究展望8 9 6 1 全文总结8 9 6 2 研究展望9 0 参考文献9 2 致谢9 9 v i i 目录 一一。 在读期间发表的学术论文与取得的其他研究成果1 0 0 v i i i 插图目录 插图目录 图1 i 芯片制造过程中的批处理机调度问题2 图1 2 论文的总体结构 l l 图2 1 聚类问题描述1 5 图2 2 具有不同利用率和负载均衡率的两个批 1 7 图2 3 两类浪费空间1 8 图2 4 计算空间浪费比的两种情2 0 图2 5 算法c a c b 的运行过程：2 3 图2 6g a 算法在不同参数下的平均收敛趋势2 4 图2 7c a c b 算法在不同参数下的平均性能 2 5 图2 8 问题( 1 b a t c h ，j ，s c l c 一) 的p l s l 类算例下算法性能趋势2 9 图2 9 问题( 1 i b a t c h ，s j - c l c 。) 的p 2 s l 类算例下算法性能趋势2 9 图2 1 0 问题( 1 b a t c h ，s ，s c i c 脓) 的p ls 2 类算例下算法性能趋 3 0 图2 1 i 问题( 1 i b a t c h ，s j c i c 脾) 的p 2 s 2 类算例下算法性能趋势3 0 图2 1 2 问题( 1 l b a t c h ，s ， - - c l ) 的p l s 3 类算例下算法性能趋势3 l 图2 1 3 问题( 1 l b a t c h ，s j c l c 恻) 的p 2 s 3 类算例下算法性能趋势3 l 图3 1 算法e r t - l p t 的运行过程4 1 图3 2 遗传算法的交叉操作4 2 图3 3 遗传算法的变异操作4 3 图3 4 遗传算法的总体流程 4 4 图4 1 基本蚁群算法的逻辑结构4 6 图4 2 蚁群算法中解的编码4 7 图4 3 启发式信息的构造4 8 图4 4 蚁群算法的总体流程5 0 图4 5 不同区分系数下g a 算法的收敛趋势5 3 图4 6 算法a c o 参数的选择5 4 图4 7 问题( 砌i b a t c h ，s ，墨c l c 麟) 的s l r l 类算例下算法性能对比5 5 图4 8问题( p r o i b a t c h ，5 j c l ) 的s 2 r l 类算例下算法性能对比5 5 图4 9 问题( p r o l b a t c h ，s ，s c l c 。) 的s 3 r l 类算例下算法性能对比5 6 图4 1 0 问题( p r o i b a t c h ，s ， - c l ) 的s i r 2 类算例下算法性能对比5 6 图4 1 l 问题( p r o b a t c h ，s ，c l ) 的s 2 r 2 类算例下算法性能对比5 7 图4 1 2 问题( p m b a t c h ，s j c i c 一) 的s 3 r 2 类算例下算法性能对比5 7 i x 插图目录 图5 1 图5 2 图5 3 图5 4 图5 5 图5 6 图5 7 图5 8 图5 9 图5 1 0 图5 1 1 图5 1 2 图5 1 3 图5 1 4 图5 1 5 2 0 0 8 年美国各部门的能源消费比重6 0 2 0 0 8 年美国工业部门的各种能源消费比重6 0 铝片制造过程中的批调度问题 6 1 分时电价的一个例子 6 1 算法l s 演示 6 6 倾斜度指标( s l o p ei n d e x ) 6 8 r i g h t s h i f t 过程7 0 n s g a i i 中新群体的构成 7 3 个体问的聚集距离 7 5 s p e a 2 适应度中尺( i ) 的计算7 7 s p e a 2 的存档修剪过程7 8 h y p e r v o l u m e 指标8 0 2 0 工件算例的非支配解集8 6 4 0 工件算例的非支配解集8 7 1 0 0 工件算例的非支配解集8 8 x 表格目录 表格目录 表2 1 算例生成的因素和等级2 3 表2 2 问题0 i b a t c h ，c l c 腽。) 1 0 工件算例下的测试结果2 6 表2 3 问题( 1 b a t c h ，s ，c l c 。) 2 0 工件算例下的测试结果o 0 一o dobi o 2 6 表2 4 问题( j i b a t c h ，j ，c 1 。) 5 0 工件算例下的测试结果2 6 表2 5 问题( 1 b a t c h ，j j 冬c l c 眦) 1 0 0 工件算例下的测试结果2 6 表2 6 问题( 1 i b a t c h ，j ，c i c 麟) 2 0 0 工件算例下的测试结果2 7 表2 7 问题( 1 l b a t c h ，s ，c l ) 3 0 0 工件算例下的测试结果2 7 表2 。8 问题( 1 b a t c h ，s ，c l c 胁) 5 0 0 工件算例下的测试结果2 7 表4 1 工件动态到达问题的算例生成参数及范围 5 l 表4 2 两个下界与最优解的接近程度 5 2 表4 3g a 和a c 0 的参数设置5 4 表5 1柔性流水车间批调度问题的算例设置7 9 表5 2p v a c s ，n s g a i i 和s p e a 2 的参数设置8 l 表5 3 算法找到的非支配解个数比较 8 2 表5 4 算法的覆盖率指标比较 8 3 表5 5 算法h y p e r v o l u m e 指标比较8 5 表5 6 算法运行时间指标比较8 5 x i 第1 章绪论 第1 章绪论 本章介绍论文的选题依据与研究内容。首先结合生产制造业的实际和发展 趋势论述了批处理机调度问题的研究意义；然后给出调度问题的基本描述和求 解方法，以及批处理机调度问题的国内外研究现状和发展趋势分析；最后阐述 本文的主要研究工作及内容组织安排。 1 1引言 生产调度，是在一定的时间内，对共享资源进行分配，对生产任务进行计 划排序的过程( r o d a m m e ra n dw h i t e ，1 9 8 8 ，f o x ，1 9 9 0 ) 。调度问题是先进生产制 造系统的关键问题之一。合理的调度方案可以大幅提高生产效益和资源利用率， 节省生产成本，从而增强企业的竞争力，推动生产制造业的发展。 尽管调度问题在制造业中具有举足轻重的地位，但很多生产中的调度问题 并没有得到很好的解决。这是因为现实中的调度问题通常是多约束、多目标、 具有随机性的不确定优化问题。其中很多已经被证明为是n p 难解问题( g a r e y e ta 1 ，1 9 7 6 ) ，很难寻找其最优解。 生产调度问题的研究，涉及数学、运筹学、计算机科学、工业工程等多个 学科，是交叉性很强的一个研究领域：从其研究目标来看，可以分为模型构建 和调度算法研究两方面。其中，对模型构建的研究主要是将现实中的生产调度 问题抽象为数学模型，涉及到条件约束、调度规则和目标函数等内容；而调度 算法研究则是根据现有的模型，设计出高效的算法求解调度问题，包括算法复 杂性、算法收敛性和优化质量等研究内容。 由于生产调度问题的重要性和广泛性，国内外的学者对该领域进行了深入 的研究，建立了各种环境下的调度模型，设计出了众多调度算法。但是，过去 的研究主要集中在经典调度问题上。这类经典问题的一个基本假设是工件的加 工具有排他性，即一台机器在同一时刻只能加工一个工件。然而，随着现代制 造业的发展，生产规模的扩大，各种新的调度问题不断涌现，对经典调度问题 的研究己经不能满足现代化生产的需要。 一类新出现的调度问题是批处理机( b a t c hp r o c e s s i n gm a c h i n e ，b p m ) 调 度问题( i k u r aa n dg i m p l e ，1 9 8 6 ，a h m a d ie ta 1 ，1 9 9 2 ，l e ee ta 1 ，1 9 9 2 ) 。不同与经 典调度问题，在批处理机调度模型中，一台机器在同一时刻可以加工多个工件。 由于批处理机调度不仅需要将工件指派到机器上，还包含将工件分批的决策问 1 第1 章绪论 题，因此又称为分批调度或简称批调度。 批处理机调度问题在现实生产环境中有着广泛的应用。一个典型的例子出 现在半导体芯片制造系统中( l e ee ta 1 ，1 9 9 2 ，u z s o y , 1 9 9 4 ) 。芯片制造过程中存 在一个老化工序，即将芯片暴露在高温之下，以检验出有潜在缺陷的芯片。高 温炉中一次可以放入多个芯片，而芯片的预烧时间根据：芷= 片类型预先确定。由 于预烧工序耗时较长，往往是其它工序加工时间的几倍，甚至几十倍，构成了 整个生产过程的瓶颈，因此提高其效率至关重要。如果将预烧芯片看作工件， 高温炉看作机器，则该问题就是一个典型的批处理机调度问题。 亩：劂激jo 7 审，辫 w a f e r ( j o b ) b u r n i nb o a r d ( b a t c h ) b u r n i no v e n ( m a c h i n e 图1 1 芯片制造过程中的批处理机调度问题 注：在半导体芯片的老化操作中，晶圆( w a f e r ) 需要放在加热板( b u m i nb o a r d ) 上 送入高温炉( b u r n i n o v e n ) 加工。若将晶圆看作工件( j o b ) ，加热板看作批( b a t c h ) ， 高温炉看作机器( m a c h i n e ) ，则这是一个典型的批处理机调度问题。 又如在多级船闸调度系统中，每天有成千上万的船舶需要通过船闸以继续 航行，每个船舶大小不一，而且船舶中所载货物的重要程度差异很大，如客轮 优先级最高、运输新鲜蔬菜水果的船舶优先级次之，而运输水泥、钢材等船舶 优先级最底。如果将每级闸室看作一个机器，过闸船舶看作工件，则该问题同 样是一种批处理机调度问题。此外，实际生产中这样的例子还有很多，如钢铁 生产、港口货物装卸、带托盘的车床加工、汽车货物运输等等。 由于批处理机调度包含工件的分批问题，它比经典调度问题更为复杂。此 外，批处理机调度问题在现实中广泛存在，解决这类问题对于提高生产效率， 增强企业的竞争力至关重要。因此，对于批处理机调度问题的研究，具有重要 2 第1 章绪论 的理论和实践意义。 1 2 调度问题的基本描述与求解方法 1 2 1 调度问题的基本描述 批处理机调度问题是调度理论的一个重要组成部分。在过去半个世纪以来， 调度领域已经有了相当多的理论研究，提出了大量数学模型和方法。对于调度 基本问题的了解有助于批处理机调度问题的深入研究，本节介绍调度问题的总 体框架，以及文中所用到的符号。 一个调度问题可以用三元组口i i ，来表示( p i n e d o ，2 0 0 2 ) 。其中，口字段描 述调度问题的机器环境；字段描述工件的加工特性和相关约束：，字段则表 示调度问题的目标函数。 口字段中的机器环境通常包括以下几类： ( 1 ) 单台机器( s i n g l em a c h i n e ) ，口字段记为1 。单台加工机器是所有机器 环境中最为简单的一种，是其他复杂机器环境的特例。 ( 2 ) 相同并行机( i d e n t i c a lp a r a l l e lm a c h i n e s ) ，记为砌。即有m 台完全相 同的机器。工件j 需要单一的操作，可以在m 台机器中的任何一台，或是某个 特定子集中的任何一台机器上加工，并且加工时间完全相同。 ( 3 ) 同类并行机( u n i f o r mp a r a l l e lm a c h i n e s ) ，记为跏。即有m 台并行， 但速度不同的机器。机器i 的速度记为啊若工件的加工量记为p ，则工件，在 机器i 上实际加工时间n = p ，叶。 ( 4 ) 无关联并行机( u n r e l a t e dp a r a l l e lm a c h i n e s ) ，记为r m 。这是同类并行 机环境的迸一步扩展，机器加工不同工件时具有不同的速度。假设机器i 加工工 件的速度记为，则工件，在机器i 上实际加工时间肋= p ，一i 。 ( 5 ) 流水车间( f l o ws h o p ) ，记为砌。有t ? l 台串行的机器，所有工件都需 要按照相同的路径( 即首先在第一台机器上加工，然后第二台，以此类推) 。 ( 6 ) 柔性流水车间( f l e x i b l ef l o ws h o p ) ，记为f f s 。柔性流水车间是并行 机环境和流水车间环境的结合。在该环境下，工件，需要依此通过s 个加工阶段， 每阶段有若干台并行机，工件，可以在其中任意一台机器上加工。 ( 7 ) 加工车间( i o bs h o p ) ，记为咖。有肌台机器，每个工件都有各自预 先确定的加工路径，工件需要按照该顺序在机器上加工。 ( 8 ) 柔性加工车间( f l e x i b l ei o bs h o p ) ，记为f j s 。柔性加工车间是并行机 环境和加工车间环境的结合。即有s 个加工阶段，每个工件按照预定的路径通 3 第1 章绪论 过这些加工阶段，每阶段中有若干台并行机可供选择。 ( 9 ) 开放车间( o p e ns h