（控制理论与控制工程专业论文）随机机器故障下混合模式的单机鲁棒调度.pdf

山东大学硕士学位论文 摘要 在企业运营管理中合理规划生产的运作方式、节约生产成本，成为提高 企业竞争力的一个核心问题，而合理规划生产运作方式与节约生产成本的核 心是能够得到一个最佳的调度方案。生产调度问题是一类复杂的组合优化问 题，并且大部分问题已被证明是n p h a r d 问题，而考虑不确定性因素的生产 调度问题减少了调度理论与工业实际之间的差距，因此生产调度问题的研究 不仅具有深远的理论意义，而且还具有重大的现实意义。 单机调度问题是最基本的调度问题形式，其中，所有的任务只需要在一 台加工设备上加工一次。单机调度问题虽然只涉及一台机器，但大部分单机 问题却是n p h a r d 问题，并且对于单机问题理论上的深刻理解往往是处理更 复杂问题的第一步。由于实际生产环境的动态特性，使得不确定生产调度问 题变得更加复杂，而调度鲁棒性是不确定调度问题主要关注的优化目标。鲁 棒调度问题的研究已经是调度领域的研究热点，但是，目前针对鲁棒调度问 题的研究主要是基于单纯的主动模式或单纯的反应模式。关于混合模式的鲁 棒调度的研究还很少。因此本文提出了混合模式的鲁棒调度方法的一般框架， 并以单机调度问题为研究平台，深入研究了随机机器故障下混合模式的单机 鲁棒调度问题。为了验证混合模式的鲁棒调度方法的有效性，本文主要做了 如下两方面的工作： ( 1 ) 随机机器故障下混合模式的单机稳定调度。本文主要针对单机鲁棒 调度问题，设计了插入空闲时间的启发式1 0 s m t t 算法，具体地，针对m e h t a 与u z s o y ( 1 9 9 9 ) 提出的插入空闲时间的启发式算法o s m h ( o p t i m i z e d s u r r o g a t em e a s u r eh e u r i s t i c ) ，提出了一个修正形式的o s m h 算法，即m o s m h ( m o d i f i e do p t i m i z e ds u r r o g a t em e a s u r eh e u r i s t i c ) 。启发式m o s m h 算法的基本 思想就是充分利用初始调度本身可能存在的空闲时间。预测调度的稳定性是 通过工件的计划完成时间与实现完成时间之f n j 的加权绝对偏离和度量的。大 量的仿真实验结果表明，本文提出的启发式m o s m h 算法与o s m h 算法相比， 较好地改善了预测调度的稳定性，而且没有恶化调度的效率指标。由m o s m | i 山东大学硕士学位论文 算法得到的预测调度对各种故障场景具有更强的不敏感性。此结果充分说明 了本文提出的混合模式的鲁棒调度方法是有效的。 ( 2 ) 随机机器故障下混合模式的单机双目标鲁棒调度。此问题是在随机 机器故障环境下生成预测调度时同时考虑调度性能鲁棒( 简称为鲁棒性) 和 调度方案鲁棒( 简称为稳定性) ，此问题属于双目标优化问题，对这两个相互 冲突的目标进行折衷。设计了预测调度的鲁棒性替代度量和稳定性替代度量， 并将其嵌入到模拟退火算法中来获得预测调度。当预测调度执行过程中，假 设只有一个故障发生，故障发生后采用r i g h ts h i f t i n gr e s c h e d u l i n g ( r s r ) 方法进行重调度。为了测试鲁棒性替代度量和稳定性替代度量，进行了大量 的仿真实验。实验结果表明，用我们的方法得到的预测调度具有较好的调度 鲁棒性和稳定性，而且对于各种场景下的随机机器故障具有不敏感性。此研究 结果也充分说明了混合模式的鲁棒调度方法的有效性。 关键词：不确定性；鲁棒性；稳定性；预测调度：机器故障：单机调度；模 拟退火算法 2 山东大学硕士学位论文 _ 一_ _ 一 a b s t r a c t i nt h eo p e r a t i o n a lm a n a g e m e n t ，r a t i o n a lp l a n n i n ga n ds a v i n gp r o d u c t i o nc o s t s h a v eb e c o m eac o r ei s s u et oe n h a n c ee n t e r p r i s ec o m p e t i t i v e n e s s m o r e o v e r , t h ek e y t ot h e mi st oo b t a i na l lo p t i m a ls c h e d u l i n gs c h e m e p r o d u c t i o ns c h e d u l i n gp r o b l e m i sac l a s so fc o m p l e xc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s ，w h e r em o s to ft h e m h a v eb e e np r o v e dt ob en p h a r d 。a n di n c o r p o r a t i n gt h eu n c e r t a i n t i e se x s l t m g i nt h e e x e c u t i o ne n v i r o n m e n to fs c h e d u l i n gp r o b l e m sm a yd e c r e a s et h eg a pb e t w e e n s c h e d u l i n gt h e o r ya n di n d u s t r i a lp r a c t i c e t h e r e f o r e ，t h ee f f o r t sc o n c e n t r a t i n go n p r o d u c t i o ns c h e d u l i n gh a v en o to n l ys i g n i f i c a n ta c a d e m i cv a l u eb u ta l s og r e a t p r a c t i c a lm e a n i n g s i n g l em a c h i n es c h e d u l i n gp r o b l e mi s t h em o s tb a s i cf o r mo fs c h e d u l i n g p r o b l e m ，w h e r eas e to fi o b s i st ob es c h e d u l e do i las i n g l em a c h i n e h o w e v e r , s i n g l em a c h i n em o d e l sa r ei m p o r t a n tf o rv a r i o u sr e a s o n s n es i n g l em a c h i n e e n v i r o n m e n ti sv e r ys i m p l ea n das p e c i a lc a s eo fa l lo t h e re n v i r o n m e n t s s i n g l e m a c h i n em o d e l so f t e nh a v ep r o p e r t i e st h a tn e i t h e rm a c h i n e si np a r a l l e l n o r m a c h i n e si ns e r i e sh a v e t h er e s u l t st h a tc a nb eo b t a i n e df o rs i n g l em a c h i n em o d e l s n o to n l yp r o v i d ei n s i g h t si n t ot h es i n g l em a c h i n ee n v i r o n m e n t ，b u ta l s op r o v i d ea b a s i sf o rh e u r i s t i c st h a ta r ea p p l i c a b l et om o r ec o m p l i c a t e dm a c h i n ee n v i r o n m e n t s i nf a c t ，s c h e d u l i n gp r o b l e m si nm o r ec o m p l i c a t e dm a c h i n ee n v i r o n m e n t sa r eo f t e n d e c o m p o s e di n t os u b p r o b l e m st h a td e a lw i t hs i n g l em a c h i n e t h en a t u r eo fd y n a m i cc h a r a c t e r i s t i e si nr e a d l i f em a n u f a c t u r i n ge n v i r o n m e n t s m a k e st h es c h e d u l i n gp r o b l e m su n d e ru n c e r t a i n t i e s ( a l s ok n o w na sd y n a m i c s c h e d u l i n g ) m o r ec o m p l e x s c h e d u l er o b u s t n e s si st h em a j o r m e a s u r ec o n c e r n e db y d y n a m i cs c h e d u l i n g h e n c e , r o b u s ts c h e d u l i n gp r o b l e m sh a v eb e e nt h er e s e a r c h f o c u so ft h es c h e d u l i n gf i e l d h o w e v e r , t h er e s e a r c he f f o r t si nt h er o b u s ts c h e d u l i n g p r o b l e m sa t em a i n l yb a s e do ne i t h e rp r o a c t i v es c h e d u l i n g0 1 r e a c t i v es c h e d u l i n g ， a n dt h el i t e r a t u r eo nh y b r i dr o b u s ts c h e d u l i n gi sr a t h e rs p a r s e t h e r e f o r e , t h i sp a p e r p r o p o s e dt h eg e n e r a lf r a m e w o r ko fh y b r i dr o b u s ts c h e d u l i n g , a n dh y b r i dr o b u s t s c h e d u l i n gm e t h o d su n d e rr a n d o mb r e a k d o w nw a si n v e s t i g a t e d i nd e t a i lw i t h s i n g l e m a c h i n em o d e lo fs c h e d u l i n g a sr e s e a r c h p l a t f o r m t o e x a mt h e e f f e c t i v e n e s so f h y b r i dr o b u s ts c h e d u l i n gm e t h o d s ，t h em a i ne f f o r t sa r e a sf o l l o w s ah y b r i dr o b u s ts c h e d u l i n gw i t hs t a b i l i t ya sc r i t e r i o nf o rs i n g l em a c h i n ew i t h r a n d o mb r e a k d o w ni sd e a l tw i t h t h es i n g l em a c h i n es c h e d u l i n gp r o b l e m i ss u b j e c t t or a n d o mm a c h i n eb r e a k d o w n ，w h e r ej o b sa r r i v e a ts y s t e md y n a m i c a l l y a m o d i f i e dv e r s i o no fo p t i m i z e ds u r r o g a t em e a s u r eh e u r i s t i c ( o s m h ) d e v e l o p e d b ym e h t aa n du z s o y ( 1 9 9 9 】i sp r o p o s e d ，i e ，m o d i f i e do p t i m i z e ds u r r o g a t e 3 山东大学硕士学位论文 m e a s u r eh e u r i s t i c ( m o s m h ) t h ei d e ab e h i n dt h eh e u r i s t i cm o s m hi st om a k e f u l lu s eo ft h ei d l et i m e sp r o b a b l ye x i s t i n gi ni n i t i a ls c h e d u l e n es t a b i l i t yo ft h e p r e d i c t i v es c h e d u l ei sm e a s u r e db yt h es u mo ft h ew e i g h t e da b s o l u t ed e v i a t i o n b e t w e e nt h ep l a n n e di o bc o m p l e t i o nt i m e sa n dt h er e a l i z e do n e e x t e n s i v e c o m p u t a t i o n a lr e s u l t ss h o wt h a tt h eh e u r i s t i cm o s m hp r o p o s e di n t h i sp a p e r s i g n i f i c a n t l yi m p r o v e st h es c h e d u l es t a b i l i t yw i t h o u td e t e r i o r a t i n gt h ee f f i c i e n c y p e r f o r m a n c ea n dt h ep r e d i c t i v es c h e d u l eo b t a i n e db ym o s m h i sm o r ei n s e n s i t i v e t ot h ev a r i o u sb r e a k d o w ns c e n a r i o st h a nt h eh e u r i s t i co s m h ，w h i c hf u l l y d e m o n s t r a t e st h ee f f e c t i v e n e s so ft h eh y b r i dr o b u s ts c h e d u l i n g ，p r o p o s e di n t h i s p a p e r , f o rs i n g l em a c h i n ew i t hr a n d o mb r e a k d o w n ah y b r i dr o b u s ts c h e d u l i n gw i t hb i o b j e c t i v ea sc r i t e r i o nf o rs i n g l em a c h i n e s u b j e c tt or a n d o mb r e a k d o w ni s c o n s i d e r e d t h er e s e a r c he f f o r ti st of i n d p r e d i c t i v es c h e d u l ew i t hp e r f o r m a n c er o b u s t n e s s ( r e f e r r e dt oa sr o b u s t n e s s ) a n d s u l o t i o nr o b u s t n e s s ( k n o w na ss t a b i l i t y ) f o ras i n g l em a c h i n es u b j e c tt or a n d o m m a c h i n eb r e a k d o w n ，w h e r ej o b s a r r i v e d y n a m i c a l l ya n dt h e t o t a lw e i 曲t e d t a r d i n e s si st h ep e r f o r m a n c et ob eo p t i m i z e d 1 1 1 ep r o b l e mi sab i - o b j e c t i v e o p t i m i z a t i o n t og e n e r a t et h ep r e d i c t i v es c h e d u l e ，t h eo b u s t n e s sa n ds t a b i l i t ya r e c o n s i d e r e ds i m u l t a n e o u s l y t w os u r r o g a t em e a s u r e sf o rr o b u s t n e s sa n ds t a b i l i t ya r e d e v e l o p e da n de m b e d d e di n as i m u l a t e da n n e a li n ga l g o r i t h mt oo b t a i nt h e p r e d i c t i v es c h e d u l e t h e nt h ep r e d i c t i v es c h e d u l ei sr e l e a s e di n t os h o pf l o o rt ob e e x e c u t e d o no c c u l r e n c eo fam a c h i n eb r e a k d o w n ，t h er i g h ts h i t t i n gr e s c h e d u l i n g ( r s r ) i su s e dt oa c c o m m o d a t et h eb r e a k d o w n t h et e s tp r o b l e m sa r ec a m e d o u tt o e x a mt h es u r r o g a t em e a s u r e s t h ee x t e n s i v ec o m p u t a t i o n a lr e s u l t ss h o wt h a tt h e s c h e d u l eg e n e r a t e db yo u rm e t h o dc a np r o v i d eb e t t e rr o b u s t n e s sa n ds t a b i l i t ya n di t i sm o r ei n s e n s i t i v et ot h ev a r i o u sb r e a k d o w ns c e n a r i o s ，w h i c hs h o w sag o o d e f f e c i t i v e n e s so ft h eh y b r i dr o b u s ts c h e d u l i n g ，p r e s e n t e di n t h i sp a p e r , f o rs i n g l e m a c h i n ew i t hr a n d o mb r e a k d o w n k e y w o r d s ：u n c e r t a i n t y ；r o b u s t n e s s ；s t a b i l i t y ；p r e d i c t i v es c h e d u l e ；m a c h i n e b r e a k d o w n ；s i n g l em a c h i n es c h e d u l i n g ；s i m u l a t e da n n e a l i n g 4 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体己经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均己在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：重丝乏 日 期：上归 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阕；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名夕纽三导师签名：j 赴日期：垂塑：p 山东大学硕士学位论文 1 1 引言 第1 章绪论 随着调度问题研究先驱t | e n r y ( ；a n t t 的研究成果的出现，调度问题开始得 到了重视【l l 。二战后，各类大型企业逐渐兴起，。规模庞大，结构复杂，计算稍 有不周即可造成重大损失，依靠拍脑袋已不能解决问题。此时各种新的组合 优化问题便涌现出来，调度问题便是其中之一。美国国防部与数学科学研 究的报告中指出：在2 0 世纪9 0 年代至2 l 世纪，数学发展的重点将从连续的 对象转向离散的对象，并且组合最优化将有很大的发展f z j 。1 9 5 4 年，j a c k s o n f l o ws h o p i 周度问题f 2 1 l 气。提出了一个简便但十分巧妙的算法，求得最优 解p i 。自此，调度问题在国际上得到迅猛发展，调度领域成为研究最活跃、成 果最丰硕、前景最诱人的科学领域之一，至今仍吸引着大批的研究工作者， 并产生了大量的研究文献i o j 。 金融危机的全球性爆发，使得各行各业都受到了严重的影响，而对制造 业的影响尤为严重。制造业的目标仍然是盈利、赚钱，这一目标的实现需要 三个衡量指标即有效产出、存货和运营费用来衡量，其中有效产出必须由高 效的生产管理来保障l 。在当今尤为恶劣的经济环境下，企业之间的竞争日 益加剧。由于客户的需求日益多样化，产品寿命周期缩短，使得企业的生产 必须按照品种多、批量小的模式进行。实际上，生产过程又面临着诸多的不 确定性【1 2 。6 1 ，比如随机的机器故障、加急订单、材料短缺、人员变动、本企 业与其他公司进行竞标的随机性等等；同时，企业为了盈利的目标又必须降 低成本，并导致对零库存系统的需求，然而，企业为了保持市场份额就必须 对变化多端的市场进行快速反应，这就意味着要求更多的库存来保证。有效 的生产调度已经成为先进制造业管理中的核心与关键。因而生产调度问题的 研究不仅具有深远的理论意义，而且还具有重大的现实意义。 本章首先概述生产调度问题并描述生产调度问题中存在的不确定性及其 处理方法，然后综述单机鲁棒调度问题研究现状及存在的问题并引出本文将 要研究的内容，最后给出全文的内容安排。 山东大学硕士学位论文 1 2 生产调度问题概述 生产调度问题概述 调度在制造业的管理、服务业的管理与信息处理环境中扮演着重要的角 色，应用领域非常广泛，比如制造业的生产调度( p r o d u c t i o ns c h e d u l i n g ) 、 物流管理中的供应链调度( s u p p l yc h a ins c h e d u l in g ) 、项目管理中的项目 调度( p r o j e c ts c h e d u l i n g ) 、运输业中的车辆调度问题( v e h i c l er o u t i n g s c h e d u l i n g ) 等等，除了生产调度领域产生的大量文献外，其它领域也产生 了大量的研究成果【1 7 2 2 1 。 生产调度问题是在一定的时问内，进行可用共享资源的分配和生产任务 的排序，以满足某些指定的性能指标1 2 ”。一般地，生产调度可描述为：针对 某项可以分解的工作，在一定的约束条件下，安排其组成部分( 操作) 所占 用的资源、加工时间及先后顺序，以获得产品制造时间或者成本等最优【2 4 1 。 生产调度问题是一类组合优化问题，通常是多约束、多目标、随机不确 定优化问题。大部分生产调度问题己被证明是n p h a r d f 目题【2 5 1 ，其特点主要表 现为建模复杂性和计算复杂性、系统动态性与不确定性、多约束性和多目标 性f 2 4 2 6 。2 7 。 生产调度问题的分类方法有很多。按照生产过程中的机器环境可分为单 机和多机调度问题。多机调度问题包括f l o ws h o p 、j o bs h o p 和并行机调度问 题。 单机调度问题的重妻意义 单机调度问题非常重要。首先，单机环境是许多工业和资源环境中的一 种特例，单机调度问题虽然只涉及一台机器，但大部分单机问题却是n p h a r d 问题，比如问题模型为li i q 、li - i k 、lioi 弓和ii l 哆t 等的单 机调度问题都已被证明是强n p h a r d f t i 题；其次，单机模型通常具有并行机 或者串行机所没有的性质，因而从单机模型中得到的结果不仅能对单机环境 提供深刻的透视，也能为适用于更复杂机器环境的启发式算法提供一个基础； 另外，对于单机问题理论上的深刻理解往往是处理更复杂问题的第一步，比 如在现实世界中具有瓶颈机的复杂机器环境下的调度问题经常会被分解成处 理单机问题的许多子问题。a d a m 等人【8 i 提出的分解方法一移动瓶颈方法 2 山东大学硕士学位论文 s b p ( s h i i t i n gb o t t l e n e c kp r o c e d u r e ) 是求解j o bs h o p 调度问题最成功的启发式算 法之一。文u o 提出了基于s b p 的r t t p ( r o l l i n gh o r i z o np r o c e d u r e ) 方法通过将大 规模j o b - s h o p 调度问题分解成一系列单机子问题而成功地求解了大规模复杂 调度问题。 本文研究的单机调度问题考虑了生产环境中的不确定性因素，使得调度 问题更加接近于工业实际，因此本文的研究不仅具有重大的理论价值和现实 意义，而且还对更复杂的多机调度问题提供研究基础并推动更复杂调度问题 的研究。 1 3 生产调度中的不确定性及其处理方法 虽然生产调度领域已经涌现出了大量的研究成果，但有相当一部分是确定 性调度问题【7 2 5 - 2 9 1 。确定性调度问题假设所有的问题参数都是已知并且是确 定的，这种假设是对实际生产环境的一种理想化。然而，实际的生产环境具 有复杂多变的动态特性，存在着各种各样的不确定因素，比如来自企业内部 的机器故障、操作人员的技术水平、人员变动、加工时间的不确定性等，还 有来自企业外部环境的不确定性，比如原材料的价格浮动、物料供应变动、 市场环境的变化、加急订单的到达、交货期的改变和工件的取消等等。不确 定性与扰动早在二十世纪初就已经是研究的课题，自从系统化制造开始至今， 仍然是一个开放性的问题。最近十几年来，人们发现这种对制造环境理想化 的假设行不通了，因而努力拓展确定性的研究方法去求解不确定的调度问题 u 2 1 。目前，不确定的调度问题己经成为国际国内的研究热a t l 3 - 1 6 , 3 0 - 3 1 1 。 不确定因素给生产调度带来的直接后果就是由确定性环境得到的调度方 案的性能可能会受到影响，甚至使得调度方案根本不再可行。对于决策者来 说，如何处理生产调度过程中的不确定因素，成为必须要考虑的问题。因此， 我们有必要对调度过程中的不确定性进行深刻的理解，有助于将来的问题研 究。下面从调度问题中的不确定性、对不确定性的建模方法和处理不确定性 的鲁棒调度方法三个方面来叙述生产调度中的不确定性。 调度问题中的不确定性 文 3 2 将不确定性( u n c e r t a i n t y ) 定义为对一个过程或者参数缺乏准确的知 识或预测。对于生产调度中的不确定性因素，文 1 2 从以下三个方面来理解 山东大学硕士学位论文 和描述不确定性：( i ) c a u s e ；( 2 ) c o n t e x t ；( 3 ) i m p a c t 。c a u s e r 从分析引起不确 定性的原因的角度来认识不确定性的，c a u s e 可看做是物体及其状态，比如材 料是否准备好、资源与夹具是否可用或者运行状态是否良好未被损坏、人员 健康与否等；c o n t e x t 指的是调度时刻的环境条件，可分为两种情形，即与环 境无关( c o n t e x t f r e e ) 和对环境敏感( c o n t e x t s e n s i t i v e ) ，当我们对生产环境建模 时，与环境无关的情形不需要附加的信息或做出特殊的决策，而对环境敏感 的情形则需要获取环境条件的有关信息；i m p a c t 指的是由不确定性带来的后 果，即不确定性带来时间上的影响、对其它工件或活动带来的影响等。以上 三个方面能够捕捉现实世界调度问题的重要因素。 不确定性的形式 不确定性可以有多种形式。文【3 3 】将不确定性的形式分为两大类，即与资 源相关的不确定性和与工件相关的不确定性。与资源相关的不确定性形式主 要有机器故障、操作人员生病、夹具不可用、负载限制、材料短缺或材料到 达时问延迟以及材料存在缺陷等。与工件相关的不确定性形式主要有加急工 件的到达、工件的取消、交货期的改变、工件提前或拖期到达、工件优先权 的改变以及工件加工时间的改变等。 不确定信息的分类 不确定因素的种类很多，总体上来看主要是客观存在的不确定性因素和 主观判断引起的不确定性矧。由于客观存在的不确定性不以人的意志为转移， 我们对于此种不确定性所能够做的工作甚少。主观判断引起的不确定性是指 在建模的过程中，人们要对客观现象进行描述，作出判断，不可避免地要掺 杂主观因素。但有很多主观的不确定性因素的来源是由于所得到的信息不够 完整所致。而对于主观判断引起的不确定性，我们可以采取正确的措施尽量 地减少不确定性的程度。文 3 4 】把不确定性因素的起因概括为：信息的缺乏 ( l a c ko f i n f o r m a t i o n ) 、信息复杂性( a b u n d a n c eo f i n f o r m a t i o n ( c o m p l e x i t y ) ) 、证 据彼此冲突( c o n f l i c t i n ge v i d e n c e ) 、语言描述的模糊性( a m b i g u i t y ) 、工程测量 误差( m e a s u r e m e n t ) 和信息的可信度( b e l i e f ) 。 不确定因素的分类 文1 1 3 1 和文 3 5 1 从两个不同的角度对不确定性因素进行了分类。文【1 3 】基 于不确定性来源的特性，将不确定性可分为四种类型：模型( 系统) 固有的 4 山东大学硕士学位论文 不确定性( m o d e l i n h e r e n tu n c e r t a i n t y ) ，生产过程固有的不确定性 ( p r o c e s s i n h e r e n tu n c e r t a i n t y ) ，来自外部环境的不确定性( e x t e r n a lu n c e r t a i n t y ) 和离散的不确定性( d i s c r e t eu n c e r t a i n t y ) 。文1 3 5 1 基于可预测性，将不确定性分 为：完全不可知( c o m p l e t eu n k n o w n s ) 、对未来的猜测( s u s p i c i o n sa b o u tt h ef u t u r e ) 和己知的不确定性( k n o w nu n c e r t a i n t i e s ) 。完全未知的不确定，是指完全不可预 测的事情。对于这种不确定性，在生成预测调度时，很难将其考虑进去，当 这种不确定性发生时，只能对其进行反应处理，别无它法。对未来的猜测源 自于调度人员的直觉和经验。由于人们的直觉和经验很难进行量化，因而也 难于将其融于算法中。己知的不确定性，是指那些可以获得有关信息的不确 定性。本文将已知的不确定性称为可预测不确定性，将完全不可知和对未来 的猜测称为不可预测的不确定性。 不确定性的建模方法 对不确定性建模的方法主要有基于概率论( p r o b a b i l i t yt h e o r y ) 的随机分析 法【3 6 。8 1 ，基于可能性理论【3 l ，3 9 4 1 1 ( q u a l i t a t i v ep o s s i b i l i t yt h e o r y ) 的模糊分析法， 离散值法【1 3 ，1 6 1 ( d i s c r e t ev a l u e s ) 和场景计划法【4 u ( s c e n a r i op l a n n i n ga p p r o a c h ) 等。 随机分析法是用某种概率分布来刻画不确定性，概率分布可以通过研究 生产车间的历史数据来获得。m e h t a g l u z s o y l 3 7 - 3 8 1 分别研究了服从指数分布的 随机机器故障下j o bs h o p 和单机调度问题，其目标函数是极小化最大 l a t e n e s s ( k ) ，提出t p r e d i c t a b l es c h e d u l i n g ( p s 方法，此方法就是在预测调 度中插入空闲时问来减少扰动对调度的影响，仿真结果表明p s 方法在可预测 性能上( p r e d i c t a b i l i t y ) 有很大的改善，而k 。的牺牲较小。0 d o n o v a n 等a 3 6 l 也致力于研究生成稳定调度，采用的方法类似，而他们的性能度量指标是总 拖期时间。 基于可能性理论【3 9 j 的模糊分析法是用模糊数( f u z z yn u m b e r ) 及模糊隶属 度函数( f u z z ym e m b e rf u n c t i o n ) 来描述不确定性。近年来，越来越多的研究者关 注于模糊调度的研究( 3 i 4 叫。文【3 l 】提出了基于模糊集理论( f u z z ys e tt h e o r y ) 的鲁棒调度方法用于不确定的产品开发项目。文献 4 0 1 研究了不确定环境下的 资源约束项目调度问题，提出了模糊关键链的方法。文f 4 l 】研究了具有不确定 加工时问的鲁棒f l o ws h o p 调度问题采用三角模糊数来表示不确定的加工时 5 山东大学硕士学位论文 间和完成时问，提出了模糊m a k e s p a n 的鲁棒性度量，并采用离散的微粒群算 法( d i s c r e t ep a r t i c l es w a r mo p t i m i z a t i o n ) 求解此问题。 离散值法用离散的随机分布函数来刻画不确定的随机离散事件( 1 3 l ，比如 操作人员的误操作，在实际处理此类不确定性时往往采用动态反馈策略，一 旦不确定性发生，及时进行检测，对调度模型重新进行优化，以确保整个调 度方案的最优性1 1 6 1 。 场景计划法是采用离散的场景来描述不确定性的各种情形，这些不确定 性的各种场景是基于决策者的知识与经验的，描述了生产环境中不确定性因 素与相应的决策模型的输入数据之间的关系。文 4 2 4 3 基于场景计划法研究 了单机鲁棒调度问题，文 4 4 1 基于场景计划法建立了鲁棒离散优化的基础理 论。 一 对机器故障的建模 在确定性环境下，生产过程一般按照确定性的初始调度进行，但是在实 际初始调度的执行过程中会不可避免地发生机器故障或扰动。机器故障或扰 动的发生频率和持续时间都具有随机性，对其预测和描述可以基于对生产过 程历史数据的统计规律。另外，对于关键操作人员生病、夹具不可用、负载 限制、加急订单、过多的加工时间、材料短缺或材料到达时间延迟等扰动也 可将其看作机器故障。 现有文献对于机器故障的处理方法主要有：基于概率论的随机分析法和 简单模拟的方法。文 3 6 3 8 ，4 5 4 7 】采用随机分析法对机器故障进行建模，其中 文 3 6 3 8 ，4 6 睬用指数分布来描述机器故障发生间隔，采用一致分布产生故障 持续时间或故障修复时间；而 4 5 ，4 7 则采用g a m m a 分布来对机器故障建模。 文 4 8 - - 4 9 贝j j 采用简单模拟的方法来描述机器故障。具体地，文 4 8 】随机产生一 个干扰位置，即单机环境下随机选择某个工件遭遇机器故障，并假设故障持 续时间已知；文【4 9 】采用一致分布来随机选择初始调度中的一个操作，那么加 工此操作的机器就被认为发生了故障，故障的开始时间设为此操作的开始加 工时间，故障结束时间等于故障开始时间加上故障持续时间( 故障持续时间 设为定常时问) 。 处理不确定性的鲁棒调度方法 不确定生产环境下，实际的实现调度未必就是初始调度。由于不确定事 6 山东大学硕士学位论文 件的发生，实现调度相对初始调度会产生较大的偏离，从而引起额外的费用， 因此调度鲁捧性成为研究不确定调度问题所关注的主要优化目标。 调度鲁棒性是一个难以定义、难以度量的一个概念l ij 。文献中对调度鲁棒 性概念的定义既有定性的也有定量的，至今没有统一的被广泛认可的定义， 但是对调度鲁棒性概念的定义都反映了调度方案在遭遇扰动时所具有的对不 确定性因素的不敏感性的实质。g r a v e s ! l o 】在二十世纪八十年代将调度鲁棒性 ( s c h e d u l er o b u s t n e s s ) 的概念引入到了生产调度中，并认为调度鲁棒性是指调 度方法明确地反映所获得信息所具有的不确定性的本质，或者调度方法能够 提供某种保证，确保调度对未来信息具有不敏感性。笼统地说，调度的鲁棒 性( s c h e d u l er o b u s t n e s s ) 是指调度方案遭遇不确定因素时的抗干扰能力。决策 者总是希望调度方案的某些性能在实际执行中遭遇不确定因素后仍能保持优 良，同时希望实际执行的调度方案与原始调度方案的偏离最小，从而降低制 造环境中的不确定因素带来的影响。调度的鲁棒性度量主要有性能鲁棒 ( p e r f o r m a n c er o b u s t n e s s ) 和方案鲁棒( s o l u t i o nr o b u s t n e s s ) 两种。所谓性能鲁棒 是指调度的某个或某些性能在不确定环境中具有抗扰动性，而方案鲁棒是指 调度方案本身在扰动发生后相对初始调度的偏离尽可能小。性能鲁棒和方案 鲁棒是从两个不同的角度去度量鲁棒性，实际上二者是密不可分的，因为调 度方案偏离很可能带来性能的改变，而性能的偏离肯定伴随着调度方案的偏 离。为叙述简便，并且不会引起概念混淆时，在本文的后续部分将调度的性 能鲁棒简称为鲁棒性，将调度的方案鲁棒简称为稳定性。 鲁棒调度方法的目的在于当调度执行过程中发生扰动时，根据决策者的 偏好，或者获得调度鲁棒性或调度稳定性，或者获得二者的折中。目前对于 调度鲁棒性的实现方法有主动模式( p r o a c t i v es c h e d u l i n g ) 1 3 6 3 8 4 2 4 3 1 、反应模式 ( r e a c t i v es c h e d u l i n g ) | 4 7 , 5 0 - 5 6 1 和混合模式( h ) ，b r i ds c h e d u l i n g ) t 4 8 ，s 7 1 。 基于主动模式的鲁棒调度是对鲁棒性主动优化的一种模式，具体地来说 就是在生成初始调度时主动考虑未来潜在的不确定因素，定义鲁棒性度量并 将其作为优化目标。一般地，鲁棒性度量可以是单独的鲁棒性度量或单独的 稳定性度量，也可以是二者兼有。本文研究的混合模式鲁棒调度的第一步就 是主动地考虑不确定性。本文第二章在生成预测调度时主动地考虑了调度的 稳定性，而第三章则同时考虑了鲁棒性度量和稳定性度量。 山东大学硕士学位论文