Multi‐mode resource‐constrained project scheduling using modified variable neighborhood search heuristic

This paper aims at providing a fast near‐optimum solution to the multi‐mode resource‐constrained project scheduling problems (MRCPSPs), for projects with activities that have known deterministic renewable and nonrenewable resource requirements. The MRCPSP is known to be nondeterministic polynomial‐time hard and has been solved using various exact, heuristic, and meta‐heuristic procedures. In this paper, a modified variable neighborhood search heuristic algorithm is used as an advanced optimization technique that suits scheduling problems. For the experimental study, we have considered a standard set of 3929 multi‐mode benchmark instances from the project scheduling library with a range of projects comprising 10–30 activities. Moreover, for a better comparison, this research also considers a standard set of 4320 newly developed multi‐mode instances from MMLIB50, MMLIB100, and MMLIB+ datasets. With the limit of 50,000 schedules on these datasets, our proposed algorithm provides better makespan for 106, 34, and 1601 instances, respectively, which justifies the efficiency of the proposed algorithm, particularly for projects with a larger number of activities. The results reported in this paper can be used as a benchmark for other researchers to compare and improve.     

基于禁忌搜索的启发式算法求解球体Packing问题*

为求解具有NP难度的球体Packing问题,通过将禁忌搜索方法与基于自适应步长的梯度下降法和二分法相结合,提出了一个启发式算法。对50个等球算例进行了实例测试,算法改进了其中44个算例的目前最优结果。大量的实例计算结果表明,该启发式算法是求解球体Packing问题的一个有效算法。     

Flow shop scheduling with blocking using modified harmony search algorithm with neighboring heuristics methods

The flow shop scheduling with blocking is considered an important scheduling problem which has many real-world applications. This paper proposes a new algorithm which applies heuristic techniques in harmony search algorithm (HSA) to minimize the total flow time. The proposed method is called modified harmony search algorithm with neighboring heuristics methods (MHSNH). To improve the initial harmony memory, we apply two heuristic techniques: nearest neighbor (NN) and constructive modified NEH (MNEH). A modified version of harmony search algorithm evolves to explore and generates a new solution. The newly generated solution is then enhanced by using neighboring heuristics. Lastly, another neighboring heuristic is applied to improve the obtained solution. The proposed algorithm is evaluated using 12 real-world problem instances each with 10 samples. The experimental evaluation is accomplished using two factors: CPU computational time and the number of iterations. For the first factor, comparative evaluation against six well-established methods shows that the proposed method achieves almost the best overall results in six problem instances out of the twelve and yields fruitful results for others. For the second factor, comparative evaluation against twelve well-regarded methods shows that the proposed method achieves the best overall results in three problem instances and obtains very good results in other instances. In a nutshell, the proposed MHSNH is an effective strategy for solving the job shop scheduling problem.     

A Best-first Branch-and-bound Algorithm for Orthogonal Rectangular Packing Problems

In this paper we discuss the problem of packing a set of small rectangles (pieces) in an enclosing final rectangle. We present first a best-first branch-and-bound exact algorithm and second a heuristic approach in order to solve exactly and approximately this problem. The performances of the proposed approaches are evaluated on several randomly generated problem instances. Computational results show that the proposed exact algorithm is able to solve small and medium problem instances within reasonable execution time. The derived heuristic performs very well in the sense that it produces high-quality solutions within small computational time.     

Efficient algorithms for real-life instances of the variable size bin packing problem

In this paper we present a local search heuristic for real-life instances of the variable size bin packing problem, and an exact algorithm for small instances. One important issue our heuristic is able to satisfy is that solutions must be delivered within (milli)seconds and that the solution methods should be robust to last minute changes in the data. Furthermore we show that we are able to incorporate the concept of usable leftovers on a single bin, and the implementation of many additional constraints should be supported by the straightforward solution representation. The heuristic is compared to others from the literature, and comes out ahead on a large subset of the instances.     

An enhanced beam search algorithm for the Shortest Common Supersequence Problem

The Shortest Common Supersequence Problem asks to obtain a shortest string that is a supersequence of every member of a given set of strings. It has applications, among others, in data compression and oligonucleotide microarray production. The problem is NP-hard, and the existing exact solutions are impractical for large instances. In this paper, a new beam search algorithm is proposed for the problem, which employs a probabilistic heuristic and uses the dominance property to further prune the search space. The proposed algorithm is compared with three recent algorithms proposed for the problem on both random and biological sequences, outperforming them all by quickly providing solutions of higher average quality in all the experimental cases. The Java source and binary files of the proposed IBS_SCS algorithm and our implementation of the DR algorithm and all the random and real datasets used in this paper are freely available upon request.     

正三角形容器内等圆Packing问题的启发式算法

等圆Packing问题研究如何将n个单位半径的圆形物体互不嵌入地置入一个边长尽量小的正三角形容器内,作为一类经典的NP难度问题,其有着重要的理论价值和广泛的应用背景.模拟退火算法是一种随机的全局寻优算法,通过将启发式格局更新策略与基于梯度法的局部搜索策略融入模拟退火算法,并与二分搜索相结合,提出一种求解正三角形容器内等圆Packing问题的启发式算法.该算法将启发式格局更新策略用来产生新格局和跳坑,用梯度法搜索新产生格局附近能量更低的格局,并用二分搜索得到正三角形容器的最小边长.对41个算例进行测试的实验结果表明,文中算法改进了其中38个实例的目前最优结果,是求解正三角形容器内等圆Packing问题的一种有效算法.     

An extended Akers graphical method with a biased random‐key genetic algorithm for job‐shop scheduling

This paper presents a local search, based on a new neighborhood for the job‐shop scheduling problem, and its application within a biased random‐key genetic algorithm. Schedules are constructed by decoding the chromosome supplied by the genetic algorithm with a procedure that generates active schedules. After an initial schedule is obtained, a local search heuristic, based on an extension of the 1956 graphical method of Akers, is applied to improve the solution. The new heuristic is tested on a set of 205 standard instances taken from the job‐shop scheduling literature and compared with results obtained by other approaches. The new algorithm improved the best‐known solution values for 57 instances.     

Multiobjective heuristic search in road maps

This article considers the application of exact multiobjective techniques to search in large size realistic road maps. In particular, the NAMOA^∗ algorithm is successfully applied to several road networks from the DIMACS shortest path implementation challenge with two objectives. An efficient heuristic function previously proposed by Tung and Chew is evaluated. Heuristic values are precalculated with search. The precalculation effort is shown to pay off during the multiobjective search stage. An improvement to the calculation procedure is also proposed, resulting in added improved time performance in many problem instances.     

Branch-and-Bound-Based Local Search Heuristics for Train Timetabling on Single-Track Railway Network

The modified formulation and two branch-and-bound-based local search heuristic algorithms for train timetabling in single-track railway network in the planning application are proposed. The original local search heuristic is modified such that when a neighbor of a currently tested resolved conflict for improvement is evaluated, the depth-first search branch-and-bound algorithm is employed with two branching rules: least-lower-bound and least-delay-time. The detailed implementation of the proposed heuristic algorithms are described, including the neighborhood definitions of overtaking and crossing conflicts, the procedure to detect overtaking and crossing conflicts, and a recursive procedure for the depth-first search branch-and-bound algorithm. The proposed heuristic algorithms, the original heuristic, the equivalent manual solution method and the exact solution method are compared using a toy problem and four problems (26-train, 50-train, 76-train and 108-train) in the Thailand Southern line railway network, which consisted of 266 single-track segments, 15 double-track segments, 282 stations/sidings, and total distance of 1577 km. The proposed heuristic algorithm with the least-lower-bound branching rule outperforms the other heuristics in terms of the solution quality with up to 2.827 % improvement over the equivalent manual solution method and less than 8 % optimality gap. The proposed heuristic algorithms require longer time to terminate than the original heuristic. The proposed heuristic algorithm with the least-lower-bound branching rule converges faster than that with the least-delay-time branching rule in all test problems. Based on the empirical results, the proposed heuristic algorithms are solvable in polynomial time. Furthermore, the proposed heuristic algorithm with the least-lower-bound branching rule is enhanced by embedding a uniform sampling strategy, and it is found that the total CPU time can be saved by about 50 % with marginally worse solution quality.     

Exact algorithm and heuristic for the Closest String Problem

The Closest String Problem (CSP) is an NP-hard problem, which arises in computational molecular biology and coding theory. This class of problems is to find a string that minimizes the maximum Hamming distance to a given set of strings. In this paper, we present an exact algorithm called Distance First Algorithm (DFA) for three strings of CSP with alphabet size two. For the general CSP, we design a polynomial heuristic which is a combination of our proposed approximation algorithm LDDA ([10] Liu Xiaolan, Fu Keqiang, Shao Renxiang. Largest distance decreasing algorithm for the Closest String Problem. Journal of Information & Computational Science 2004; 1(2): 287–92) and local search strategies. Numerical results show that the proposed heuristic may obtain a nearly optimal value in a reasonable time for small and large-scale instances of the CSP.     

A beam-search-based constructive heuristic for the PFSP to minimise total flowtime

In this paper we present a beam-search-based constructive heuristic to solve the permutation flowshop scheduling problem with total flowtime minimisation as objective. This well-known problem is NP-hard, and several heuristics have been developed in the literature. The proposed algorithm is inspired in the logic of the beam search, although it remains a fast constructive heuristic.The results obtained by the proposed algorithm outperform those obtained by other constructive heuristics in the literature for the problem, thus modifying substantially the state-of-the-art of efficient approximate procedures for the problem. In addition, the proposed algorithm even outperforms two of the best metaheuristics for many instances of the problem, using much lesser computation effort. The excellent performance of the proposal is also proved by the fact that the new heuristic found new best upper bounds for 35 of the 120 instances in Taillard’s benchmark.     

A hybrid method for the Probabilistic Maximal Covering Location–Allocation Problem

This paper presents a hybrid algorithm that combines a metaheuristic and an exact method to solve the Probabilistic Maximal Covering Location–Allocation Problem. A linear programming formulation for the problem presents variables that can be partitioned into location and allocation decisions. This model is solved to optimality for small- and medium-size instances. To tackle larger instances, a flexible adaptive large neighborhood search heuristic was developed to obtain location solutions, whereas the allocation subproblems are solved to optimality. An improvement procedure based on an integer programming method is also applied. Extensive computational experiments on benchmark instances from the literature confirm the efficiency of the proposed method. The exact approach found new best solutions for 19 instances, proving the optimality for 18 of them. The hybrid method performed consistently, finding the best known solutions for 94.5% of the instances and 17 new best solutions (15 of them optimal) for a larger dataset in one-third of the time of a state-of-the-art solver.     

Heuristic and exact algorithms for product configuration in software product lines

Software product line (SPL) is a set of software applications that share a common set of features satisfying the specific needs of a particular market segment. SPL engineering is a paradigm to develop software applications that commonly use a feature model to capture and document common and variable features, and their relationships. A big challenge is to derive one product among all possible products in the SPL, which satisfies the business and customer requirements. This task is known as product configuration. Although product configuration has been extensively investigated in the literature, customer's preferences are frequently neglected. In this paper, we propose a novel approach to configure a product that considers both qualitative and quantitative feature properties. We model the product configuration task as a combinatorial optimization problem, and heuristic and exact algorithms are proposed. As far as we are concerned, this proposal is the first work in the literature that considers feature properties in both leaf and nonleaf features. Computational experiments showed that the best of our heuristics found optimal solutions for all instances where those are known. For the instances where optimal solutions are not known, our heuristic outperformed the best solution obtained by a one‐hour run of the exact algorithm by up to 67.89%.     

一种多目标不等面积设施布局问题的启发式算法

多目标不等面积设施布局问题（UA-FLP）是将一些不等面积设施放置在车间内进行布局,要求优化多个目标并满足一定的限制条件。以物料搬运成本最小和非物流关系强度最大来建立生产车间的多目标优化模型,并提出一种启发式算法进行求解。算法采用启发式布局更新策略更新构型,通过结合基于自适应步长梯度法的局部搜索机制和启发式设施变形策略来处理设施之间的干涉性约束。为了得到问题的Pareto最优解集,提出了基于Pareto优化的局部搜索和基于小生境技术的全局优化方法。通过两个典型算例对算法性能进行测试,实验结果表明,所提出的启发式算法是求解多目标UA-FLP的有效方法。     

An improved scatter search algorithm for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times

In this paper, a scatter search algorithm with improved component modules is proposed to solve the single machine total weighted tardiness problem with sequence-dependent setup times. For diversification generation module, both random strategy based heuristics and construction heuristic are adopted to generate the diversified population. For improvement module, variable neighborhood search based local searches are embedded into the algorithm to improve the trial solutions and the combined solutions. For reference set update module, the number of edges by which the two solutions differ from each other is counted to measure the diversification value between two solutions. We also propose a new strategy in which the length of the reference set could be adjusted adaptively to balance the computing time and solving ability. In addition, a discrete differential evolution operator is proposed with another two operators constitute the combination module to generate the new trial solutions with the solutions in the subsets. The proposed algorithm is tested on the 120 benchmark instances from the literature. Computational results indicate that the average relative percentage deviations of the improved algorithm from the ACO_AP, DPSO, DDE and GVNS are −5.16%, −3.33%, −1.81% and −0.08%, respectively. Comparing with the state-of-the-art and exact algorithms, the proposed algorithm can obtain 78 optimal solutions out of 120 instances within a reasonable computational time.     

An asynchronous genetic local search algorithm for the permutation flowshop scheduling problem with total flowtime minimization

In this study, the permutation flowshop scheduling problem with the total flowtime criterion is considered. An asynchronous genetic local search algorithm (AGA) is proposed to deal with this problem. The AGA consists of three phases. In the first phase, an individual in the initial population is yielded by an effective constructive heuristic and the others are randomly generated, while in the second phase all pairs of individuals perform the asynchronous evolution (AE) where an enhanced variable neighborhood search (E-VNS) as well as a simple crossover operator is used. A restart mechanism is applied in the last phase. Our experimental results show that the algorithm proposed outperforms several state-of-the-art methods and two recently proposed meta-heuristics in both solution quality and computation time. Moreover, for 120 benchmark instances, AGA obtains 118 best solutions reported in the literature and 83 of which are newly improved.     

Effective three-phase evolutionary algorithm to handle the large-scale colorful traveling salesman problem

This paper proposes a novel evolutionary algorithm to handle the colorful traveling salesman problem. The proposed evolutionary algorithm is a three-phase algorithm and utilizes two types of a new crossover and an enhanced local search. In the first phase, quality of population is increased by applying the first crossover. After the first phase, a priority value is computed to each color, based on the best tour of the first phase. During the second phase, priority values are updated when a solution with better cost than existing solutions in population is found. Priority values are used by the second type of crossover, which is used in the second phase. After the second phase, the problem is converted to the classical traveling salesman problem ingeniously, and finally, the third phase is a hybrid genetic algorithm, for which an enhanced local search algorithm is applied. Applying the second type of crossover and updating priority values are continued in the third phase. The proposed algorithm is effective and finds new bounds for many large-scale instances and outperforms other state-of-the-art heuristic in terms of accuracy and speed. In many cases, gaps between results obtained by the proposed algorithm and the other methods are high. For some large-scale instances, proposed algorithm is 44 times faster than the other state-of-the-art competitor, which is the current most efficient algorithm.     

A robust two-phase heuristic algorithm for the truck scheduling problem in a resource-constrained crossdock

This paper studies truck scheduling in a resource-constrained crossdock. The problem decides on the sequence of incoming and outgoing trucks at the dock doors of the crossdocking terminal, subject to the availability of crossdock resources including dock doors and material handling systems. The resources are assumed non-preemptive making it necessary to address the feasibility of the problem before its optimality as it might be entrapped in deadlock and no feasible solution is produced. The paper thus aims at developing an algorithmic approach capable of establishing solution feasibility for truck scheduling problem instances of various types and difficulty levels which at the same time can be readily implemented in an industrial setting. The proposed approach is a two-phase heuristic algorithm where in the first phase, a heuristic search is deployed to construct a feasible sequence of trucks for the assignment to dock doors and in the second, a rule-based heuristic is used to assign each sequenced truck to a proper dock door, subject to a limited number of forklifts, such that significant savings in the truck schedule length are achieved. Extensive experiments are conducted to evaluate the efficiency of the algorithm in terms of deadlock avoidance and solution quality. The evaluation is carried out against the solutions generated by the exact mathematical model of the problem and a constructive heuristic developed for a similar truck scheduling problem. Experimental results demonstrate that the proposed algorithm is robust in avoiding deadlock and generates feasible solutions for the instances where the other two approaches cannot. Furthermore, significant improvement in the solution quality is achieved by augmenting the algorithm to a re-starting heuristic.