Constructive heuristic algorithms for the open shop problem

In this paper we consider constructive heuristic algorithms for the open shop problem with minimization of the schedule length. By means of investigations of the structure of a feasible solution two types of heuristic algorithms are developed: construction of a rank-minimal schedule by solving successively weighted maximum cardinality matching problems and construction of an approximate schedule by applying insertion techniques combined with beam search. All presented algorithms are tested on benchmark problems from the literature. Our computational results demonstrate the excellent solution quality of our insertion algorithm, especially for greater job and machine numbers. For 29 of 30 benchmark problems with at least 10 jobs and 10 machines we improve the best known values obtained by tabu search.     

Distributed algorithms for covering, packing and maximum weighted matching

This paper gives poly-logarithmic-round, distributed δ-approximation algorithms for covering problems with submodular cost and monotone covering constraints (Submodular-cost Covering). The approximation ratio δ is the maximum number of variables in any constraint. Special cases include Covering Mixed Integer Linear Programs (CMIP), and Weighted Vertex Cover (with δ = 2). Via duality, the paper also gives poly-logarithmic-round, distributed δ-approximation algorithms for Fractional Packing linear programs (where δ is the maximum number of constraints in which any variable occurs), and for Max Weighted c-Matching in hypergraphs (where δ is the maximum size of any of the hyperedges; for graphs δ = 2). The paper also gives parallel (RNC) 2-approximation algorithms for CMIP with two variables per constraint and Weighted Vertex Cover. The algorithms are randomized. All of the approximation ratios exactly match those of comparable centralized algorithms.     

Solving the maximal covering location problem with heuristic concentration

The metaheuristic heuristic concentration (HC) is applied here to the solution of large instances of the maximal covering location problem with high percentage coverage. In these instances, exact methods may be too cumbersome for practical use, and heuristics can allow faster solution times with near-optimal results. We examined the performance of HC based on its ability to approach the optimal solutions to these problems and the run times of the algorithm compared to LP-IP runtimes. Exact solutions, generated by linear programming and branch and bound, provided a benchmark for comparison when the LP-IP problems could be run to completion. In all cases, HC found solutions with objective values no worse than 0.543% below the best known LP-IP objective value. In several instances, LP-IP runtime ballooned to as much as 38.5 h, while HC took no longer than 1.6 h in any instance. In one particular instance, LP-IP took 38.5 h to terminate, while HC found a near-optimal solution (within 0.306% of optimality) in only 25 min. Furthermore, in 62.5% of the runs, the second stage of HC improved on the first stage 1-opt algorithm.     

Efficient primal-dual heuristic for a dynamic location problem

In this paper the dynamic location problem with opening, closure and reopening of facilities is formulated and an efficient primal-dual heuristic that computes both upper and lower limits to its optimal solution is described. The problem here studied considers the possibility of reconfiguring any location more than once over the planning horizon. This problem is NP-hard (the simple plant location problem is a special case of the problem studied). A primal-dual heuristic based on the work of Erlenkotter [A dual-based procedure for uncapacitated facility location. Operations Research 1978;26:992–1009] and Van Roy and Erlenkotter [A dual-based procedure for dynamic facility location. Management Science 1982;28:1091–105] was developed and tested over a set of randomly generated test problems. The results obtained are quite good, both in terms of the quality of lower and upper bounds calculated as in terms of the computational time spent by the heuristic. A branch-and-bound procedure that enables to optimize the problem is also described and tested over the same set of randomly generated problems.     

Two methods of ordering the covering elements for the solution of the set covering problem

Two set-covering algorithms are proposed and proved, one selecting and ordering the covering candidates by degrees and the other using lexicographic ordering.Translated from Kibernetika, No. 4, pp. 70–74, July–August, 1989.     

MSC问题的一类表面DNA解法

利用基于表面的DNA粘贴模型求解最小集合覆盖问题。改进体现在计算模版表面穷举了所有可能的结果,同一时间验证结果是否满足条件,真正实现了DNA的强大并行性。同时在互补的寡聚核苷酸片段发生退火反应时,利用特殊的化学反应,通过催化剂来决定是否杂交,减少了人工参与,提高了计算效率。通过计算机仿真模拟验证了模型的可行性。     

Implementation analysis of efficient heuristic algorithms for the traveling salesman problem

The state-of-the-art of local search heuristics for the traveling salesman problem (TSP) is chiefly based on algorithms using the classical Lin–Kernighan (LK) procedure and the stem-and-cycle (S&C) ejection chain method. Critical aspects of implementing these algorithms efficiently and effectively rely on taking advantage of special data structures and on maintaining appropriate candidate lists to store and update potentially available moves. We report the outcomes of an extensive series of tests on problems ranging from 1000 to 1,000,000 nodes, showing that by intelligently exploiting elements of data structures and candidate lists routinely included in state-of-the-art TSP solution software, the S&C algorithm clearly outperforms all implementations of the LK procedure. Moreover, these outcomes are achieved without the use of special tuning and implementation tricks that are incorporated into the leading versions of the LK procedure to enhance their computational efficiency.     

Exact and heuristic algorithms for the interval data robust assignment problem

We consider the Assignment Problem with interval data, where it is assumed that only upper and lower bounds are known for each cost coefficient. It is required to find a minmax regret assignment. The problem is known to be strongly NP-hard. We present and compare computationally several exact and heuristic methods, including Benders decomposition, using CPLEX, a variable depth neighborhood local search, and two hybrid population-based heuristics. We report results of extensive computational experiments.     

A tabu-search based heuristic for the hub covering problem over incomplete hub networks

Hub location problems deal with finding the location of hub facilities and with the allocation of demand nodes to these located hub facilities. In this paper, we study the single allocation hub covering problem over incomplete hub networks and propose an integer programming formulation to this end. The aim of our model is to find the location of hubs, the hub links to be established between the located hubs, and the allocation of non-hub nodes to the located hub nodes such that the travel time between any origin–destination pair is within a given time bound. We present an efficient heuristic based on tabu search and test the performance of our heuristic on the CAB data set and on the Turkish network.     

Efficient approximation algorithms for the routing open shop problem

We consider the routing open shop problem being a generalization of two classical discrete optimization problems: the open shop scheduling problem and the metric traveling salesman problem. The jobs are located at nodes of some transportation network, and the machines travel on the network to execute the jobs in the open shop environment. The machines are initially located at the same node (depot) and must return to the depot after completing all the jobs. It is required to find a non-preemptive schedule with the minimum makespan. The problem is NP-hard even on the two-node network with two machines. We present new polynomial-time approximation algorithms with worst-case performance guarantees.     

The minimum weighted covering location problem with distance constraints

The objective is to locate undesirable facilities on a network so as to minimize the total demand covered subject to the condition that no two facilities are allowed to be closer than a pre-specified distance. We prove that there exists a dominating location set and that it is a challenging problem to determine the consistency of the distance constraints. We compare several different mathematical formulations to solve the problem. Heuristics with computational experiments are provided.     

Fast algorithms for the dominating set problem on permutation graphs

AnO(n log logn) (resp.O(n² log² n)) algorithm is presented to solve the minimum cardinality (resp. weight) dominating set problem on permutation graphs, assuming the input is a permutation. The best-known previous algorithm was given by FÄrber and Keil, where they use dynamic programming to get anO(n² (resp.O(n³)) algorithm. Our improvement is based on the following three factors: (1) an observation on the order among the intermediate terms in the dynamic programming, (2) a new construction formula for the intermediate terms, and (3) efficient data structures for manipulating these terms.This research was supported in part by the National Science Foundation under Grant CCR-8905415 to Northwestern University.     

New ideas for applying ant colony optimization to the set covering problem

The set covering problem (SCP) is a well known NP-hard problem with many practical applications. In this research, a new approach based on ant colony optimization (ACO) is proposed to solve the SCP. The main differences between it and the existing ACO-based approaches lie in three aspects. First, it adopts a novel method, called single-row-oriented method, to construct solutions. When choosing a new column, it first randomly selects an uncovered row and only considers the columns covering this row, rather than all the unselected columns as candidate solution components. Second, a kind of dynamic heuristic information is used in this approach. It takes into account Lagrangian dual information associated with currently uncovered rows. Finally, a simple local search procedure is developed to improve solutions constructed by ants while keeping their feasibility. The proposed algorithm has been tested on a number of benchmark instances. Computational results show that it is able to produce competitive solutions in comparison with other metaheuristics.     

A GRASP algorithm to solve the unicost set covering problem

The set covering problem (SCP) is a well-known combinatorial optimization problem. This paper presents a GRASP algorithm to solve a special SCP case known in the literature as the unicost set covering problem. The algorithm incorporates a local improvement procedure based on the heuristics to solve binary constraint satisfiability problems (SAT). The quality of the proposed algorithm is tested on a set of reference instances, comparing the obtained results with those found in the literature. Our algorithm improves the best-known solutions for many of these instances.     

A dynamic programming algorithm for tree-like weighted set packing problem

In hierarchical organizations, hierarchical structures naturally correspond to nested sets. That is, we have a collection of sets such that for any two sets, either one of them is a subset of the other, or they are disjoint. In other words, a nested set system forms a hierarchy in the form of a tree structure. The task assignment problem on such hierarchical organizations is a real life problem. In this paper, we introduce the tree-like weighted set packing problem, which is a weighted set packing problem restricted to sets forming tree-like hierarchical structure. We propose a dynamic programming algorithm with cubic time complexity.     

A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem

In this paper, we study the job shop scheduling problem with the objective of minimizing the total weighted tardiness. We propose a hybrid shifting bottleneck-tabu search (SB-TS) algorithm by replacing the re-optimization step in the shifting bottleneck (SB) algorithm by a tabu search (TS). In terms of the shifting bottleneck heuristic, the proposed tabu search optimizes the total weighted tardiness for partial schedules in which some machines are currently assumed to have infinite capacity. In the context of tabu search, the shifting bottleneck heuristic features a long-term memory which helps to diversify the local search. We exploit this synergy to develop a state-of-the-art algorithm for the job shop total weighted tardiness problem (JS-TWT). The computational effectiveness of the algorithm is demonstrated on standard benchmark instances from the literature.