Optimization of project payment schedules with Nash equilibrium model and genetic algorithm

To minimize the deviations of the net present values of project payment for both the owner and the client and optimize project payment schedules, a Nash equilibrium model based on game theory was set up and a genetic algorithm was developed to work out the Nash equilibrium solution with a two-stage backward inductive approach that requires the client responds to the owner’s payment schedule with an activity schedule so as to maximize the client’s net present value of cash flows. A case study demonstrated that a payment schedule at the Nash equilibrium position enables both the owner and the client to gain their desirable interests, thus is a win-win solution for both parties. Despite the computation time of the proposed algrithm in need of improving, combining Nash equilibrium and genetic algorithm into a complete-information dynamic-game model is a promising method for project management optimization.

考虑序列相关准备时间的分布式柔性作业车间调度研究

针对考虑序列相关准备时间的分布式柔性作业车间调度问题,提出以最小化最大完工时间为优化目标的混合整数线性规划模型,并提出一种改进遗传算法。采用基于负荷均衡的种群初始化方法提高初始种群质量,根据问题特性构造6个局部扰动算子,设计多重局部扰动策略提高算法的局部搜索能力。通过扩展柔性作业车间调度基准生成测试算例,使用正交实验确定算法参数。实验结果表明,所提改进策略能够有效提高算法性能,求解结果优于对比算法,验证了调度模型和所提算法的可行性和有效性。

机场场面滑行道与跑道运行综合优化调度

考虑到机场场面多资源之间的耦合性影响场面整体调度性能以及场面一体化综合调度模型存在求解时间长的问题,研究了场面滑行道调度与跑道调度问题两步综合优化调度方法。方法将整体调度过程分为两个步骤分别进行处理:第一步考虑停机位区域的滑行冲突与跑道运行间隔约束构建多跑道航班起降序列优化模型,并设计遗传算法求解;第二步,将步骤一获得的跑道起降顺序作为第二步的约束,同时考虑航班场面滑行区的滑行冲突以及跑道间隔约束构建了综合调度模型,为进离场航班生成滑行道和跑道的综合调度方案。实验结果表明,该两步综合优化调度方法可以在满足运行需求的计算时间内实现场面滑行道和跑道的综合优化调度。

基于表达式树的顺序柔性车间调度问题求解

为求解顺序柔性车间调度问题,提出一种表达式树结构的描述模型和一种工序顺序的随机生成方法,建立了以最大完工时间为优化目标的数学模型及其遗传算法求解流程;设计了相应的染色体编解码方法,并根据编码方式选择合适的遗传操作,该编码由0和1组成,描述形式简洁且任意形式均表示可行解。在不同规模及柔性指标的测试案例上进行实验,以平均解和标准差作为指标评价了模型的有效性。通过与无顺序柔性模型、随机顺序模型和柔性工序段模型对比,验证了表达式树模型的优化性能。

不确定条件下基于区间灰数的柔性车间调度

为了获得柔性车间在不确定条件下的最优调度方案,提出了基于区间灰数和操作顺序自适应遗传算法的车间调度方法。考虑了加工时间模糊、机床维护等不确定条件,建立了以加工时间区间灰数最小为目标的优化模型。在求解算法上,根据染色体聚集度自适应调整遗传操作顺序,保持了算法在不同情况下的进化能力,从而提出了基于操作顺序自适应遗传算法的调度方法。以某车间的生产调度案例为例,经仿真验证,与遗传算法、精英保留遗传算法和候鸟算法等相比,操作顺序自适应遗传算法的完工时间区间灰数最小,为[74,84]min;且调度方案满足生产顺序约束和时间约束,是可行的调度方案。实验结果表明,操作顺序自适应遗传算法在车间调度中是有效可行的。

汽车制造涂装-总装缓存调序区调度优化问题的研究

当今世界绿色制造是大势所趋,有效的生产线布局设计方法可以减少加工过程中的资源浪费。本文聚焦汽车制造涂装-总装缓存调序区,针对其存在的设备利用率低、待机时间长、交接效率低等核心问题,构建了一个多目标规划模型。该模型综合考虑了多约束条件,包括汽车制造过程中的缓冲区设备利用、交接以及调度时间等因素;严格遵循PBS约束及相关时间数据,根据涂装出车序列,结合PBS区域调度能力及限制,确保模型的精准性和实用性。为求解这一复杂的多目标优化问题,提出了一种创新的求解方法,该方法结合了改进粒子群算法和遗传算法的优势,能够更有效地找到最优解,不仅为汽车制造涂装-总装缓存调序区的调度问题提供了新的理论支撑,而且为探究独立缓冲区对汽车制造待产车调度的影响开辟了新的途径。

一类无缓冲区涂装喷漆排序问题

研究了一类无缓冲区的汽车涂装车间喷漆生产排序问题.给出了一种数学模型,该模型以喷涂颜色改变次数最少为目标,并要求保持焊装车间产出白车身类型的顺序.为解决这一问题,设计了一种遗传算法.该算法采用子串交换实现交叉,采用互换算子实现变异,其优点在于减少了遗传过程中的修补工作量.通过一个实际的例子验证了该算法.计算结果显示,所设计的算法能够较好地求解上述模型.该研究对焊装车间与涂装车间之间未设置线性缓存系统或采用先进先出(FIFO)缓存系统的汽车制造企业具有较好的实用价值.

家庭智能用电任务调度优化模型及其算法研究

针对家庭负荷的优化调度,提出了一种家庭智能用电任务调度优化模型。根据不同家电设备的用电特点,采用集合论语言对不同用电任务进行描述定义,建立以负荷峰值、用电费用为优化目标,以家庭负荷特性及运行状态为约束的多目标优化问题。提出了基于混合编码遗传算法的求解算法,算法中针对不同用电任务分别设计了不同的算法编码及算法操作策略,实现对家庭智能用电任务调度问题的单目标和多目标优化求解。通过家庭用电任务模拟算例对该算法性能进行了验证,结果表明该算法能够较好地实现家庭用电任务的优化调度。

基于多色集合的改进遗传算法求解多品种柔性调度问题

为克服传统遗传算法求解调度问题所存在的早熟或收敛过慢等不足,提出基于多色集合理论的改进遗传算法。在编码、解码和变异过程中,通过搜索围道矩阵提高算法速度,进而提高求解效率;采用单层编码方式表示调度问题中的双层约束,以降低算法的时间与空间复杂度。通过实例比较验证了所提算法的可行性与优越性。

动态Job-Shop调度问题的一种自适应遗传算法

提出了基于序列号的、独特的混合编码与级联编码相结合的遗传编码构造方法 ,给出了序列海明距离的定义和具体的计算方法 ,并引入到自适应遗传算法中。实例仿真计算的结果表明 ,提出的自适应遗传算法提高了全局求解能力 ,在解决动态Job -Shop调度问题时具有明显的优越性。

基于博弈论的虚拟制造网络车间调度优化方法

针对虚拟制造网络中的车间调度问题,提出了一个非合作博弈调度优化模型,将车间调度问题转化为一场博弈。在分析该博弈调度模型的理想纳什均衡存在性的基础上,提出了D最小纳什均衡的概念。结合虚拟制造网络中车间调度问题的特点,设计了染色体编码与解码方案以及适应度函数,提出了一种基于遗传算法的博弈调度求解算法来求得该博弈调度模型的D最小纳什均衡。在若干基准实例上验证了该方法的有效性。

单件车间调度问题的改进型病毒进化遗传算法

针对单件车间调度问题,设计了一种改进型病毒进化遗传算法IVEGA。为提高局部搜索能力,有效地避免丢失优秀解,缩小搜索空间,算法在主个体遗传过程和病毒感染过程中分别加入了主群体知识库和病毒群体知识库,并引入学习机制。通过对11个经典的Benchmarks问题进行了求解,结果表明了IVEGA的相对偏差为1.66%。

改进的多任务分配与调度遗传算法

提出了一种改进的混沌遗传算法,定义了问题模型,采用一任务序列加一主机序列的编码表示,并由约束关系阶段随机产生合法调度。为确保生成新调度,改进了交叉机制;为保持解的多样性和均衡负载,设计了任务均衡变异算子。为利用混沌优化技术,交叉、变异频率都由混沌序列动态控制。仿真结果表明,该算法总能得到最佳解。

到场飞机排序及调度问题的Memetic算法

为克服遗传算法求解多跑道系统到场飞机排序及调度问题时局部搜索能力不强的弱点,建立了该问题的混合整数0-1二次规划模型.通过证明同型飞机在每条跑道上都应按其预计到达该跑道时间的先后顺序依次着陆这一命题,设计了遗传算法与局部优化算法相结合的Memetic算法.算例结果表明:其运行10次的最劣解均不劣于其他遗传算法的最好解,且在5条跑道、20架飞机的情况下,Memetic算法求解时间为0.17 s,与精确算法相比,能满足实时应用需求.

作业车间调度的非合作博弈模型与混合自适应遗传算法

采用博弈理论,建立了一种基于非合作博弈的作业车间任务调度模型.在该任务调度模型中,将源于不同客户的制造任务映射为非合作博弈模型中的局中人,并将与制造任务包含的工序集所对应的可选加工设备映射为可行方案集,使各制造任务的加工完成时间和成本组合形成的多目标综合指标映射为收益函数,从而将对任务调度模型的求解转换为寻求非合作博弈模型的Nash均衡点.通过设计的爬山搜索混合自适应遗传算法、自适应交叉和变异算子,实现了对该任务调度非合作博弈模型的Nash均衡点的有效求解,同时算例仿真结果也验证了所提出的调度方法的正确性.

一类Job-shop车间生产计划和调度的集成优化

讨论一类Job-shop车间的生产计划和调度的集成优化问题,给出了该问题的非线性混合整数规划模型,并采用混合遗传算法进行求解。该模型利用调度约束来细化生产计划,以保证得到可行的调度解。在混合算法中,利用启发式规则来改善初始解集,并采用分段编码策略将计划和调度解映射为染色体。算例研究表明,该算法对求解该类问题具有很好的效果。

基于混合自适应遗传算法的相控阵雷达任务调度

针对相控阵雷达任务调度NP难题,提出一种混合自适应遗传算法进行求解。在构建相控阵雷达任务调度优化模型的基础上,通过混沌理论优化初始种群,采取精英保留和混合排名的选择策略以及设计自适应的交叉、变异算子来提升算法的搜索性能;在自适应遗传算法的框架下,提出启发式脉冲交错算法,以利用雷达任务中的等待期来交错执行其他任务的发射期或接收期。仿真结果表明:相比于基于遗传算法的调度方法,改进算法的搜索效率更高、结果更优;相比于传统启发式算法,改进算法的调度成功率、时间利用率和实现价值率均得到了提升,并有效降低了时间偏移率。

基于多色集合理论和遗传算法的加工中心工步排序研究

针对加工中心上一次装夹下复杂的工步排序问题,通过实例介绍一种基于多色集合理论和遗传算法的工步排序优化算法。首先,在分析工步排序原则和典型工艺路线的基础上,根据多色集合理论建立加工中心上工步排序问题的约束模型。然后,以辅助时间最短为优化目标,建立其数学优化模型。最后,将遗传算法应用到工步排序中从而得出最优解。实例证明,在多色集合约束模型约束下的遗传算法能够很好地求解加工中心上的工步排序问题,排序结果接近最优且可以大幅提高加工中心的效率。

基于模糊理论的软件项目调度算法

针对软件项目调度问题中信息的不确定性及资源分配的特殊性需要,提出了一种基于模糊理论的软件项目调度算法FS-SA。该算法采用模糊数表示任务的工期并应用遗传算法产生任务的调度序列。实验结果表明,FSSA算法能在很短的时间内得到理想的结果,有一定的应用价值。