文档介绍：上海交通大学
博士学位论文
动态不确定环境下生产调度算法研究
姓名:刘琳
申请学位级别:博士
专业:控制理论与控制工程
指导教师:席裕庚
20070701
动态不确定环境下生产调度算法研究摘要生产调度的目的是在有限时域内为生产任务分配有限的车间资源来优化一个或者多个性能指标。以往的关于调度的研究主要集中在理想的调度环境,一般都是以确定性的数学模型为基础,与实际的车间调度环境存在很大差别。在实际的制造车间中,往往存在着很多动态不确定因素,如加工时间变动、机器故障或者交货期变更等。如何在生成预调度时考虑到不确定因素的影响,已经成为解决实际问题的关键。不确定因素可以分为部分已知和完全未知两类,对于第一类情况,在建立预调度优化模型时,就应考虑这些因素的影响,可以有效提高调度的鲁棒性和稳定性:而对于第二类情况,采用反应式的重调度是适应环境变化的最好解决方式。在动态不确定环境下的调度问题,其计算复杂度远远超过了静态调度问题,使得以往的研究方法难以直接应用,对问题的求解提出了更高的要求。本文围绕着动态不确定环境下的调度问题展开研究,主要研究了三种典型的情况:加工时间不确定、机器随机故障和工件到达时间未知。本文的主要工作包括如下五个方面:紫妊芯苛思庸な奔洳蝗范ǖ牡セ鶭甀畉鞫任侍狻R蛭T诩庸な奔淙范ㄊ保不存在一个多项式时间算法得到问题的最优调度,所以采用了绝对鲁棒指标以最小化所有可能力时间下的最大代价,这是一个呕侍狻T诟ǖ鞫顺序后,内层呕侍獾木霾呖占涫羌庸な奔涔钩傻耐苟嗝嫣澹呕勘是关于加工时间的凸函数,则可以在凸多面体的顶点取得侍獾募担虼大大降低了问题的搜索空间。根据侍馓匦陨杓屏艘恢至讲阋糯惴ǎ与以期望时间为基础的确定性调度算法相比,在多种加工时间情况下设计的算法得到了更加鲁棒的调度。ǘ圆蝗范ḿ庸な奔淝榭鱿碌穆嘲舻鞫任侍獾难芯看拥セ┱沟絁于单机问题,中的约束更加复杂,增加了同一工件所有工序的先后顺序约束,因此不具有类似于单机内层侍獾奶匦裕渌阉骺占湮U黾庸な奔的可行域,大大增加了计算复杂度。相对于解决单机问题的两层算法,从兼顾算法性能和计算效率的角度出发,设计了一种双空间协同进化遗传算法,仿真测试表明了算法的有效性。芯苛嘶魉婊收锨榭鱿录婀宋榷ㄐ缘牡セ嘲舻鞫任侍猓梦侍馐且桓鏊。.相对上海交通大学博士学位论文
标优化问题。在调度执行之前,无法获得真实的性能指标,因此采用期望指标。通过将多次故障集结为一次故障,并采用右移重调度处理故障,简化了对调度的鲁棒性和稳定性指标的估算。采用权重和方法将双目标转化为单目标问题,设计了两阶段多种群遗传算法有效确定双目标优化问题的最优解。在仿真试验中,对四种不同方法进行了对比分析,同时比较了随机权重和固定权重情况下算法的性能,结果表明了随机权重比固定权重具有更好的搜索能力。ǖセ难芯砍晒┱沟交魉婊收锨榭鱿录婀宋榷ㄐ缘腏鲁棒调度问题。与单机问题求解算法的不同之处在于染色体的编码方式,不仅包含了表达工序优先关系的基因,还包含了计算插入空闲时间大小的基因。由于自身约束的复杂性,对调度的鲁棒性和稳定性指标计算更加困难,因此采用了采样方法进行估算。在仿真试验中,对未考虑空闲时间影响和考虑空闲时间影响的两种算法进行了对比分析,结果表明了后者比前者较大程度改善了稳定性,对鲁棒性的影响程度很小。怨ぜ酱锸奔湮粗5亩琂滚动重调度问题进行了深入研究,提出了关键工序集的概念。在滚动时域分解方法框架下,以时间窗口作为滚动窗口,设计了基于关键工序集的滚动重调度算法。采用混和遗传算法有效地确定关键工序集及其最优调度顺序,对关键工序集之外的工序,采用了分派规则确定在机器上的加工顺序,最后以完全调度的目标值评价染色体的适应度。与基于完全工序集的算法相比,大大降低了搜索空间。仿真试验表明,基于关键工序集的算法极大提高了计算效率,对全局性能指标的影响程度很小,为实际生产中的大规模动态调度问题提供了一种新思路。关键词:生产调度,不确定性,鲁棒性,稳定性,遗传算法,滚动时域分解摘要
甌甌.:瑆,,,,甋,
.甌甌.·瓵·.甌,甌瓵瑃ぁ甌瑃瑃:,,..甋,
日期:渤,暌自上海交通大学学位论文原创生声明本人郑重声明:所呈交的学位论文,是本人在导师的指导下,独立包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体,均已在文中以明确方式标明。本人完全意学位论文作者签名:进行研究工作所取得的成果。除文中已经注明引用的内容外,本论文不识到本声明的法律结果由本人承担。
指导教师签名:坪客《卢日期:暌自耭日期:岬年‘月保密口,在一年解密后适用本授权书。学位论文作者签名:朝挪:上海交通大学学位论文版权使用授权书本学位论文作者完全了解学校有关保