存在无等待工序的综合调度混合算法研究

来源 :哈尔滨理工大学 | 被引量 : 0次 | 上传用户:czq8068
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
综合调度问题是一种加工与装配同时考虑的调度问题。这种调度充分考虑了个性化产品生产过程的特点:不同产品的结构特征、制造参数相差较大;大量非标准工件组装后再进行深入加工的情况普遍存在。无等待工序在钢铁铸造、精密装配、食品工业中广泛存在,其要求受无等待约束的工序必须无间断地处理。例如,在低温装配作业过程中,经过低温处理的工件需要马上进行装配作业,否则可能出现温度不均等情况,导致装配失败、达不到精度要求。所以,研究存在无等待工序的综合调度问题(No-wait Integrated Scheduling Problem,NWISP)可以从整体上优化个性化产品的生产过程,达到增产增效的效果。具体研究工作由以下几个部分组成:针对静态NWISP问题,以最小完工时间为目标,建立静态NWISP数学模型,提出了一种基于粒子群和遗传算法的混合方法(Genetic Algorithm and Particle Swarm Optimization,GA-PSO)进行求解。该算法借鉴了速度位置公式所表达的信息流向关系,以遗传操作为基础,将PSO的更新机制嵌入到GA算法中,形成了以双种群更新策略为基础的混合算法。为了处理无等待紧前工序数量大于1的情况,设计了基于最早适应策略的无等待虚拟工序编码、解码算法,使一组无等待工序解码后依然保持树形约束关系。实验数据表明所设计的GA-PSO算法可以获得比对照算法更短的完工时间,验证了算法是有效可行的。针对动态NWISP问题,采用事件重调度策略将动态的生产过程转换为在时间上连续的静态调度问题,以最小化总拖期作为调度目标。提出GA-VNS(Genetic Algorithm and Variable Neighborhood Search)混合算法,在每个事件时刻应用GA-VNS调度未完工任务和该时刻新到达的任务。GA-VNS考虑了柔性制造资源的情况,为其设计了柔性设备的冲突调整方法,解决了无等待紧前工序数量大于1时设备冲突的问题。实验数据验证了所提的优化方法有效可行,可以获得比对照算法更短的总拖期。多车间NWISP问题中存在运输约束、柔性制造资源。在多车间的情况下,工序处理完毕需要运送到紧后工序的设备所在车间,此时需要考虑不同车间的运输时间。为了处理多车间的情况,提出了适用于多车间柔性资源的冲突设备调整方法,保证了无等待紧前工序数量大于1时设备编码始终处于可行设备方案,而不会出现冲突。提出了适用于多车间的虚拟工序解码方法,保证了多车间约束条件和无等待约束条件。基于这些改进,提出了多车间无等待综合调度问题算法,使用变邻域算法进行局部优化,使用遗传算法进行全局优化。实验结果表明,所提的算法可以解决多车间NWISP问题,而且可以获得比对照算法更短的总拖期。针对多目标无等待综合调度问题(No-wait Multi-objective Integrated Scheduling Problem,NWMISP),同时考虑完工时间与总制造费用。将拥挤度策略、多目标非支配解策略嵌入到GA-PSO混合算法中,使之可以处理多目标问题。其中拥挤度策略可保抑制种群过度集中于某些个体的情况,多目标非支配解策略给出了多目标情况下个体排序的方法。实验结果表明,嵌入拥挤度策略和多目标非支配解策略的GA-PSO算法有效可行,能够解决NWMISP调度问题。在某些生产环境中,设备在投入使用之前需要预热(Warm-up),但是在离散的生产活动当中使设备时刻保持工作状态会极大地增加能源消耗,产生不必要的成本。将预热时间转换为一种特殊的准备时间(Setup Time),即准备时间与设备的初始状态相关。同时考虑这种特殊准备时间约束和无等待约束,建立了以总拖期最小化和总准备时间最小化的双目标数学模型。为了使用GA-PSO算法进行求解,提出了一种设备空闲信号驱动的解码方法,该解码方法可以同时处理特殊的准备时间约束和无等待约束。仿真实验结果表明所提算法不但有效可行,而且调度质量优于对照算法。
其他文献
排序(scheduling),是组合优化领域中最经典的问题之一。一般而言,排序指的是:给定机器和待加工的工件,对工件制定一个在机器上加工的计划,使得所有工件尽可能快的完工。随着人们对排序问题研究的深入,与排序相关的更为复杂的问题也被清晰的刻画了出来,成为了更贴合实际的研究热点。它们不但具有很高的理论价值,更具有非常广泛的应用背景。本文主要研究与排序相关的优化问题:排序博弈(scheduling g
学位
细胞焦亡是细胞程序性死亡中的一种,最早被发现参与免疫细胞抵抗病原菌感染过程。发生焦亡的免疫细胞细胞膜破裂,胞质内容物释放,进而引发更加强烈的免疫反应即炎症反应。细胞焦亡不仅在病原菌感染导致的炎症反应中发挥重要作用,而且在很多疾病如一些遗传性疾病、自身免疫性疾病以及癌症中都发挥了不可替代的作用。目前对细胞焦亡分子机制及其生理功能的研究已成为细胞死亡研究领域的前沿热点。然而不同于细胞凋亡,细胞焦亡从发
学位
胞磷胆碱作为一种可以治疗多种神经系统疾病的药物,在临床上有广泛的应用,展现了良好的安全性和有效性。由于化学法合成会涉及有毒试剂的使用且底物转化率较低,目前主要使用生物法进行合成。受限于关键底物的穿膜效率,胞磷胆碱的生物合成主要采用两步法,首先大量培养并富集微生物细胞,通过冻存处理提高细胞膜的通透性或者直接超声处理使细胞裂解,然后加入底物进行生物催化反应。这一生产过程工艺复杂、且耗时耗力。胞磷胆碱的
学位
可见光驱动的光催化技术在清洁能源和可再生能源以及废水处理领域具有重要的应用前景。然而,由于有限的光吸收效率和显著的电子-空穴复合,必须对半导体结构进行修饰以提高其光催化效率。从这个意义上讲,本文介绍了一种基于氧化铌(Nb2O5)和石墨相氮化碳(g-C3N4)的可见光活性光催化剂的合成、表征和应用。Nb2O5是一种有望替代其他半导体用于废水处理的新材料,因为它具有催化性能,如能够支持催化过程的表面基
学位
基于优质底盘宿主,通过异源表达实现功能蛋白和化学品的高水平、可调控生产,是目前合成生物学和代谢工程领域的研究热点和主要方向之一。由启动子介导的基因转录过程是决定基因表达强度和调控模式的关键步骤,一些来源于不同宿主的高效天然启动子被鉴定开发并广泛应用于学术研究和工业生产。然而,随着生物产业的快速发展,受限于有限的优质启动子数量及单一的信号响应模式,天然转录系统已经难以满足日渐多样化的研究及生产需求。
学位
新型的生物基聚合物有望替代传统的石油基聚合物解决环境污染和温室气体过量排放的问题,但是使用淀粉和糖等可食用原料生产生物基聚合物不仅提高了生产成本,还会造成粮食短缺等问题。来源广泛、供应量巨大且不可食用的木质纤维素可再生资源是生物基聚合物生产原料的最佳选择。本论文旨在利用木质纤维素作为原料,生产生物基聚合物及前体,具体包括聚3-羟基丁酸酯(Poly 3-hydroxybutyrate,PHB)以及生
学位
图谱理论是研究图的谱性质以及图的结构与图的谱性质之间关系的一个图论分支。图谱理论在很多研究领域都有着显著的应用。图的谱性质包括图的邻接矩阵,拉普拉斯矩阵以及距离矩阵等一些和图有关的矩阵的谱性质。在本文中,讨论了图的邻接矩阵谱性质的相关结论,主要涉及到图的邻接矩阵的零特征值,最小特征值,谱半径以及正负特征值的平方和。具体内容如下。在第二章中,讨论了在Wang等人给出的零度上下界|V(G)|-2m(G
学位
造血干/祖细胞(Hematopoietic stem/progenitor cell,HSPC)移植在治疗恶性血液疾病和免疫系统疾病方面有着广泛的应用。脐带血由于其中HSPC含量高、扩增能力强、免疫原性低、采集方便以及对供体无害等优势而成为理想HSPC来源。由于单份脐带血中HSPC的绝对数量有限,难以满足成年人治疗所需的剂量,限制了其临床应用。高效的HSPC体外扩增技术是突破这一难题的关键。目前的
学位
近年来,氢能经济在环境能源领域的发展热度日益提高,实现高效的可再生能源的电解水制氢技术是解决目前化石燃料燃烧所造成的一系列污染等问题的关键所在,其中实现酸性溶液中高效率的电解水制氢中的关键反应步骤——析氧反应(OER),具有重要的科研意义。有效设计并调控电催化阳极Ir基催化剂的析氧反应性能,实现高效率高寿命的电解水制氢能力,对推动氢能经济发展至关重要。本文将深入探究Ir基催化剂在OER应用上的的设
学位
群体决策是一组专家根据特定的决策标准对选项进行评价、排序并最终形成群组意见的过程。群体决策具有整合群组成员智慧、背景和知识等的优势,因而被广泛应用到选举、人员评估等多种现实问题中。当前群体决策问题面临两大主要挑战。其一,群体决策过程如何有效地降低主观性和不精确性,从而提高决策结果的可靠性;其二,在有人际关系网络的决策环境中,如何刻画专家意见形成的行为动力学特征。这两方面问题既涉及到群体决策的静态意
学位