解并行多机提前/拖后调度问题的并行遗传算法

为有效地解决带有公共交货期的非等同并行多机提前/拖后调度问题,设计了一种分段扩展排列编码的混合遗传算法,使遗传编码能同时反映调度方案和公共交货期,并对其初始种群产生、交叉和变异方法也进行了研究。同时为了更好地适应调度实时性和解大规模此类问题的需要,基于遗传算法自然并行性特点的基础上,实现了主从式控制网络模式下并行混合遗传算法。计算结果表明,此算法是有效的,优于启发式算法和遗传算法,有着较高的并行性,并能适用于大规模非等同并行多机提前/拖后调度问题。

最优公共交货期单机提前/拖后调度和对应的批次送货

本文考虑了一个包含工件生产和工件送货的单机调度问题。目标是寻找所有工件的公共交货期和每个工件的送货时间使得工件所受到惩罚(提前/拖后惩罚,送货费用等)的值最小。完成的工件按照批次进行送货,所有在公共交货期前完工的工件在最优交货期时间一起交付,对批次送货没有量的约束。本文确定了最优公共交货期,并给出了相应的排序。

解并行机提前／拖后调度问题的一种新并行遗传算法

针对交货期窗口非等同并行机提前/拖后调度问题,设计了一个基于向量组编码的新的遗传算法.此算法特点是编码方法简单,能有效地反映实际调度方案,即清楚反映出每台机器加工工件的代号和顺序,并能保证交叉和变异后个体自动满足约束条件,收敛速度快.同时为了更好地适应调度实时性和解大型此类问题的需要,在基于遗传算法自然并行性特点的基础上,实现了主从式控制网络模式下并行遗传算法.仿真结果表明,此算法是有效的,优于普通的遗传算法,具有较高的并行性,并能适用于解大型这类调度问题.

基于遗传算法的作业车间提前/拖期调度问题

针对带有交货期窗口硬约束并对提前/拖期零件进行惩罚的一类作业车间调度问题,设计了一种改进型遗传算法,该算法采用"逆向后推"和"顺向前拉"相结合的两阶段求解策略。针对部分染色体在解码过程中违反交货期窗口硬约束而产生非法解的问题,采用基于关键路径的染色体修复方法来调整染色体基因序列,以期实现在满足交货期窗口硬约束的同时降低零件拖期成本;在保持第一调度阶段拖期成本不变的基础上,采用基于逆向重调度的目标值修订方法来延迟零件开工时间,以降低在制品流动成本和成品提前库存成本。通过80组调度测试用例的仿真结果表明,该算法在降低调度总成本和拖期成本方面具有一定的优势。

求解作业车间提前/拖期调度问题的一种新解码方法

针对带有非正规性能指标的作业车间提前/拖期调度问题,基于工序编码方式,设计了一种适用于粒子、染色体等个体的三阶段解码方法。通过半主动解码操作,以增加初始调度解的搜索范围;采用插入式贪婪解码这类主动调度方法,以减少拖期零件子集的拖期惩罚成本。运用逆向主动解码操作来延迟所有零件的释放期,并在保证拖期零件完工时间不变的前提下进一步压缩提前惩罚成本。这种三层递阶解码方法有助于大幅度压缩提前/拖期惩罚总成本。将该解码方法应用于粒子群算法中的粒子解码过程,并通过粒子位置更新操作来实现调度解的迭代优化。通过120个随机调度算例的仿真实验,证明了该方法的有效性。

Job-shop提前/拖期调度问题的研究

基于模糊控制和遗传算法 ,提出了求解 Job- shop提前 /拖期问题的联合算法。用遗传算法确定可行调度序列 ,然后用模糊控制器对开工时间加以调整。模糊控制的引入为有效地求解 Job- shop提前 /拖期调度问题提供了新方法。

具有提前/拖期惩罚的热轧钢管批调度问题研究

建立了具有提前/拖期惩罚的热轧钢管批调度问题的混合整数非线性规划模型,提出并证明了给定合同排序下的最优组批方式,从而将原问题转化为易求解的合同排序问题.同时,建立了转化问题的数学模型并设计了遗传算法.仿真实验验证了模型和算法的有效性.

约束满足混合算法求解提前/拖期Job Shop调度问题

针对提前/拖期Job Shop调度问题,建立其约束满足优化问题模型,提出了一种约束满足与禁忌搜索结合的混合算法。该算法基于约束满足思想,通过约束传播技术和启发式修复算法,得到可行调度作为禁忌搜索算法的初始解;再进行关键路径上的邻域变换,优化当前解;并采用一种全局邻域交换策略,扩大搜索空间,改善优化结果。数据实验表明了该混合算法的可行性和有效性。

基于遗传算法的单机提前/拖期调度方法研究

针对对工件有不同交货期要求 ,并对提前 /拖期工件进行惩罚的一类单机调度问题 ,提出了基于遗传算法的优化方法 .提出一种基于“非”一致次序交叉算子的遗传算法 ,用于排序优化 ;在分析了惩罚函数性质的基础上 ,给出了最优开工时间算法 .对不同规模的调度问题 ,应用本文提出的算法与其它算法进行了比较 ,结果表明该方法具有优良的性能 .

软计算求解分布式多工厂单件制造业的提前/拖期生产计划问题

描述了分布式多工厂单件制造企业准时化生产计划问题 ,以实现最小化提前 /拖期惩罚费用、生产成本、产品运输费用之和为目标建立了 0 - 1规划数学模型 ;设计了基于模糊规则量化的方法求解模糊决策 ,并将模糊决策嵌入到遗传算法中的软计算方法求解模型 ,使得算法具有比分枝定界法更快速的寻找优解的能力以及更广泛的适应范围 .

流水车间作业提前/拖期调度问题研究

在非正规性能指标提前/拖期调度问题中,工件的加工顺序和每个加工活动的开始时刻都属于需要优化的变量,增加了求解的难度。针对这一问题,提出了采用分层调度模式求解流水车间提前/拖期调度问题的联合算法。首先,采用遗传算法对加工顺序进行寻优;其次,在给定调度序列的情况下采用启发式算法对加工开始时刻进行优化,制定插入机器空闲时段的策略,确定何时插入空闲时段和空闲时段的大小,即在给定顺序下确定工件加工活动的开始时刻,以满足在加工完所有工件后,使提前惩罚费用与拖期惩罚费用之和最小。数值计算结果证明了该联合算法的有效性。

求解带有时间窗和提前/拖期惩罚的飞机着陆问题的遗传算法

研究了带有时间窗、飞机着陆的总提前/拖期惩罚最小为目标函数的飞机着陆问题.针对此问题设计了一种遗传算法进行求解.染色体表示为飞机着陆次序和着陆跑道两个向量,一个新的解码算法来计算飞机的着陆时间.采用数据库OR-Library中的实例进行数值实验,实验结果表明:设计的算法是有效的,主要原因是解码算法能大大提高解的质量.该算法对于求解带有时间窗、目标函数为提前/拖期惩罚最小的调度问题具有借鉴意义.

不确定条件下的中间存储时间有限的Flow Shop提前/拖期调度问题

生产调度是企业生产过程中一个重要的部分,在实际生产调度过程中,会存在各种各样的不确定性.本文针对不确定条件下的具有不同交货期窗口的F low Shop提前/拖期调度问题,考虑了产品中间存储时间的有限性,用模糊数学的方法来表示产品的不确定处理时间,在模糊规划理论的基础上建立了相应的调度模型.并借鉴生物免疫系统的概念和机理,提出了解决此类特殊问题的模糊免疫调度算法.仿真结果表明了该模型的有效性和算法的较好的收敛效率.

交货期窗口下带有附加惩罚的单机提前/拖期调度问题

交货期窗口下的交货期确定和排序问题是调度领域研究的一个方面 .本文对交货期窗口下的单机作业问题进行了研究 ,目标函数不仅考虑提前 /拖期惩罚 ,还考虑附加惩罚 .假设如果任务在交货期窗口内完工 ,则不受提前/拖期惩罚 ;如果在交货期窗口外完工 ,将导致提前 /拖期惩罚 .本文确定了最优公共交货期 ,给出了相应的最优排序 ,并提出了一个多项式时间算法确定了使目标函数为最小的最优调度 ,最后的数值例子说明了算法的有效性 .

混合流水车间提前/拖期调度问题的DE优化解

针对JIT生产模式下的混合流水车间调度问题特点,提出了采用DE算法与指派规则联合调度策略求解流水车间提前/拖期调度问题。构建了混合流水车间的提前/拖期调度模型。详细论述了DE算法的实施流程和关键问题。在算法实施过程中,首先,采用DE算法进行全局寻优,完成生产任务指派,确定某个工件在某个工序在哪个工位加工;然后采用局部指派规则来确定工件在该工序的开工时间。在满足目标完成时间(交货期)的前提下,使提前惩罚费用与拖期惩罚费用之和最小。数值计算结果证明了该算法的有效性。

一类带有deadline约束的作业车间提前/拖期调度问题研究

针对带有零件deadline时间约束的一类作业车间提前/拖期调度问题,设计了一种改进型遗传算法(EGA)。EGA算法采用拖期优先的调度策略,将原有的非正规性能指标的E/T调度问题转化为拖期子问题、修复子问题和提前子问题,以此来降低E/T调度问题的求解复杂度。采用基于工序的编码方法,在染色体解码过程中,分别采用了主动解码、染色体修复和逆向重调度三阶段的解码操作,以期实现在满足零件deadline约束的前提下尽可能降低提前/拖期惩罚总成本。180个调度测试用例仿真结果表明,EGA算法在解决问题数、寻优能力、调度结果的均衡性等方面具有一定的优势。

批量制造业交货窗口提前/拖期生产计划方法

建立批量制造企业在交货期窗口下的提前／拖期生产计划模型，将交货期窗口（ｄｕｅ－ｗｉｎｄｏｗ）概念引入到带有能力约束的提前／拖期生产计划中，拓宽了生产计划问题研究的范围．并利用数学推导，将所建模型转化为线性规划模型，使得该模型运用单纯形法就可求取精确的最优解，从而解决了开发中的ＣＯＮＷＩＰ集成化生产管理软件对不确定交货期主生产计划的编制问题．

不确定性条件下存储时间有限型Flow Shop问题的提前/拖期调度研究

研究了具有不同交货期窗口的Flowshop提前/拖期调度问题,并考虑处理时间的不确定性以及存储时间的有限性,在模糊规划理论基础上,建立了带有提前/拖期的存储时间有限型Flowshop的调度模型,通过中间值最大隶属度算法,将原有的模糊调度模型转化为清晰的调度模型,并应用了遗传算法进行优化求解。仿真实验验证了算法的有效性。

基于模拟退火算法的单机提前拖期模型

针对实际加工过程中作业时间的不确定性,建立了模糊加工时间的单机提前/拖期模型.目标函数在考虑了任务的提前/拖期惩罚、安装时间惩罚以及模糊加工区间限值惩罚的基础上,求取最优加工时间,使目标函数值达到最小.并用模拟退火技术确定了任务的最优加工顺序,最后给出了仿真实例.

基于联姻遗传算法的混合Flowshop提前/拖期调度问题

混合流水车间 (Flowshop)提前 /拖期调度问题的目标是使工件的提前 /拖期惩罚成本最小 ,这是一个NP完全问题 ,很难用一般的方法解决。文中首先给出了问题的数学模型 ,然后采用联姻遗传算法求解该问题。