Best position algorithms for efficient top-k query processing

The general problem of answering top-k queries can be modeled using lists of data items sorted by their local scores. The main algorithm proposed so far for answering top-k queries over sorted lists is the Threshold Algorithm (TA). However, TA may still incur a lot of useless accesses to the lists. In this paper, we propose two algorithms that are much more efficient than TA. First, we propose the best position algorithm (BPA). For any database instance (i.e. set of sorted lists), we prove that BPA stops as early as TA, and that its execution cost is never higher than TA. We show that there are databases over which BPA executes top-k queries O(m) times faster than that of TA, where m is the number of lists. We also show that the execution cost of our algorithm can be (m−1) times lower than that of TA. Second, we propose the BPA2 algorithm, which is much more efficient than BPA. We show that the number of accesses to the lists done by BPA2 can be about (m−1) times lower than that of BPA. We evaluated the performance of our algorithms through extensive experimental tests. The results show that over our test databases, BPA and BPA2 achieve significant performance gains in comparison with TA.     

An exact algorithm for minimum distortion embedding

Let G be an unweighted connected graph on n vertices. We show that an embedding of the shortest path metric of G into the line with minimum distortion can be found in time 5^n+o(n). This is the first algorithm breaking the trivial n!-barrier.     

Available-to-promise based bidding decision by fuzzy mathematical programming and genetic algorithm

The present study attempts to integrate bidding decisions with order promising and production planning to enhance supplier profitability and service level. This study formulates the bid price and production plan as a mixed integer programming model with fuzzy constraints. The fuzzy constraints represent the decision-maker’s subjective judgment regarding the customer’s price tolerance. The proposed model combines the advanced available-to-promise (AATP) concept to find optimum resource allocation and enable accurate estimations of production costs and delivery dates. The proposed solution procedure determines the optimum bid price by striking a compromise between profitability and the possibility to win the contract. This study develops a genetic algorithm to solve this problem, and provides computer simulated experiments to evaluate the performance of the proposed approach.     

Estimation of distribution algorithm for permutation flow shops with total flowtime minimization

In this paper, an Estimation of Distribution Algorithm (EDA) is proposed for permutation flow shops to minimize total flowtime. Longest Common Subsequence (LCS) is incorporated into the probability distribution model to mine good “genes”. Different from common EDAs, each offspring individual is produced from a seed, which is selected from the population by the roulette method. The LCS between the seed individual and the best solution found so far is regarded as good “genes”, which are inherited by offspring with a probability less than 100% to guarantee the population diversity. An effective Variable Neighborhood Search (VNS) is integrated into the proposed EDA to further improve the performance. Experimental results show that the inheritance of good “genes” obtained by LCS can improve the performance of the proposed EDA. The proposed hybrid EDA outperforms other existing algorithms for the considered problem in the literature. Furthermore, the proposed hybrid EDA improved 42 out of 90 current best solutions for Taillard benchmark instances.     

Bi-objective scheduling for reentrant hybrid flow shop using Pareto genetic algorithm

This paper deals with a scheduling problem for reentrant hybrid flowshop with serial stages where each stage consists of identical parallel machines. In a reentrant flowshop, a job may revisit any stage several times. Local-search based Pareto genetic algorithms with Minkowski distance-based crossover operator is proposed to approximate the Pareto optimal solutions for the minimization of makespan and total tardiness in a reentrant hybrid flowshop. The Pareto genetic algorithms are compared with existing multi-objective genetic algorithm, NSGA-II in terms of the convergence to optimal solution, the diversity of solution and the dominance of solution. Experimental results show that the proposed crossover operator and local search are effective and the proposed algorithm outperforms NSGA-II by statistical analysis.     

Multi-objective FMS process planning with various flexibilities using a symbiotic evolutionary algorithm

This paper presents an evolutionary algorithm, called the multi-objective symbiotic evolutionary algorithm (MOSEA), to solve a multi-objective FMS process planning (MFPP) problem with various flexibilities. The MFPP problem simultaneously considers four types of flexibilities related to machine, tool, sequence, and process and takes into account three objectives: balancing the machine workload, minimizing part movements, and minimizing tool changes. The MOSEA is modeled as a two-leveled structure to find a set of well-distributed solutions close to the true Pareto optimal solutions. To promote the search capability of such solutions, two main processes imitating symbiotic evolution and endosymbiotic evolution are introduced, together with an elitist strategy and a fitness sharing scheme. Evolutionary components suitable for the MFPP problem are provided. With a variety of test-bed problems, the performance of the proposed MOSEA is compared with those of existing multi-objective evolutionary algorithms. The experimental results show that the MOSEA is promising in solution convergence and diversity.     

Combined planning and scheduling in a divergent production system with co-production: A case study in the lumber industry

Many research initiatives carried out in production management consider process planning and operations scheduling as two separate and sequential functions. However, in certain contexts, the two functions must be better integrated. This is the case in divergent production systems with co-production (i.e. production of different products at the same time from a single product input) when alternative production processes are available. This paper studies such a context and focuses on the case of drying and finishing operations in a softwood lumber facility. The situation is addressed using a single model that simultaneously performs process planning and scheduling. We evaluate two alternative formulations. The first one is based on mixed integer programming (MIP) and the second on constraint programming (CP). We also propose a search procedure to improve the performance of the CP approach. Both approaches are compared with respect to their capacity to generate good solutions in short computation time.     

Numerical inversions of a source term in the FADE with a Dirichlet boundary condition using final observations

This paper deals with an inverse problem of determining a source term in the one-dimensional fractional advection-dispersion equation (FADE) with a Dirichlet boundary condition on a finite domain, using final observations. On the basis of the shifted Grünwald formula, a finite difference scheme for the forward problem of the FADE is given, by means of which the source magnitude depending upon the space variable is reconstructed numerically by applying an optimal perturbation regularization algorithm. Numerical inversions with noisy data are carried out for the unknowns taking three functional forms: polynomials, trigonometric functions and index functions. The reconstruction results show that the inversion algorithm is efficient for the inverse problem of determining source terms in a FADE, and the algorithm is also stable for additional data having random noises.     

Shortest path problem with uncertain arc lengths

Uncertainty theory provides a new tool to deal with the shortest path problem with nondeterministic arc lengths. With help from the operational law of uncertainty theory, this paper gives the uncertainty distribution of the shortest path length. Also, it investigates solutions to the α-shortest path and the most shortest path in an uncertain network. It points out that there exists an equivalence relation between the α-shortest path in an uncertain network and the shortest path in a corresponding deterministic network, which leads to an effective algorithm to find the α-shortest path and the most shortest path. Roughly speaking, this algorithm can be broken down into two parts: constructing a deterministic network and then invoking the Dijkstra algorithm.