模糊环境下的非确定性调度问题的研究

《模糊环境下的非确定性调度问题的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、l‘‘1●RESEARCHONNONDETERMINISTICSCHEDULINGPROBLEMSINFUZZYENVIRONMENTSThesisSubmittedtoShanghaiJiaoTongUniversityinpartialfulfillmentoftherequirementforthedegreeofDoctorXieYuan(Automation)ThesisSupervisor：Prof．XieJian—yingJune，2006，一<声▲上海交通大学学位论文原创性声明本

2、人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本态，；文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。l◆本人完全意识到本声明的法律结果由本人承担。寺加名7戤吖税僻作q文y一洲上海交通大学学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权上海交通

3、大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。，、保密日，在生年解密后适用本授权书。本学位论文属于7不保密口。(请在以上方框内打“√")学位论文作者主名：谢源指导教师签日期：沙口{7年]月6El吼训7月芗i，巨“也’=。—-，‘L．—一S警r妙＼型姜著弋×妥弋爿}。卜、)、芒而)j捌、。I炽￥≮-≤廷树[：二苍、r州≈泠、p酞P分N矗l：j《≮剥泔、一、—．一弋‘c、々蝌。二．≤主三●螫吣＼芒+慕一蕊‘、尽≮，碰‘1。J二溶、

4、=，藤●提涮区!订垡颦鲻辎杈斟辎整’●一惫浆_蚤鞯帮藤禄舔释藤副夸延j、-·==’星搞讨芒J翅圈二<==’’=嗣蝥纠薯毒二醚二2二二二jj。搭、一裂～巷二掮●*七“星*爿-L一’：基(，●≮令蚕兰】磐才-乎牦汁精—^瞄二<磐二<基。薯_二<二嗣冒曩鲁杈铡烈jg二：≮囊哥鲁。童·暑囊譬‘}，··，昭二二鼍鼍三j目罚姿_——-一裂二鲁●一、o冀●●。一‘～J一卜恩V岣o：蚤oN锥=量一苍J／譬鄹正N翻数专≮寸嗣裂登议漤彀1-量’楚志#，妥：÷雁V-i粒韵<：lj芒导暴j牛冠<三：’2●袋=三≈蓉昱墨

5、●宰答卷蓑靶仪袋．逍外孙K冒粼建二厂模糊环境下的非确定性调度问题的研究摘要在实际调度中，许多参数在调度之前不是精确已知的，这些参数的不完全性和不确定性往往不符合统计的规律，模糊调度研究就是运用模糊集理论表示这类不精确参数，并求解对应的不确定性调度问题。论文研究了单机、并行机和车间调度这三类主要的模糊调度问题的建模过程和求解方法，给出了模糊调度研究的一般框架。模糊调度采用模糊数描述问题中的不精确参数，通过模糊数的运算来表示调度问题的模糊约束和模糊目标函数。模糊调度问题既要优化确定性调度问题中已有的

6、性能指标，还需要处理模糊调度特有的模糊性能指标，因此论文分析的几种具体的模糊调度问题具有多个目标函数。为了同时最优化多个目标函数，引入Pareto最优的概念描述问题的最优调度，借鉴非支配调度的方法在多个目标函数之间寻找平衡，得到模糊调度问题的最优解。根据模糊参数和目标函数的不同，采用适合模糊环境的启发式规则算法求解简单的模糊调度问题，复杂的问题则采用针对具体问题的遗传算法或者神经网络等人工智能的方法来求解。论文的主要研究成果和创新如下：1．提出了一种带模糊任务交货期和模糊任务优先关系的单机调度问

7、题，问题的目标函数是任务完成时间关于模糊交货期的满意程度和模糊优先约束的满意程度。采用非支配调度的概念来描述该双目标函数问题的最优解，提出通过寻找非支配向量的方法来求解问题。在上述问题的研究基础上，进一步指出当问题还具有确定性优先约束时，也可以采用非支配调度的方法来求解带混合优先约束和模糊交货期的单机调度问题o．．tL2．分析了一种带模糊处理时间的单机模糊时间延迟调度问题，提出采用L—R模糊数来表示任务的时间延迟和模糊处理时间，改进了已知的Lawler算法，能够在多项式时间内求解该模糊时间延迟调

8、度问题，但是该问题对应的确定性问题却是NP难题。通过该问题的求解，指出某些情况下把问题模糊化可以达到降低问题的复杂性的效果。上海交通大学博士学位论文3．研究了一种目标函数为最大模糊拖延时间的期望值的单机调度问题，针对该模糊问题的NP完全特性，提出采用标准遗传算法寻找问题的最优解。4．对于并行机调度问题，提出了一种任务的交货期是模糊数的调度问题，调度的目标是最优化任务的最大完成时间和模糊交货期的最小满意程度。该问题无法在多项式时间内求解，因此论文分别采用NichedPareto遗传算法(NPGA)