An Improved Iterated Greedy Algorithm for Solving Rescue Robot Path Planning Problem with Limited Survival Time

Effective path planning is crucial for mobile robots to quickly reach rescue destination and complete rescue tasks in a post-disaster scenario.In this study,we investigated the post-disaster rescue path planning problem and modeled this problem as a variant of the travel salesman problem(TSP)with life-strength constraints.To address this problem,we proposed an improved iterated greedy(IIG)algorithm.First,a push-forward insertion heuristic(PFIH)strategy was employed to generate a high-quality initial solution.Second,a greedy-based insertion strategy was designed and used in the destruction-construction stage to increase the algorithm’s exploration ability.Furthermore,three problem-specific swap operators were developed to improve the algorithm’s exploitation ability.Additionally,an improved simulated annealing(SA)strategy was used as an acceptance criterion to effectively prevent the algorithm from falling into local optima.To verify the effectiveness of the proposed algorithm,the Solomon dataset was extended to generate 27 instances for simulation.Finally,the proposed IIG was compared with five state-of-the-art algorithms.The parameter analysiswas conducted using the design of experiments(DOE)Taguchi method,and the effectiveness analysis of each component has been verified one by one.Simulation results indicate that IIGoutperforms the compared algorithms in terms of the number of rescue survivors and convergence speed,proving the effectiveness of the proposed algorithm.

A Modi ed Iterated Greedy Algorithm for Flexible Job Shop Scheduling Problem

The flexible job shop scheduling problem(FJSP) is considered as an important problem in the modern manufacturing system. It is known to be an NP-hard problem. Most of the algorithms used in solving FJSP problem are categorized as metaheuristic methods. Some of these methods normally consume more CPU time and some other methods are more complicated which make them di cult to code and not easy to reproduce. This paper proposes a modified iterated greedy(IG) algorithm to deal with FJSP problem in order to provide a simpler metaheuristic, which is easier to code and to reproduce than some other much more complex methods. This is done by separating the classical IG into two phases. Each phase is used to solve a sub-problem of the FJSP: sequencing and routing sub-problems. A set of dispatching rules are employed in the proposed algorithm for the sequencing and machine selection in the construction phase of the solution. To evaluate the performance of proposed algorithm, some experiments including some famous FJSP benchmarks have been conducted. By compared with other algorithms, the experimental results show that the presented algorithm is competitive and able to find global optimum for most instances. The simplicity of the proposed IG provides an e ective method that is also easy to apply and consumes less CPU time in solving the FJSP problem.

Effective Iterated Greedy Algorithm for Flow-Shop Scheduling Problems with Time lags

Flow shop scheduling problem with time lags is a practical scheduling problem and attracts many studies. Permutation problem（PFSP with time lags） is concentrated but non-permutation problem（non-PFSP with time lags） seems to be neglected. With the aim to minimize the makespan and satisfy time lag constraints, efficient algo- rithms corresponding to PFSP and non-PFSP problems are proposed, which consist of iterated greedy algorithm for permutation（IGTLP） and iterated greedy algorithm for non-permutation （IGTLNP）. The proposed algorithms are verified using well-known simple and complex instances of permutation and non-permutation problems with various time lag ranges. The permutation results indicate that the proposed IGTLP can reach near optimal solution within nearly 11% computational time of traditional GA approach. The non-permutation results indicate that the proposed IG can reach nearly same solution within less than 1% com- putational time compared with traditional GA approach. The proposed research combines PFSP and non-PFSP together with minimal and maximal time lag consideration, which provides an interesting viewpoint for industrial implementation.

An Iterated Greedy Algorithm with Memory and Learning Mechanisms for the Distributed Permutation Flow Shop Scheduling Problem

The distributed permutation flow shop scheduling problem(DPFSP)has received increasing attention in recent years.The iterated greedy algorithm(IGA)serves as a powerful optimizer for addressing such a problem because of its straightforward,single-solution evolution framework.However,a potential draw-back of IGA is the lack of utilization of historical information,which could lead to an imbalance between exploration and exploitation,especially in large-scale DPFSPs.As a consequence,this paper develops an IGA with memory and learning mechanisms(MLIGA)to efficiently solve the DPFSP targeted at the mini-malmakespan.InMLIGA,we incorporate a memory mechanism to make a more informed selection of the initial solution at each stage of the search,by extending,reconstructing,and reinforcing the information from previous solutions.In addition,we design a twolayer cooperative reinforcement learning approach to intelligently determine the key parameters of IGA and the operations of the memory mechanism.Meanwhile,to ensure that the experience generated by each perturbation operator is fully learned and to reduce the prior parameters of MLIGA,a probability curve-based acceptance criterion is proposed by combining a cube root function with custom rules.At last,a discrete adaptive learning rate is employed to enhance the stability of the memory and learningmechanisms.Complete ablation experiments are utilized to verify the effectiveness of the memory mechanism,and the results show that this mechanism is capable of improving the performance of IGA to a large extent.Furthermore,through comparative experiments involving MLIGA and five state-of-the-art algorithms on 720 benchmarks,we have discovered that MLI-GA demonstrates significant potential for solving large-scale DPFSPs.This indicates that MLIGA is well-suited for real-world distributed flow shop scheduling.

A Penalty Groups-Assisted Iterated Greedy Integrating Idle Time Insertion:Solving the Hybrid Flow Shop Group Scheduling with Delivery Time Windows

The hybrid flow shop group scheduling problem(HFGSP)with the delivery time windows has been widely studied owing to its better flexibility and suitability for the current just-in-time production mode.However,there are several unresolved challenges in problem modeling and algorithmic design tailored for HFGSP.In our study,we place emphasis on the constraint of timeliness.Therefore,this paper first constructs a mixed integer linear programming model of HFGSP with sequence-dependent setup time and delivery time windows to minimize the total weighted earliness and tardiness(TWET).Then a penalty groups-assisted iterated greedy integrating idle time insertion(PG IG ITI)is proposed to solve the above problem.In the PG IG ITI,a double decoding strategy is proposed based on the earliest available machine rule and the idle time insertion rule to calculate the TWET value.Subsequently,to reduce the amount of computation,a skip-based destruction and reconstruction strategy is designed,and a penalty groups-assisted local search is proposed to further improve the quality of the solution by disturbing the penalized groups,i.e.,early and tardy groups.Finally,through comprehensive statistical experiments on 270 test instances,the results prove that the proposed algorithm is effective compared to four state-of-the-art algorithms.

Intelligent Optimization Under Multiple Factories: Hybrid Flow Shop Scheduling Problem with Blocking Constraints Using an Advanced Iterated Greedy Algorithm

The distributed hybrid flow shop scheduling problem(DHFSP),which integrates distributed manufacturing models with parallel machines,has gained significant attention.However,in actual scheduling,some adjacent machines do not have buffers between them,resulting in blocking.This paper focuses on addressing the DHFSP with blocking constraints(DBHFSP)based on the actual production conditions.To solve DBHFSP,we construct a mixed integer linear programming(MILP)model for DBHFSP and validate its correctness using the Gurobi solver.Then,an advanced iterated greedy(AIG)algorithm is designed to minimize the makespan,in which we modify the Nawaz,Enscore,and Ham(NEH)heuristic to solve blocking constraints.To balance the global and local search capabilities of AIG,two effective inter-factory neighborhood search strategies and a swap-based local search strategy are designed.Additionally,each factory is mutually independent,and the movement within one factory does not affect the others.In view of this,we specifically designed a memory-based decoding method for insertion operations to reduce the computation time of the objective.Finally,two shaking strategies are incorporated into the algorithm to mitigate premature convergence.Five advanced algorithms are used to conduct comparative experiments with AIG on 80 test instances,and experimental results illustrate that the makespan and the relative percentage increase(RPI)obtained by AIG are 1.0%and 86.1%,respectively,better than the comparative algorithms.

基于IIGA的分布式装配置换流水车间调度

针对分布式装配置换流水车间调度问题,提出一种改进的迭代贪婪算法进行求解。首先,以最小化总流经时间为优化目标建立数学模型,提出一种改进的迭代贪婪算法,采用结合CDS(campbell dudek smith)和NEH(nawaz-enscore-ham)的启发式方法以生成较高质量的初始解,提高种群的多样性;其次,针对可重构产品与作业设计破坏和重构过程,将移除的序列插入指定位置,采用本地搜索策略获得新的解决方案;最后,通过不同规模的仿真实验对本文所提算法与其他四种智能算法进行对比,实验结果表明改进的迭代贪婪算法在求解分布式装配置换流水车间调度方面具有高效性和稳定性。

改进迭代贪婪算法求解可重入流水车间调度问题

可重入混合流水车间是在混合流水车间的基础上增加了可重入特性,具有更高的调度复杂性。为了求解可重入混合流水车间调度问题,首先建立了调度优化模型,优化目标为最小化最大完工时间,然后提出一种带精英调整的学习型迭代贪婪算法(LIG-EA)。LIG-EA算法采用基于工件的编码方式,对重组后的染色体进行解码。种群分为精英个体和普通个体两部分,对精英个体进行精英破坏重建和基于关键工件的染色体调整,对普通个体进行学习机制的构建和普通个体的破坏重建。为提高初始种群质量,采用NEH启发式算法进行种群初始化,并针对可重入混合流水车间的重入特性,在重建操作中增加了插入有效性判断,提高了算法的运行速度。通过大量实验表明LIG-EA算法能够有效求解可重入混合流水车间调度问题。

基于贪婪算法的大数据兼容性云存储方法仿真

现阶段云环境下大数据的存储仍存在存储效率低、带宽合理性差的问题,因大数据的数量巨大、难收集和分析的特点,导致很难实现大数据的精准兼容存储。为此提出基于贪婪算法的大数据兼容性云存储方法。根据大数据云存储流程获取数据存储基本框架。引入贪婪算法,通过贪婪算法的循环迭代重构云存储节点的比特功率,使初始云存储环境转化成具有相同访问数据选择策略的优化云存储环境,提高大数据云存储流程的兼容性,完成大数据兼容性的云存储。实验测试结果表明,提出方法在规定时间内的数据漏存储量较少,且用户下载数据的响应时间始终低于5ms,大数据兼容性云存储的错误样本量低于100bit,说明提出方法的可应用性较强,研究价值较高。

求解能耗成本平衡的分布式阻塞流水线调度群体迭代贪婪算法

在经典分布式流水车间调度问题基础上,本文构建了具有序列相关准备时间的分布式阻塞流水线调度问题(DBFSP SDST)的混合线性整数规划模型(MILP),以均衡各工厂能耗成本为优化目标,提出了基于群体优化的迭代贪婪算法(PEIG).该算法针对零缓冲区和多工厂生产模式,设计了问题特性的启发式方法;针对迭代贪婪算法(IGA)的优势和不足,提出了基于群体的局部搜索策略、多邻域搜索结构和增强的跨工厂破坏重构方法,以进一步平衡所提算法的全局探索和局部搜索能力.通过270个测试算例的数值仿真,以及与最新4种代表算法的统计比较,本文验证了所提PEIG算法的优越性,能为中大规模的DBFSP SDST提供更优的调度方案.

Distributed Flow Shop Scheduling with Sequence-Dependent Setup Times Using an Improved Iterated Greedy Algorithm

To meet the multi-cooperation production demand of enterprises,the distributed permutation flow shop scheduling problem(DPFSP)has become the frontier research in the field of manufacturing systems.In this paper,we investigate the DPFSP by minimizing a makespan criterion under the constraint of sequence-dependent setup times.To solve DPFSPs,significant developments of some metaheuristic algorithms are necessary.In this context,a simple and effective improved iterated greedy(NIG)algorithm is proposed to minimize makespan in DPFSPs.According to the features of DPFSPs,a two-stage local search based on single job swapping and job block swapping within the key factory is designed in the proposed algorithm.We compare the proposed algorithm with state-of-the-art algorithms,including the iterative greedy algorithm(2019),iterative greedy proposed by Ruiz and Pan(2019),discrete differential evolution algorithm(2018),discrete artificial bee colony(2018),and artificial chemical reaction optimization(2017).Simulation results show that NIG outperforms the compared algorithms.

求解流水车间订单接受与调度问题的多线程并行迭代贪婪算法

针对流水车间实际生产过程中交货期短和生产能力不足的困难,研究了流水车间订单接受与调度问题,并以企业生产总净利润最大化为目标建立了数学优化模型。鉴于传统迭代贪婪算法求解流水车间调度问题的优势与不足之处,提出了一种多线程并行迭代贪婪算法(MPIG)。在算法的初始化阶段以及破坏重构阶段分别设计基于NEH(Nawaz-Enscore-Ham)的初始解产生方法以及融合不同破坏优先级的破坏方式。为提高算法搜索效率,提出了一种多线程并行搜索策略。首先利用二分查找算法快速找到订单在待插入序列中的拒绝点,随后通过多个线程同时搜索订单在序列中的局部最优位置,并最终找到订单最佳插入位置。实验结果表明,与解决类似生产调度问题的相关智能优化算法相比,所提出的MPIG具有更好的求解质量以及求解稳定性。同时,与实际生产过程中常用的启发式调度方法相比,所提出的算法在目标值上表现出不低于11%的改进率,可以有效增加企业生产总净利润,减小拖期成本。

基于改进贪心算法的电力通信网故障诊断方法

现行方法在电力通信网故障诊断中的效果不佳,灵敏度和查准率均较低,为解决现行方法存在的缺陷与不足,提出基于改进贪心算法的电力通信网故障诊断方法。利用数据采集卡采集通信网物理层、链路层、网络层和传输层状态数据信息,建立通信网故障诊断问题模型,通过对贪心算法迭代周期的优化,实现对贪心算法的改进,利用改进贪心算法求解问题模型,实现电力通信网故障诊断决策。实验证明,该设计方法灵敏度在95%以上,查全率在90%以上,在电力通信网故障诊断领域具有良好的应用前景。

有向传感器网络覆盖增强问题的贪婪迭代算法

在有向传感器网络中,可以通过调整节点的感知方向来增强目标区域的覆盖率.提出了有向传感器网络覆盖增强问题的一种贪婪迭代算法,在每次迭代中,调整那些使得覆盖率增加最大的节点的感知方向,重复此迭代过程直至通过调整任一节点的感知方向已不能再增加覆盖率.此外,还提出了一种通过计算几何求解该算法中区域计算问题的方法,以提高计算精度和减少计算时间.大量的仿真实验结果表明,该算法的执行时间较短,收敛速度较快,能够获得比现有算法更高的目标区域覆盖率.

一种新的混合粒子群算法求解置换流水车间调度问题

针对粒子群算法易早熟的缺点,提出了一种结合迭代贪婪(IG)算法的混合粒子群算法。算法通过连续几代粒子个体极值和全局极值的变化判断粒子的状态,在发现粒子出现停滞或者粒子群出现早熟后,及时利用IG算法的毁坏操作和构造操作对停滞粒子和全局最优粒子进行变异,变异后利用模拟退火思想概率接收新值。全局最优粒子的改变会引导粒子跳出局部极值的约束,增加粒子的多样性,从而克服粒子群的早熟现象。同时,为了使算法能更快找到或逼近最优解,采用了循环迭代策略,在阶段优化结果的基础上,周而复始循环迭代进行求解。将提出的混合粒子群算法应用于置换流水车间调度问题,并在问题求解时与几个具有代表性的算法进行了比较。结果表明,提出的算法能够克服粒子群早熟,在求解质量方面优于其他算法。

一种基于加权迭代贪婪算法的InSAR相位解缠的新方法

该文针对干涉SAR二维相位解缠问题,提出了一种利用贪婪算法提高解缠精度的新方法。首先从理论上推导了贪婪算法相位解缠的基本原理,然后提出了一种迭代加权的贪婪算法,以克服传统贪婪算法解缠结果收敛于局部最优解的弊病,最后利用仿真数据和实际数据进行实验分析,验证了本文算法的有效性。

60 GHz毫米波通信中贪婪迭代的波束成形方法

目前,60 GHz毫米波通信标准(802.11.ad,802.15.3c)中采用基于码本的波束成形技术,其性能仍有提升空间且在天线数较大时,搜索复杂度较高。该文基于以上两点提出了一种贪婪迭代的波束成形方法。首先寻找最佳分区中的中心波束作为初值,然后逐次在每根天线上选取移相器可能取值(1,-1,i,-i)中的最优值作为权重值,最后在收发端进行迭代,直至算法收敛。仿真表明,该方法不仅能够获得更高的频谱效率,同时具有线性复杂度,在毫米波阵列天线数较多时具有较大的优势。

基于贪婪思想的二阶段无线传感器网络定位算法

近些年来,将优化算法应用到节点定位问题当中成为了一个研究热点.本文假设下一次定位结果为准确坐标,对前后两次定位结果邻居节点之间距离关系进行深度分析和推导,得到一个邻域函数.在此基础上根据贪婪思想,提出了贪婪定位算法.为了达到更精确的定位结果,本文将贪婪定位算法分成两个阶段:第一阶段,根据贪婪迭代优化得到一组初始定位结果;第二阶段将满足一定条件的未知节点升级为锚节点,重新执行第一阶段的过程,重复第二阶段,直到没有未知节点可以升级为锚节点为止.实验结果表明,无论是定位精确度还是算法执行时间,本文所提算法都比当前的一些优化定位算法要好.

考虑运输的柔性流水车间多处理器任务调度的混合遗传优化算法

多处理器任务调度在制造业有着较广泛的应用,为了解决实际柔性流水车间环境下的多处理器任务调度优化问题,研究了考虑运输时间和释放时间的多阶段柔性流水车间多处理器任务调度问题,该问题为NP-hard问题,以最小化最大完工时间为目标建立了柔性流水车间多处理器任务调度整数规划模型。为有效求解该问题,首先研究了工件加工机器流生成机制、单工件加工机器流矩阵编码方案和批量工件加工机器流编码方案。进而设计了基于机器空闲随机筛选的工件安排机制,产生该规划的初始解生成方法,以最小化最大完工时间原则进行新解筛选。然后构建基于工件顺序与加工机器流同步交叉的新解更新过程、基于工件顺序与加工机器流同步变异的新解调整过程,并利用迭代贪婪算法完成调整和重建操作,产生全新方案以改善求解质量,最终形成结合迭代贪婪算法的混合遗传融合优化策略。仿真实验利用解的下界得出偏差百分比,分别用遗传算法、迭代贪婪算法和混合遗传融合优化算法对不同规模的问题进行测试,结果表明,混合遗传融合优化算法能够获得较好的近优解。

基于贪婪随机自适应过程的多类型卫星联合任务规划技术

对地观测卫星任务规划问题需要考虑侧视、星上能量、数据容量和数据传输等多种约束,是一类复杂的组合优化问题,现有研究大多对问题进行了不同程度的简化。面向多种载荷类型卫星的联合任务规划问题,考虑上述多种约束,基于贪婪随机自适应搜索过程提出了一种新的混合算法对问题进行求解。实验结果表明,该混合算法在多星联合任务规划领域是可行有效的。