The Selective Fixing Algorithm for the closest string problem

A hybrid heuristic algorithm based on integer linear programming is proposed for the closest string problem (CSP). The algorithm takes a rough feasible solution in input and iteratively selects variables to be fixed at their initial value until the number of free variables is small enough for the remaining problem to be solved to optimality by an ILP solver. The new solution can then be used as input for another iteration of the algorithm and this approach is repeated a predefined number of times. The procedure is denoted as Selective Fixing Algorithm (SFA). SFA has first been tested on standard instances available from the literature, which is denoted as rectangular having string length larger than the number of strings. Then, this approach has also been tested on the so-called square instances (having string length equal to the number of strings) and rectangular inverse instances (having string length smaller than the number of strings). Computational experiments indicate that SFA globally outperforms the state-of-the-art heuristics.     

Solving the bi-objective personnel assignment problem using particle swarm optimization

A particle swarm optimization (PSO) algorithm combined with the random-key (RK) encoding scheme (named as PSORK) for solving a bi-objective personnel assignment problem (BOPAP) is presented. The main contribution of this work is to improve the f₁_f₂ heuristic algorithm which was proposed by Huang et al. [3]. The objective of the f₁_f₂ heuristic algorithm is to get a satisfaction level (SL) value which is satisfied to the bi-objective values f₁, and f₂ for the personnel assignment problem. In this paper, PSORK algorithm searches the solution of BOPAP space thoroughly. The experimental results show that the solution quality of BOPAP based on the proposed method is far better than that of the f₁_f₂ heuristic algorithm.     

A heuristic algorithm based on Lagrangian relaxation for the closest string problem

The closest string problem that arises in both computational biology and coding theory is to find a string minimizing the maximum Hamming distance from a given set of strings. This study proposes an efficient heuristic algorithm for this NP-hard problem. The key idea is to apply the Lagrangian relaxation technique to the problem formulated as a mixed-integer programming problem. This enables us to decompose the problem into trivial subproblems corresponding to each position of the strings. Furthermore, a feasible solution can be easily obtained from a solution of the relaxation. Based on this, a heuristic algorithm is constructed by combining a Lagrangian multiplier adjustment procedure and a tabu search. Computational experiments will show that the proposed algorithm can find good approximate solutions very fast.     

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 GRASP algorithm for the Closest String Problem using a probability-based heuristic

The Closest String Problem (CSP) is the problem of finding a string whose Hamming distance from the members of a given set of strings of the same length is minimal. It has applications, among others, in bioinformatics and in coding theory. Several approximation and (meta)heuristic algorithms have been proposed for the problem to achieve ‘good’ but not necessarily optimal solutions within a reasonable time. In this paper, a new algorithm for the problem is proposed, based on a Greedy Randomized Adaptive Search Procedure (GRASP) and a novel probabilistic heuristic function. The algorithm is compared with three recently proposed algorithms for CSP, outperforming all of them by achieving solutions of higher quality within a few seconds in most of the experimental cases.     

Two-machine flowshop scheduling with bicriteria problem

This paper attempts to solve a two-machine flowshop bicriteria scheduling problem with release dates for the jobs, in which the objective function is to minimize a weighed sum of total flow time and makespan. To tackle this scheduling problem, an integer programming model with N²+3N variables and 5N constraints where N is the number of jobs, is formulated. Because of the lengthy computing time and high computing complexity of the integer programming model, a heuristic scheduling algorithm is presented. Experimental results show that the proposed heuristic algorithm can solve this problem rapidly and accurately. The average solution quality of the heuristic algorithm is above 99% and is much better than that of the SPT rule as a benchmark. A 15-job case requires only 0.018 s, on average, to obtain an ultimate or even optimal solution. The heuristic scheduling algorithm is a more practical approach to real world applications than the integer programming model.     

A network-based approach to the multi-activity combined timetabling and crew scheduling problem: Workforce scheduling for public health policy implementation

This paper introduces the multi-activity combined timetabling and crew scheduling problem. The goal of this problem is to schedule the minimum number of workers required in order to successfully visit a set of customers characterized by services needed matched against schedule availability. Two solution strategies are proposed. The first is based on mathematical programming whilst the second uses a heuristic procedure in order to reduce computational time. The proposed model combines timetabling with crew scheduling decisions in one mixed integer programming model which considers multiple activities. The algorithms are tested on randomly generated and real instances provided by the Health to School Initiative, a program based at Bogotá’s local Health Department. The results show that the Initiative can increase its coverage by up to 68% using the proposed heuristic approach as a planning process tool.     

A parallel multistart algorithm for the closest string problem

In this paper we describe and implement a parallel algorithm to find approximate solutions for the Closest String Problem (CSP). The CSP, also known as Motif Finding problem, has applications in Coding Theory and Computational Biology. The CSP is NP-hard which motivates us to think about heuristics to solve large instances. Several approximation algorithms have been designed for the CSP, but all of them have a poor performance guarantee. Recently some researchers have shown empirically that integer programming techniques can be successfully used to solve moderate-size instances (10–30 strings each of which is 300–800 characters long) of the CSP. However, real-world instances are larger than those tested. In this paper we show how a simple heuristic can be used to find near-optimal solutions to that problem. We implemented a parallel version of this heuristic and report computational experiments on large-scale instances. These results show the effectiveness of our approach.     

Makespan minimization on single batch-processing machine via ant colony optimization

This paper investigates the problem of minimizing makespan on a single batch-processing machine, and the machine can process multiple jobs simultaneously. Each job is characterized by release time, processing time, and job size. We established a mixed integer programming model and proposed a valid lower bound for this problem. By introducing a definition of waste and idle space (WIS), this problem is proven to be equivalent to minimizing the WIS for the schedule. Since the problem is NP-hard, we proposed a heuristic and an ant colony optimization (ACO) algorithm based on the theorems presented. A candidate list strategy and a new method to construct heuristic information were introduced for the ACO approach to achieve a satisfactory solution in a reasonable computational time. Through extensive computational experiments, appropriate ACO parameter values were chosen and the effectiveness of the proposed algorithms was evaluated by solution quality and run time. The results showed that the ACO algorithm combined with the candidate list was more robust and consistently outperformed genetic algorithm (GA), CPLEX, and the other two heuristics, especially for large job instances.     

An effective GRASP and tabu search for the 0–1 quadratic knapsack problem

As a generalization of the classical 0-1 knapsack problem, the 0-1 Quadratic Knapsack Problem (QKP) that maximizes a quadratic objective function subject to a linear capacity constraint is NP-hard in strong sense. In this paper, we propose a memory based Greedy Randomized Adaptive Search Procedures (GRASP) and a tabu search algorithm to find near optimal solution for the QKP. Computational experiments on benchmarks and on randomly generated instances demonstrate the effectiveness and the efficiency of the proposed algorithms, which outperforms the current state-of-the-art heuristic Mini-Swarm in computational time and in the probability to achieve optimal solutions. Numerical results on large-sized instances with up to 2000 binary variables have also been reported.     

An adaptive amoeba algorithm for constrained shortest paths

The constrained shortest path problem (CSP) is one of the basic network optimization problems, which plays an important part in real applications. In this paper, an adaptive amoeba algorithm is combined with the Lagrangian relaxation algorithm to solve the CSP problem. The proposed method is divided into two steps: (1) the adaptive amoeba algorithm is modified to solve the shortest path problem (SPP) in a directed network; (2) the modified adaptive amoeba algorithm is combined with the Lagrangian relaxation method to solve the CSP problem. In addition, the evolving processes of the adaptive amoeba model have been detailed in the paper. Two examples are used to illustrate the efficiency of the proposed method. The results show that the proposed method can deal with the CSP problem effectively.     

Solution approaches for the cutting stock problem with setup cost

In this paper, we study the Cutting Stock Problem with Setup Cost (CSP-S) which is a more general case of the well-known Cutting Stock Problem (CSP). In the classical CSP, one wants to minimize the number of stock items used while satisfying the demand for smaller-sized items. However, the number of patterns/setups to be performed on the cutting machine is ignored. In most cases, one has to find the trade-off between the material usage and the number of setups in order to come up with better production plans. In CSP-S, we have different cost factors for the material and the number of setups, and the objective is to minimize total production cost including both material and setup costs. We develop a mixed integer linear program and analyze a special case of the problem. Motivated by this special case, we propose two local search algorithms and a column generation based heuristic algorithm. We demonstrate the effectiveness of the proposed algorithms on the instances from the literature.     

求解加权圆集布局问题的快速启发式搜索算法

加权圆集布局问题是基于性能驱动的一类布局问题,由于其NP-hard属性,难以在多项式时间内求解,提出一种快速启发式搜索算法。权矩阵的行向量1范数作为首次赌轮选择圆的启发信息,依次以权矩阵的当前行（其行号等于当前选择圆的序号）元素作为下次赌轮选择的启发信息,利用图形学理论给出低计算复杂度的定位规则,进而基于该定序定位规则提出一种启发式搜索算法,以求得该问题的最优解。数值实验表明,该算法的性能优于已有算法。     

Beam search for the longest common subsequence problem

The longest common subsequence problem is a classical string problem that concerns finding the common part of a set of strings. It has several important applications, for example, pattern recognition or computational biology. Most research efforts up to now have focused on solving this problem optimally. In comparison, only few works exist dealing with heuristic approaches. In this work we present a deterministic beam search algorithm. The results show that our algorithm outperforms the current state-of-the-art approaches not only in solution quality but often also in computation time.     

Heuristic search for scheduling flexible manufacturing systems using lower bound reachability matrix

For scheduling flexible manufacturing systems efficiently, we propose new heuristic functions for A^* algorithm that is based on the T-timed Petri net. In minimizing makespan, the proposed heuristic functions are usually more efficient than the previous functions in the required number of states and computation time. We prove that these heuristic functions are all admissible and one of them is more informed than that using resource cost reachability matrix. We also propose improved versions of these heuristic functions that find a first near-optimal solution faster. In addition, we modify the heuristic function of Yu, Reyes, Cang, and Lloyd (2003b) and propose an admissible version in all states. The experimental results using a random problem generator show that the proposed heuristic functions perform better as we expected.     

Effect of solution representations on Tabu search in scheduling applications

This research investigates the application of meta-heuristic algorithms to a scheduling problem called permutation manufacturing-cell flow shop (PMFS) from two perspectives. First, we examine the effect of using different solution representations (S_new and S_old) while applying Tabu-search algorithm. Experimental results reveal that Tabu_S_new outperforms Tabu_S_old. The rationale why Tabu_S_new is superior is further examined by characterizing the intermediate outcomes of the evolutionary processes in these two algorithms. We find that the superiority of S_new is due to its relatively higher degree of freedom in modeling Tabu neighborhood. Second, we propose a new algorithm GA_Tabu_S_new, which empirically outperforms the state-of-the-art meta-heuristic algorithms in solving the PMFS problem. This research highlights the importance of solution representation in the application of meta-heuristic algorithm, and establishes a significant milestone in solving the PMFS problem.     

Rapid Physarum Algorithm for shortest path problem

As shortest path (SP) problem has been one of the most fundamental network optimization problems for a long time, technologies for this problem are still being studied. In this paper, a new method by integrating a path finding mathematical model, inspired by Physarum polycephalum, with extracted one heuristic rule to solve SP problem has been proposed, which is called Rapid Physarum Algorithm (RPA). Simulation experiments have been carried out on three different network topologies with varying number of nodes. It is noted that the proposed RPA can find the optimal path as the path finding model does for most networks. What is more, experimental results show that the performance of RPA surpasses the path finding model on both iterations and solution time.     

An incomplete m-exchange algorithm for solving the large-scale multi-scenario knapsack problem

This paper introduces a fast heuristic based algorithm for the max-min multi-scenario knapsack problem. The problem is a variation of the standard 0-1 knapsack problem, in which the profits of the items vary under different scenarios, though the capacity of the knapsack is fixed. The objective of the problem is to find the optimal packing of a set of items so that the minimum total profits of the items in the knapsack over all different scenarios is maximized. For some large-scaled instances, traditional branch-and-bound techniques cannot find an optimal solution within reasonable time, thus we propose a collection of incomplete m-exchange algorithms which are able to produce high quality solutions in just a few minutes of cpu time. Various computational results are also given.     

一类最优交通小区划分问题的一阶邻接约束建模方法

提出一种使用邻接矩阵保证最优交通小区划分一阶邻接约束的整数规划建模方法。从求解复杂度和质量两个角度,比较并分析了该邻接约束建模方法与其他3种方法对问题求解效率的影响。设计了聚合式层次聚类启发算法以求解所提出的模型。针对较大规模算例,将所提出的建模方法与其他3种邻接约束建模方法的结果进行了对比与分析。结果表明,基于邻接矩阵表示的建模方法能在允许时间内求得满意解,较其他3种方法更适合大规模问题。     

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.