Single-machine scheduling to minimize total convex resource consumption with a constraint on total weighted flow time

In this paper, we consider single-machine scheduling problem in which processing time of a job is described by a convex decreasing resource consumption function. The objective is to minimize the total amount of resource consumed subject to a constraint on total weighted flow time. The optimal resource allocation is obtained for any arbitrary job sequence. The computational complexity of the general problem remains an open question, but we present and analyze some special cases that are solvable by using polynomial time algorithms. For the general problem, several dominance properties and some lower bounds are derived, which are used to speed up the elimination process of a branch-and-bound algorithm proposed to solve the problem. A heuristic algorithm is also proposed, which is shown by computational experiments to perform effectively and efficiently in obtaining near-optimal solutions. The results show that the average percentage error of the proposed heuristic algorithm from optimal solutions is less than 3%.     

A memetic algorithm for the optimal winner determination problem

In this paper, we propose a memetic algorithm for the optimal winner determination problem in combinatorial auctions. First, we investigate a new selection strategy based on both fitness and diversity to choose individuals to participate in the reproduction phase of the memetic algorithm. The resulting algorithm is enhanced by using a stochastic local search (SLS) component combined with a specific crossover operator. This operator is used to identify promising search regions while the stochastic local search performs an intensified search of solutions around these regions. Experiments on various realistic instances of the considered problem are performed to show and compare the effectiveness of our approach.     

Finding low autocorrelation binary sequences with memetic algorithms

This paper deals with the construction of binary sequences with low autocorrelation, a very hard problem with many practical applications. The paper analyzes several metaheuristic approaches to tackle this kind of sequences. More specifically, the paper provides an analysis of different local search strategies, used as stand-alone techniques and embedded within memetic algorithms. One of our proposals, namely a memetic algorithm endowed with a Tabu Search local searcher, performs at the state-of-the-art, as it consistently finds optimal sequences in considerably less time than previous approaches reported in the literature. Moreover, this algorithm is also able to provide new best-known solutions for large instances of the problem. In addition, a variant of this algorithm that explores only a promising subset of the whole search space (known as skew-symmetric sequences) is also analyzed. Experimental results show that this new algorithm provides new best-known solutions for very large instances of the problem.     

A memetic algorithm to solve an unrelated parallel machine scheduling problem with auxiliary resources in semiconductor manufacturing

In this paper, we propose a metaheuristic for solving an original scheduling problem with auxiliary resources in a photolithography workshop of a semiconductor plant. The photolithography workshop is often a bottleneck, and improving scheduling decisions in this workshop can help to improve indicators of the whole plant. Two optimization criteria are separately considered: the weighted flow time (to minimize) and the number of products that are processed (to maximize). After stating the problem and giving some properties on the solution space, we show how these properties help us to efficiently solve the problem with the proposed memetic algorithm, which has been implemented and tested on large generated instances. Numerical experiments show that good solutions are obtained within a reasonable computational time.     

文化基因算法在第四方物流路径规划中的应用

第四方物流路径问题是复杂的组合优化问题。基本遗传算法在第四方物流路径问题上存在随着问题规模扩大,算法的成功率和准确率不断下降等缺点。针对基本的遗传算法已经不能满足规模较大的第四方物流问题等缺点,结合实验分析,提出了一种以遗传算法为全局搜索策略的文化基因算法,并针对第四方物流的问题特点设计了相应的局部搜索策略。实验结果表明,与基本遗传算法相比,该混合算法不仅在求解质量上有了较大的改进,并且在大规模第四方物流问题上也能获得质量较好的解,算法的成功率和准确率明显高于基本的遗传算法。因此,基于遗传算法的文化基因算法是解决大规模第四方物流路径问题的一种有效方法。     

Real-coded memetic algorithms with crossover hill-climbing

This paper presents a real-coded memetic algorithm that applies a crossover hill-climbing to solutions produced by the genetic operators. On the one hand, the memetic algorithm provides global search (reliability) by means of the promotion of high levels of population diversity. On the other, the crossover hill-climbing exploits the self-adaptive capacity of real-parameter crossover operators with the aim of producing an effective local tuning on the solutions (accuracy). An important aspect of the memetic algorithm proposed is that it adaptively assigns different local search probabilities to individuals. It was observed that the algorithm adjusts the global/local search balance according to the particularities of each problem instance. Experimental results show that, for a wide range of problems, the method we propose here consistently outperforms other real-coded memetic algorithms which appeared in the literature.     

带机器人制造单元的作业车间调度仿真

针对带有机器人制造单元的作业车间调度优化问题, 在若干加工机器上可以加工具有特定加工工序的若干工件, 并且搬运机器人可以将工件在装卸载站与各加工机器间进行搬运. 在实际生产过程中, 由于不确定性, 特别是带有存货的加工单元, 要求工件的完工时间在一个时间窗内, 而不是一个特定的时间点. 因此针对此情况的作业车间, 考虑到其在求解问题过程中的复杂性和约束性等特点, 研究了在时间窗约束下, 目标值为最小化工件完成时间提前量和延迟量的总权重. 提出了一种将文化基因算法与邻域搜索技术(变邻域下降搜索)相结合的改进元启发式算法, 在求得最优目标值的同时, 可得到最优值的工件加工序列及机器人搬运序列. 通过实验结果表明, 所提出的算法有效且优于传统文化基因算法与遗传算法.     

A transgenetic algorithm applied to the Traveling Car Renter Problem

The Traveling Car Renter is a new problem and constitutes a generalization of the Traveling Salesman. Several applications arise from it, mainly in the scheduling optimization of rental cars and in other problems concerning transport systems. In this paper, an integer quadratic programming model is presented for the Traveling Car Renter. It is linearized and implemented on a solver providing optimal solutions to a set of eighteen small instances. Large instances are tackled with a transgenetic algorithm proposed here. A computational experiment is reported on sixty instances and the proposed algorithm is compared to a memetic algorithm presented previously. The computational experiment aimed at focusing on the differences of performance between the two heuristic algorithms due to the search strategy used by each of them. Therefore, the implementation of both methods shared several elements. The results show that the transgenetic algorithm presents the best performance, indicating that its cooperative evolutionary process was more effective on the investigated problem than the competitive scheme of the memetic algorithm.     

A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows

In this paper, we present an effective memetic algorithm for the vehicle routing problem with time windows (VRPTW). The paper builds upon an existing edge assembly crossover (EAX) developed for the capacitated VRP. The adjustments of the EAX operator and the introduction of a novel penalty function to eliminate violations of the time window constraint as well as the capacity constraint from offspring solutions generated by the EAX operator have proven essential to the heuristic's performance. Experimental results on Solomon's and Gehring and Homberger benchmarks demonstrate that our algorithm outperforms previous approaches and is able to improve 184 best-known solutions out of 356 instances.     

Bacterial memetic algorithm for simultaneous optimization of path planning and flow shop scheduling problems

The paper deals with simultaneous optimization of path planning of mobile robots and flow shop scheduling problem. The goal of the path planning problem is to determine an optimal collision-free path between a start and a target point for a mobile robot in an environment surrounded by obstacles. The objective is to minimize the path length without colliding with an obstacle. On the other hand, shop scheduling problems deal with processing a given set of jobs on a given number of machines. Each operation has an associated machine on which it has to be processed for a given length of time. The problem is to minimize the overall time demand of the whole process. In this paper, we deal with two robots carrying items between the machines. Bacterial memetic algorithm is proposed for solving this combined problem. The algorithm is verified by experimental simulations and compared to classical techniques.     

A memetic algorithm for the generalized traveling salesman problem

The generalized traveling salesman problem (GTSP) is an extension of the well-known traveling salesman problem. In GTSP, we are given a partition of cities into groups and we are required to find a minimum length tour that includes exactly one city from each group. The recent studies on this subject consider different variations of a memetic algorithm approach to the GTSP. The aim of this paper is to present a new memetic algorithm for GTSP with a powerful local search procedure. The experiments show that the proposed algorithm clearly outperforms all of the known heuristics with respect to both solution quality and running time. While the other memetic algorithms were designed only for the symmetric GTSP, our algorithm can solve both symmetric and asymmetric instances.     

Memetic algorithms based on local search chains for large scale continuous optimisation problems: MA-SSW-Chains

Nowadays, large scale optimisation problems arise as a very interesting field of research, because they appear in many real-world problems (bio-computing, data mining, etc.). Thus, scalability becomes an essential requirement for modern optimisation algorithms. In a previous work, we presented memetic algorithms based on local search chains. Local search chain concerns the idea that, at one stage, the local search operator may continue the operation of a previous invocation, starting from the final configuration reached by this one. Using this technique, it was presented a memetic algorithm, MA-CMA-Chains, using the CMA-ES algorithm as its local search component. This proposal obtained very good results for continuous optimisation problems, in particular with medium-size (with up to dimension 50). Unfortunately, CMA-ES scalability is restricted by several costly operations, thus MA-CMA-Chains could not be successfully applied to large scale problems. In this article we study the scalability of memetic algorithms based on local search chains, creating memetic algorithms with different local search methods and comparing them, considering both the error values and the processing cost. We also propose a variation of Solis Wets method, that we call Subgrouping Solis Wets algorithm. This local search method explores, at each step of the algorithm, only a random subset of the variables. This subset changes after a certain number of evaluations. Finally, we propose a new memetic algorithm based on local search chains for high dimensionality, MA-SSW-Chains, using the Subgrouping Solis Wets’ algorithm as its local search method. This algorithm is compared with MA-CMA-Chains and different reference algorithms, and it is shown that the proposal is fairly scalable and it is statistically very competitive for high-dimensional problems.     

带时间窗的同时取送货车辆路径问题建模及模因求解算法

为解决逆向物流背景下的带时间窗的同时取送货车辆路径问题（VRPSPDTW）,根据实际情况建立了相应的车辆路径问题模型,并采用模因算法进行求解。在模型的求解过程中使用引导弹射搜索（GES）生成初始种群,在种群进化的过程中采用边界组合交叉（EAX）产生子代,并采用多种邻域结构对子代进行修复、教育,以提高解的质量和算法的搜索效率。通过在Wang和Chen测试数据集上与遗传算法（GA）、并行模拟退火（p-SA）算法、离散布谷鸟（DCS）算法进行比较,实验结果显示：在小规模算例进行求解时,所提算法全部取得了当前最优解;对标准规模算例进行求解时,所提算法使70%的算例更新或获取了当前最优解,获得的最优求解算例结果与当前最优解相比有超过5%的提升,充分验证了所提算法求解VRPSPDTW的良好性能。     

Memetic algorithm with Preferential Local Search using adaptive weights for multi-objective optimization problems

Evolutionary multi-objective optimization algorithms are generally employed to generate Pareto optimal solutions by exploring the search space. To enhance the performance, exploration by global search can be complemented with exploitation by combining it with local search. In this paper, we address the issues in integrating local search with global search such as: how to select individuals for local search; how deep the local search is performed; how to combine multiple objectives into single objective for local search. We introduce a Preferential Local Search mechanism to fine tune the global optimal solutions further and an adaptive weight mechanism for combining multi-objectives together. These ideas have been integrated into NSGA-II to arrive at a new memetic algorithm for solving multi-objective optimization problems. The proposed algorithm has been applied on a set of constrained and unconstrained multi-objective benchmark test suite. The performance was analyzed by computing different metrics such as Generational distance, Spread, Max spread, and HyperVolume Ratio for the test suite functions. Statistical test applied on the results obtained suggests that the proposed algorithm outperforms the state-of-art multi-objective algorithms like NSGA-II and SPEA2. To study the performance of our algorithm on a real-world application, Economic Emission Load Dispatch was also taken up for validation. The performance was studied with the help of measures such as Hypervolume and Set Coverage Metrics. Experimental results substantiate that our algorithm has the capability to solve real-world problems like Economic Emission Load Dispatch and is able to produce better solutions, when compared with NSGA-II, SPEA2, and traditional memetic algorithms with fixed local search steps.     

A Memetic Approach to the Nurse Rostering Problem

Constructing timetables of work for personnel in healthcare institutions is known to be a highly constrained and difficult problem to solve. In this paper, we discuss a commercial system, together with the model it uses, for this rostering problem. We show that tabu search heuristics can be made effective, particularly for obtaining reasonably good solutions quickly for smaller rostering problems. We discuss the robustness issues, which arise in practice, for tabu search heuristics. This paper introduces a range of new memetic approaches for the problem, which use a steepest descent improvement heuristic within a genetic algorithm framework. We provide empirical evidence to demonstrate the best features of a memetic algorithm for the rostering problem, particularly the nature of an effective recombination operator, and show that these memetic approaches can handle initialisation parameters and a range of instances more robustly than tabu search algorithms, at the expense of longer solution times. Having presented tabu search and memetic approaches (both with benefits and drawbacks) we finally present an algorithm that is a hybrid of both approaches. This technique produces better solutions than either of the earlier approaches and it is relatively unaffected by initialisation and parameter changes, combining some of the best features of each approach to create a hybrid which is greater than the sum of its component algorithms.     

Adaptive memetic algorithm for minimizing distance in the vehicle routing problem with time windows

This paper presents an adaptive memetic algorithm to solve the vehicle routing problem with time windows (VRPTW). It is a well-known NP-hard discrete optimization problem with two objectives—to minimize the number of vehicles serving a set of geographically dispersed customers, and to minimize the total distance traveled in the routing plan. Although memetic algorithms have been proven to be extremely efficient in solving the VRPTW, their main drawback is an unclear tuning of their numerous parameters. Here, we introduce the adaptive memetic algorithm (AMA-VRPTW) for minimizing the total travel distance. In AMA-VRPTW, a population of solutions evolves with time. The parameters of the algorithm, including the selection scheme, population size and the number of child solutions generated for each pair of parents, are adjusted dynamically during the search. We propose a new adaptive selection scheme to balance the exploration and exploitation of the solution space. Extensive experimental study performed on the well-known Solomon’s and Gehring and Homberger’s benchmark sets confirms the efficacy and convergence capabilities of the proposed AMA-VRPTW. We show that it is very competitive compared with other state-of-the-art techniques. Finally, the influence of the proposed adaptive schemes on the AMA-VRPTW behavior and performance is investigated in a thorough sensitivity analysis. This analysis is complemented with the two-tailed Wilcoxon test for verifying the statistical significance of the results.     

A spy search mechanism for memetic algorithm in dynamic environments

Searching within the sample space for optimal solutions is an important part in solving optimization problems. The motivation of this work is that today’s problem environments have increasingly become dynamic with non-stationary optima and in order to improve optima search, memetic algorithm has become a preferred search method because it combines global and local search methods to obtain good solutions. The challenge is that existing search methods perform the search during the iterations without being guided by solid information about the nature of the search environment which affects the quality of a search outcome. In this paper, a spy search mechanism is proposed for memetic algorithm in dynamic environments. The method uses a spy individual to scope out the search environment and collect information for guiding the search. The method combines hyper-mutation, random immigrants, hill climbing local search, crowding and fitness, and steepest mutation with greedy crossover hill climbing to enhance the efficiency of the search. The proposed method is tested on dynamic problems and comparisons with other methods indicate a better performance by the proposed method.     

A memetic algorithm for the travelling salesperson problem with hotel selection

In this paper, a metaheuristic solution procedure for the travelling salesperson problem with hotel selection (TSPHS) is presented. The metaheuristic consists of a memetic algorithm with an embedded tabu search, using a combination of well-known and problem-specific neighbourhoods. This solution procedure clearly outperforms the only other existing metaheuristic in the literature. For smaller instances, whose optimal solution is known, it is able to consistently find the optimal solution. For the other instances, it obtains several new best known solutions.     

A memetic algorithm for the capacitated location-routing problem with mixed backhauls

The design of distribution networks is one of the most important problems in supply chain and logistics management. The main elements in designing a distribution network are location and routing decisions. As these elements are interdependent in many distribution networks, the overall system cost can decrease if location and routing decisions are simultaneously tackled. In this paper, we consider a Capacitated Location-Routing Problem with Mixed Backhauls (CLRPMB) which is a general case of the capacitated location-routing problem. CLRPMB is defined as finding locations of the depots and designing vehicle routes in such a way that pickup and delivery demands of each customer must be performed with the same vehicle and the overall cost is minimized. Since CLRPMB is an NP-hard problem, we propose a memetic algorithm to solve the problem. To evaluate the performance of the proposed approach, we conduct an experimental study and compare its results with the lower bounds obtained by the branch-and-cut algorithm on a set of instances derived from the literature. Computational results indicate that the proposed approach is able to find optimal or very good quality solutions in a reasonable computation time.     

A branch and bound algorithm for minimizing makespan on a single machine with unequal release times under learning effect and deteriorating jobs

We present a single-machine problem with the unequal release times under learning effect and deteriorating jobs when the objective is minimizing the makespan. In this study, we introduced a scheduling model with unequal release times in which both job deterioration and learning exist simultaneously. By the effects of learning and deterioration, we mean that the processing time of a job is defined by increasing function of its execution start time and position in the sequence. A branch-and-bound algorithm incorporating with several dominance properties and lower bounds is developed to derive the optimal solution. A heuristic algorithm is proposed to obtain a near-optimal solution. The computational experiments show that the branch-and-bound algorithm can solve instances up to 30 jobs, and the average error percentage of the proposed heuristic is less than 0.16%.