基于元启发式的分布式车间调度方法研究

来源 :南京航空航天大学 | 被引量 : 9次 | 上传用户:hanbing5
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
随着现今市场和制造全球化趋势,为应对瞬息万变的市场需求,生产车间已经由单一车间向多车间转变,从集中式结构变为分散式结构,形成了分布式车间生产模式。车间调度在分布式车间生产中至关重要,有效的调度算法和优化技术能够优化生产系统流程,提高生产效率和经济效益。分布式车间调度问题相对单车间调度问题更加复杂,尤其是调度方法的研究,已经引起了学术界和工业界的广泛关注。许多分布式车间调度问题是NP(non-deterministic polynomial)难问题,传统的调度方法如分支定界法、数学规划方法、启发式规则,都很难获取问题的最优解或者计算量太大。元启发式算法(meta-heuristics)不依赖求解问题,通过全局和局部搜索能够获得较为满意的解,是求解调度问题的有效方法,其研究成果具有重要的学术意义和应用价值。本文深入研究了制造系统中广泛存在的零等待、零空闲、交货期等加工约束,提出了基于改进的教学优化算法以及Memetic算法的调度方法。并将相关成果扩展到分布式调度车间调度中,对分布式零等待流水车间调度以及带有装配过程的分布式零空闲流水车间调度问题进行了求解。主要研究工作如下:(1)针对教学优化算法存在的不足,从概率理论的角度出发,提出了基于概率分布模型的协同学习机制,将概率模型嵌入教授或者学习阶段,即将概率分布作为老师或者信息交流平台。针对零等待流水车间调度问题,提出了一种基于概率学习阶段的离散教学优化算法(HDTPL)。该算法通过对工件序列邻域变换来模拟教授过程,同时采用概率模型作为知识收集的平台,每个学生通过该平台交流学习,实现了学生之间的自学习。基于标准测试用例的测试结果验证了HDTPL有效性和优越性。(2)研究了分布式零等待流水车间调度问题,建立了该问题的混合整数规划模型以及提出了若干邻域变换的加速算法,有效的减少了计算的复杂度。针对分布式零等待流水车间调度问题,结合变邻域搜索、变邻域下降搜索、随机变邻域提出了三种迭代贪婪算法IG_VNS、IG_VND、IG_RNS。大量仿真实验,表明所提出的算法求解效果优于当前同领域其他分布式车间调度算法。(3)研究了带有准备时间多目标分布式零等待流水车间调度问题,考虑了最大完成时间和总延迟时间为优化目标。在每台机器上,从当前工件加工完成到下一工件开始加工前存在准备时间。提出了一种基于Pareto非支配解的分布估计算法求解上述问题。建立了三种概率模型,即工件在空工厂的概率、两个工件在同一工厂的概率、两个工件相邻的概率。在该模型的基础上,提出了一种基于参考模板的采样算法来产生后代,并对档案集以及后代个体进行了多目标局部搜索。实验表明,所提出的算法优于其他相关算法,并且所得到的解具有良好的分布性和逼近性。(4)针对零空闲流水车间调度问题,提出一种基于直方图模型的Memetic算法(MANEH)。MANEH考虑了工件的顺序以及相似工件块,采用基于混合边和点直方图模型的随机采样交叉方式,避免工件选择的盲目性。在局部搜索部分,在变邻域搜索中加入了随机参考邻域搜索以及基于模拟退火的接受准则,使得局部搜索能力进一步提高。基于大规模测试用例的实验验证了MANEH优越性。(5)针对带有交货期约束的零空闲流水车间调度问题,提出一种基于概率教授的离散教学优化算法(HDTLM)。在教授阶段,根据优秀学生个体和教师构建概率模型,对概率模型采样生成一系列位置序列;采用共有序列的概念来代替原始教学优化算法平均个体的概念,根据位置序列和共有序列来产生新个体。在学习阶段,根据学生的学习水平,将学生分为三个层次,从上到下传递知识。通过与当前较为先进的几种算法对比,验证了HDTLM的优越性。(6)研究了带有装配过程的分布式零空闲流水车间调度问题。针对已有工件分配规则的不足,提出了一种工件分配规则,使得同一产品的相关工件加工顺序尽可能紧凑,同时使得装配过程尽早开始,减少装配等待时间。针对带有装配过程的分布式零空闲车间调度问题,提出混合迭代局部搜索(HILS)算法和混合变邻域搜索(HVNS)算法。通过求解标准测试用例,验证了HILS和HVNS的性能显著优于同领域同其他相关算法。
其他文献
日本乙型脑炎病毒(Japanese encephalitis virus,JEV)是黄病毒属的一种蚊媒病毒,是急性病毒性脑炎和流行性脑炎的常见病因。世界上大约60%的人口居住在JEV流行地区。由于全球变暖,病毒继续传播到以前未受影响的地区。JEV感染机体后大部分的病毒能被机体的免疫系统清除,但有少量病毒能够逃逸机体的免疫反应并穿越血脑屏障(blood-brain barrier,BBB)进入到中枢
本文针对凉山南红玛瑙、保山南红玛瑙、巴西玛瑙、马达加斯加玛瑙、北红玛瑙、宣化战国红玛瑙、大同玛瑙七个品种玛瑙进行实验,将各个品种分类进行热处理,并利用宝石显微镜、扫描电镜、红外光谱、拉曼光谱、光纤光谱、差热分析等现代测试技术,对各品种玛瑙加热前后的各项性质变化进行了详细的分析研究。通过显微观察可知,玛瑙在热处理过程中发生了一系列颜色及结构上的变化。随着温度的上升,各样品均有颜色发灰的现象出现。大同
目的:近年来,全球恶性肿瘤的总体发病率呈现持续升高的趋势,死亡人数上升。恶性肿瘤等慢性非传染性疾病已成为全球的第二大死因,2010年恶性肿瘤造成的疾病负担占总疾病负担的
2001年越共九大的召开在越南历史上具有特别的意义,从越共理论思维的角度来看,这一年是越共理论成果取得重大突破的一年。事物的发展不是一蹴而就的,越共九大召开前越南走过了十五年的革新历程,这十五年理论和实践的发展为越共九大取得质的飞跃提供了量的积累。越共对马克思主义的灵活运用和准确把握为越南革新实践提供了正确的行动指引。越南在经济、政治、社会建设领域的革新实践取得了明显的成效,这离不开理论思维革新的
岩黄连(Corydalis saxicolae Herba)为罂粟科植物石生黄堇(Corydalissaxicola Bunting)的全草,其生物碱提取物临床用于治疗急性黄疸型肝炎、肝硬化、肝癌、疮疖肿毒、急性肠
近些年来,我国经济快速发展,居民生活水平不断提升且越来越追求高质量的生活。居住环境在人们生活中逐渐占有重要地位,因此极大促进了我国建筑行业的发展。建筑行业关系着国
随着数码相机和智能手机的普及,以及网络和微博的快速发展,数字图像和视频已经成为日常生活中最受欢迎的一种信息表现和传递沟通的媒介。每天海量的数字媒体信息汇聚到互联网
现如今,随着互联网技术以及通信技术的快速发展,数字图像已经成为人们日常生活中信息传递的重要方式。据统计,2011年以来,世界产生的数字照片总量达到上百亿张,而且这个数量
随着计算机以及通信技术的不断提升,云计算也得到了飞速发展。它的发展不仅为人们的工作和生活提供了方便,同时还节约了公共资源,提高了资源利用率。云计算除了可以为用户提