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.     

Search strategy for scheduling flexible manufacturing systems simultaneously using admissible heuristic functions and nonadmissible heuristic functions

To scheduling flexible manufacturing system (FMS) efficiently, we propose and evaluate an improved search strategy and its application to FMS scheduling in the P-timed Petri net framework. On the execution of Petri net, the proposed method can simultaneously use admissible heuristic functions and nonadmissible heuristic functions for A^* algorithm. We also prove that the resulting combinational heuristic function is still admissible and more informed than any of its constituents. The experimental results of an example FMS and several sets of random generated problems show that the proposed search method performs better as we expected.     

Branch-and-bound method for minimizing the weighted completion time scheduling problem on a single machine with release dates

In this paper, we consider a single-machine scheduling problem with release dates. The aim is to minimize the total weighted completion time. This problem is known to be strongly NP-hard. We propose two new lower bounds that can be, respectively, computed in O(n²) and in O(nlogn) time where n is the number of jobs. We prove a sufficient and necessary condition for local optimality, which can also be considered as a priority rule. We present an efficient heuristic using such a condition. We also propose some dominance properties. A branch-and-bound algorithm incorporating the heuristic, the lower bounds and the dominance properties is proposed and tested on a large set of instances.     

Heuristics for planning with penalties and rewards formulated in logic and computed through circuits

The automatic derivation of heuristic functions for guiding the search for plans is a fundamental technique in planning. The type of heuristics that have been considered so far, however, deal only with simple planning models where costs are associated with actions but not with states. In this work we address this limitation by formulating a more expressive planning model and a corresponding heuristic where preferences in the form of penalties and rewards are associated with fluents as well. The heuristic, that is a generalization of the well-known delete-relaxation heuristic, is admissible, informative, but intractable. Exploiting a correspondence between heuristics and preferred models, and a property of formulas compiled in d-DNNF, we show however that if a suitable relaxation of the domain, expressed as the strong completion of a logic program with no time indices or horizon is compiled into d-DNNF, the heuristic can be computed for any search state in time that is linear in the size of the compiled representation. This representation defines an evaluation network or circuit that maps states into heuristic values in linear-time. While this circuit may have exponential size in the worst case, as for OBDDs, this is not necessarily so. We report empirical results, discuss the application of the framework in settings where there are no goals but just preferences, and illustrate the versatility of the account by developing a new heuristic that overcomes limitations of delete-based relaxations through the use of valid but implicit plan constraints. In particular, for the Traveling Salesman Problem, the new heuristic captures the exact cost while the delete-relaxation heuristic, which is also exponential in the worst case, captures only the Minimum Spanning Tree lower bound.     

A unified approach to ranking in probabilistic databases

Ranking is a fundamental operation in data analysis and decision support and plays an even more crucial role if the dataset being explored exhibits uncertainty. This has led to much work in understanding how to rank the tuples in a probabilistic dataset in recent years. In this article, we present a unified approach to ranking and top-k query processing in probabilistic databases by viewing it as a multi-criterion optimization problem and by deriving a set of features that capture the key properties of a probabilistic dataset that dictate the ranked result. We contend that a single, specific ranking function may not suffice for probabilistic databases, and we instead propose two parameterized ranking functions, called PRF ^ω and PRF ^e, that generalize or can approximate many of the previously proposed ranking functions. We present novel generating functions-based algorithms for efficiently ranking large datasets according to these ranking functions, even if the datasets exhibit complex correlations modeled using probabilistic and/xor trees or Markov networks. We further propose that the parameters of the ranking function be learned from user preferences, and we develop an approach to learn those parameters. Finally, we present a comprehensive experimental study that illustrates the effectiveness of our parameterized ranking functions, especially PRF ^e, at approximating other ranking functions and the scalability of our proposed algorithms for exact or approximate ranking.     

Disjoint pattern database heuristics

We describe a new technique for designing more accurate admissible heuristic evaluation functions, based on pattern databases [J. Culberson, J. Schaeffer, Comput. Intelligence 14 (3) (1998) 318–334]. While many heuristics, such as Manhattan distance, compute the cost of solving individual subgoals independently, pattern databases consider the cost of solving multiple subgoals simultaneously. Existing work on pattern databases allows combining values from different pattern databases by taking their maximum. If the subgoals can be divided into disjoint subsets so that each operator only affects subgoals in one subset, then we can add the pattern-database values for each subset, resulting in a more accurate admissible heuristic function. We used this technique to improve performance on the Fifteen Puzzle by a factor of over 2000, and to find optimal solutions to 50 random instances of the Twenty-Four Puzzle.     

Pruning by dominance in best-first search for the job shop Scheduling problem with total flow time

Best-First search is a problem solving paradigm that allows to design exact or admissible algorithms. In this paper, we confront the Job Shop Scheduling problem with total flow time minimization by means of the A ^* algorithm. We devised a heuristic from a problem relaxation that relies on computing Jackson’s preemptive schedules. In order to reduce the effective search space, we formalized a method for pruning nodes based on dominance relations and established a rule to apply this method efficiently during the search. By means of experimental study, we show that the proposed method is more efficient than a genetic algorithm in solving instances with 10 jobs and 5 machines and that pruning by dominance allows A ^* to reach optimal schedules, while these instances are not solved by A ^* otherwise. These experiments have also made it clear that the Job Shop Scheduling problem with total flow time minimization is harder to solve than the same problem with makespan minimization.     

Marking algorithm of distinguishing three traffic load states with two encoding states for pre-congestion notification

Pre-congestion notification (PCN) gives an early warning of congestion by marking packets to protect the quality of service of inelastic flows. PCN defines two rates per link: admissible rate (AR) and supportable rate (SR), which divide the PCN traffic load into three states, “no pre-congestion,” “AR pre-congestion,” and “SR pre-congestion.” PCN admission control and flow termination control operate in accordance with these three states. However, only two PCN encoding states, unmarked and PCN marked, can be used due to the requirement of PCN encoding to survive tunneling through a currently used IPsec tunnel. We propose a marking algorithm, which uses the two encoding states, for distinguishing the three states of PCN traffic load. We also propose new admission and flow termination controls, which are based on the proposed marking algorithm, and evaluate their performance. Markings that require fewer PCN encoding states are preferable because the remaining encoding state can be used for a newly added PCN-based control in the future. Furthermore, distinguishing more states with fewer encoding states benefits not only PCN but also general marking techniques because header fields are limited; thus, valuable.     

Duality in permutation state spaces and the dual search algorithm

Geometrical symmetries are commonly exploited to improve the efficiency of search algorithms. A new type of symmetry in permutation state spaces, duality, is introduced. Each state has a dual state. Both states share important attributes such as their distance to the goal. Given a state S, it is shown that an admissible heuristic of the dual state of S is an admissible heuristic for S. This provides opportunities for additional heuristic evaluations. An exact definition of the class of problems where duality exists is provided. A new search algorithm, dual search, is presented which switches between the original state and the dual state when it seems likely that the switch will improve the chance of reaching the goal faster. The decision of when to switch is very important and several policies for doing this are investigated. Experimental results show significant improvements for a number of applications, for using the dual state's heuristic evaluation and/or dual search.     

Testing restorable systems: formal definition and heuristic solution based on river formation dynamics

Given a finite state machine denoting the specification of a system, finding some short interaction sequences capable of reaching some/all states or transitions of this machine is a typical goal in testing methods. If these sequences are applied to an implementation under test, then equivalent states or transitions would be reached and observed in the implementation—provided that the implementation were actually defined as the specification. We study the problem of finding such sequences in the case where configurations previously traversed can be saved and restored (at some cost). In general, this feature enables sequences to reach the required parts of the machine in less time, because some repetitions can be avoided. However, we show that finding optimal sequences in this case is an NP-hard problem. We propose an heuristic method to approximately solve this problem based on an evolutionary computation approach, in particular river formation dynamics (RFD). Given finite state machine specifications and sets of states/transitions to be reached, we apply RFD to construct testing plans reaching these configurations. Experimental results show that being able to load previously traversed states generally reduces the time needed to cover the target configurations.     

An artificial immune system heuristic for two-stage multi-machine assembly scheduling problem to minimize total completion time

We address the two-stage multi-machine assembly scheduling problem. The first stage consists of m independently working machines where each machine produces its own component. The second stage consists of two independent and identical assembly machines. The objective is to come up with a schedule that minimizes total or mean completion time for all jobs. The problem has been addressed in the scheduling literature and several heuristics have been proposed. In this paper, we propose a new heuristic called artificial immune system (AIS). We conduct experimental analysis for comparing the newly proposed heuristic AIS with the best known heuristic in the literature. Experimental results show that our proposed heuristic AIS performs better than the best known existing heuristic. More specifically, our new heuristic AIS reduces the error of the best known heuristic by 60% while the computational times of both AIS and the best known heuristic are almost the same.     

The two-stage assembly scheduling problem to minimize total completion time with setup times

We address the two-stage assembly scheduling problem where there are m machines at the first stage and an assembly machine at the second stage. The objective is to schedule the available n jobs so that total completion time of all n jobs is minimized. Setup times are treated as separate from processing times. This problem is NP-hard, and therefore we present a dominance relation and propose three heuristics. The heuristics are evaluated based on randomly generated data. One of the proposed heuristics is known to be the best heuristic for the case of zero setup times while another heuristic is known to perform well for such problems. A new version of the latter heuristic, which utilizes the dominance relation, is proposed and shown to perform much better than the other two heuristics.     

An efficient method for maintaining data cubes incrementally

The data cube operator computes group-bys for all possible combinations of a set of dimension attributes. Since computing a data cube typically incurs a considerable cost, the data cube is often precomputed and stored as materialized views in data warehouses. A materialized data cube needs to be updated when the source relations are changed. The incremental maintenance of a data cube is to compute and propagate only its changes, rather than recompute the entire data cube from scratch. For n dimension attributes, the data cube consists of 2ⁿ group-bys, each of which is called a cuboid. To incrementally maintain a data cube with 2ⁿ cuboids, the conventional methods compute 2ⁿdelta cuboids, each of which represents the change of a cuboid. In this paper, we propose an efficient incremental maintenance method that can maintain a data cube using only a subset of 2ⁿ delta cuboids. We formulate an optimization problem to find the optimal subset of 2ⁿ delta cuboids that minimizes the total maintenance cost, and propose a heuristic solution that allows us to maintain a data cube using only delta cuboids. As a result, the cost of maintaining a data cube is substantially reduced. Through various experiments, we show the performance advantages of the proposed method over the conventional methods. We also extend the proposed method to handle partially materialized cubes and dimension hierarchies.     

Optimal admissible composition of abstraction heuristics

Additive ensembles of admissible heuristics constitute the most general form of exploiting the individual strengths of numerous admissible heuristics in optimal planning. However, the same set of heuristics can be additively composed in infinitely many ways and the quality of the resulting heuristic estimate depends directly on the choice of the composition. Focusing on abstraction heuristics, we describe a procedure that takes a deterministic planning problem, a forward-search state, and a set of abstraction-based admissible heuristics, and derives an optimal additive composition of these heuristics with respect to the given state. Most importantly, we show that this procedure is polynomial-time for arbitrary sets of all abstraction heuristics with which we are acquainted, including explicit abstractions such as pattern databases (regular or constrained) and merge-and-shrink, and implicit abstractions such as fork-decomposition and abstractions based on tractable constraint optimization over tree-shaped constraint networks.     

Improving Performance of Heterogeneous Agents

Agents provide services not only to humans users but also to agents in one or more multiagent systems. When agents are confronted with multiple tasks to perform (or requests to satisfy), the agent can reduce load on itself by attempting to take advantage of commonalities between the tasks that need to be performed. In this paper, we develop a logical theory by which such “heavily loaded” agents can merge commonalities amongst such tasks. In our framework, agents can be built on top of legacy codebases. We propose a logical formalism called invariants using which agent developers may specify known commonalities between tasks – after this, we propose a sound and complete mechanism to derive all possible derived commonalities. An obvious A ^*-based algorithm may be used to merge a set of tasks in a way that minimised expected execution cost. Unfortunately the execution time of this algorithm is prohibitive, even when only 10 tasks need to be merged, thus making it unusable in practice. We develop heuristic algorithms for this problem that take much less time to execute and produce almost as good ways of merging tasks.     

A heuristic search-based motion correspondence algorithm using fuzzy clustering

Motion correspondence problem between many feature points of consecutive frames is computationally explosive. We present a heuristic algorithm for finding out the most probable motion correspondence of points in consecutive frames, based on fuzzy confidence degrees. The proposed algorithm consists of three stages: (i) reduction of the search space for candidate points of association, (ii) pairwise association cost estimation and (iii) complete association of every feature point between the consecutive frames. In the first stage, all the points in a frame, frame t-1 are grouped into several groups by using fuzzy clustering. This is done with a Euclidean distance as a similarity measure between the points. The points in the following frame, frame t are also clustered into the same number of groups with respect to the cluster centers of the previous frame. The association between the points of the consecutive frames is allowed only for the points that belong to the same group in each frame. In the second stage, the cost of each association of a point in frame t-1 with a point in frame t is estimated by using motion constraints that are based on the velocity vector and the orientation angle of each point. The cost is measured as a fuzzy confidence degree of each head point, i.e., a point in frame t-1, belonging to each measurement, i.e., a point in frame t. In the final stage, we search for the most likely associations among all the possible mappings between the feature points in the consecutive frames. A search tree is constructed in such a way that an ith level node represents an association of ith node in frame t-1 with a node in frame t. We devise a heuristic function of an admissible A* algorithm by using the pairwise association cost developed in the second stage. Experimental results show an accuracy of more than 98%.     

Predicting optimal solution cost with conditional probabilities

Heuristic search algorithms are designed to return an optimal path from a start state to a goal state. They find the optimal solution cost as a side effect. However, there are applications in which all one wants to know is an estimate of the optimal solution cost. The actual path from start to goal is not initially needed. For instance, one might be interested in quickly assessing the monetary cost of a project for bidding purposes. In such cases only the cost of executing the project is required. The actual construction plan could be formulated later, after bidding. In this paper we propose an algorithm, named Solution Cost Predictor (SCP), that accurately and efficiently predicts the optimal solution cost of a problem instance without finding the actual solution. While SCP can be viewed as a heuristic function, it differs from a heuristic conceptually in that: 1) SCP is not required to be fast enough to guide search algorithms; 2) SCP is not required to be admissible; 3) our measure of effectiveness is the prediction accuracy, which is in contrast to the solution quality and number of nodes expanded used to measure the effectiveness of heuristic functions. We show empirically that SCP makes accurate predictions on several heuristic search benchmarks.     

Scheduling nonpreemptive jobs on parallel machines subject to exponential unrecoverable interruptions

In this paper we consider the problem of scheduling n independent jobs on m parallel machines. If, while a machine is processing a job, a failure (unrecoverable interruption) occurs, the current job as well as subsequently scheduled jobs on that machine cannot be performed, and hence do not contribute to the overall revenue or throughput. The objective is to maximize the expected amount of work done before an interruption occurs. In this paper, we investigate the problem when failures are exponentially distributed. We show that the problem is NP-hard, and characterize a polynomially solvable special case. We then propose both an exact algorithm having pseudopolynomial complexity and a heuristic algorithm. A combinatorial upper bound is also proposed for the problem. Experimental results show the effectiveness of the heuristic approach.     

A two-dimensional vector packing model for the efficient use of coil cassettes

We consider the problem of efficiently packing steel products, known as coils, into special containers, called cassettes for shipping. The objective is to minimize the number of cassettes used for packing all the given coils where each cassette has capacity limits on both total payload weight and size. We model this problem as a two-dimensional vector packing problem and propose a heuristic. We also analyze the worst-case performance of the proposed algorithm under a special condition which, in fact, holds for the particular real-world case that we handled. Our computational experiment with real production data shows that the proposed algorithm performs quite satisfactorily in practice.     

Finding optimal solutions to the graph partitioning problem with heuristic search

As search spaces become larger and as problems scale up, an efficient way to speed up the search is to use a more accurate heuristic function. A better heuristic function might be obtained by the following general idea. Many problems can be divided into a set of subproblems and subgoals that should be achieved. Interactions and conflicts between unsolved subgoals of the problem might provide useful knowledge which could be used to construct an informed heuristic function. In this paper we demonstrate this idea on the graph partitioning problem (GPP). We first show how to format GPP as a search problem and then introduce a sequence of admissible heuristic functions estimating the size of the optimal partition by looking into different interactions between vertices of the graph. We then optimally solve GPP with these heuristics. Experimental results show that our advanced heuristics achieve a speedup of up to a number of orders of magnitude. Finally, we experimentally compare our approach to other states of the art graph partitioning optimal solvers on a number of classes of graphs. The results obtained show that our algorithm outperforms them in many cases.