Search

This paper deals with multicriteria discrete-continuous problems of scheduling nonpreemptable jobs. The need for reusability and modularity leads us to build a “generic” optimisation and simulation framework, while the need to quickly generate good compromises between conflicting objectives requires the implementation of multicriteria scheduling models. This paper describes the practical possibilities of three hybrid models within this framework. The validation of the framework is presented in terms of its application to a real, highly constrained, discrete-continuous problem. The optimisation model is based on the hybridisation of a classical hill-climber meta-heuristic with the Promethee II multicriteria method. [ABSTRACT FROM AUTHOR]

Conventional supervised learning in neural networks is carried out by performing unconstrained minimization of a suitably defined cost function. This approach has certain drawbacks, which can be overcome by incorporating additional knowledge in the training formalism. In this paper, two types of such additional knowledge are examined: Network specific knowledge (associated with the neural network irrespectively of the problem whose solution is sought) or problem specific knowledge (which helps to solve a specific learning task). A constrained optimization framework is introduced for incorporating these types of knowledge into the learning formalism. We present three examples of improvement in the learning behaviour of neural networks using additional knowledge in the context of our constrained optimization framework. The two network specific examples are designed to improve convergence and learning speed in the broad class of feedforward networks, while the third problem specific example is related to the efficient factorization of 2-D polynomials using suitably constructed sigma-pi networks. [ABSTRACT FROM AUTHOR]

This paper considers the problem of finding minimal length tree networks on the unit sphere Φ of a given point set (V) where distance is measured along great circular arcs. The related problems of finding a Steiner Minimal Tree SMT (V) and of finding a Minimum Spanning Tree MST(V) are treated through a simplicial decomposition technique based on computing the Delaunay Triangulation DT (V) and the Voronoi Diagram VD(V) of the given point set. O (N log N) algorithms for computing DT(V), VD(V), and WST(V) as well as an O(N log N) heuristic for finding a sub-optimal SMT(V) solution are presented, together with experimental results for randomly distributed points on Φ. [ABSTRACT FROM AUTHOR]

Three possible approaches to stochastic programming problems defined in time (so that they contain random processes) are described in this paper: (1) an application of the extremal theory of random processes; (2) an exponential penalty model approach related to scenario analysis; (3) a modification of the entropic penalty approach. Explicit results are derived for some special cases. [ABSTRACT FROM AUTHOR]

The purpose of the paper is to give a survey of methods, partly derived by the author in joint work with other researchers, concerning the problem of constructing e-optimal strategies for partially observable MDPs. The methods basically consist in transforming the problem into one of approximation: Starting from the original problem a sequence of approximating problems is constructed such that: (i) For each approximating problem an optimal strategy can actually be computed, (ii) Given ϵ » 0, there exists an approximating problem such that the optimal strategy for the latter is ϵ-optimal for the original problem. [ABSTRACT FROM AUTHOR]

This paper concerns the problem of locating a central facility on a connected network N. The network, N, could be representative of a transport system, while the central facility takes the form of a connected subgraph of N. The problem is to locate a central facility of minimum length so that each of several demand points on N is covered by the central facility a demand point at vi in N is covered by the central facility if the shortest path distance between vi and the closest point in the central facility does not exceed a parameter ri. This location problem is NP-hard, but for certain special cases, efficient solution methods are available. [ABSTRACT FROM AUTHOR]

In this paper, two different decision models for the planning of highway pavement improvements are presented. In the first model, we want to get a prescribed improvement in the state of the highway network with minimal agency cost. In the second model, a given amount of money is distributed between the highway sections in different states in such a way that the achieved improvements should be the best in some sense. The first model helps the administration in the estimation of the necessary cost for the annual highway improvements. The second model in addition gives an objective tool to the administration for the distribution of the total amount of money between the different regions of the country. We present the construction of the models in detail. Both of them use Markov transition probabilities according to the states of the highway sections and produce a special structure, large-scale, linear programming problem. Some numerical results are presented on the data from Hungarian highways. [ABSTRACT FROM AUTHOR]

This paper presents a numerical method for solving quantile optimization problems, i.e. stochastic programming problems in which the quantile of the distribution of an objective function is the criterion to be optimized. [ABSTRACT FROM AUTHOR]

Uncertainty in the parameters of a mathematical program may present a modeller with considerable difficulties. Most approaches in the stochastic programming literature place an apparent heavy data and computational burden on the user and as such are often intractable. Moreover, the models themselves are difficult to understand. This probably explains why one seldom sees a fundamentally stochastic model being solved using stochastic programming techniques. Instead, it is common practice to solve a deterministic model with different assumed scenarios for the random coefficient. In this paper we present a simple approach to solving a stochastic model, based on a particular method for combining such scenario solutions into a single, feasible policy. The approach is computationally simple and easy to understand. Because of its generality, it can handle multiple competing objectives, complex stochastic constraints and may be applied in contexts other than optimization. To illustrate our model, we consider two distinct, important applications: the optimal management of a hydro-thermal generating system and an application taken from portfolio optimization. [ABSTRACT FROM AUTHOR]

In practical problem situations data are usually inherently unreliable. A mathematical representation of uncertainty leads to stochastic optimization problems. In this paper the complexity of stochastic combinatorial optimization problems is discussed. Surprisingly, certain stochastic versions of NP-hard deterministic combinatorial problems appear to be solvable in polynomial time. [ABSTRACT FROM AUTHOR]

In this work, we consider a complex flowshop scheduling problem in which both no-wait and separate setup times are considered. The optimisation criterion is the minimisation of the total completion time. We propose an effective dominance rule for the four machine case that can also be used for m machines. Five simple and fast heuristics are proposed along with two easy to code stochastic local search methods, one of them being based on Iterated Local Search (ILS). An extensive computational evaluation is carried out with two sets of 5,400 instances. All seven methods are compared to two recent algorithms. The results, confirmed by thorough statistical analyses, show that the proposed methods are more effective and efficient when compared to the best existing algorithms in the literature for the considered problem. [ABSTRACT FROM AUTHOR]

The article presents information on tabu search (TS), a mathematical optimization method. It mentions that a starting premise of TS is that intelligent inhibition plays a critical role in making effective use of memory. It is worth stressing that discoveries about effective uses of memory within the search methods may provide clues about strategies that humans are adept at employing.

Some developments in structure and stability of stochastic programs during the last decade together with interrelations to optimization theory and stochastics are reviewed. With weak convergence of probability measures as a backbone we discuss qualitative and quantitative stability of recourse models that possibly involve integer variables. We sketch stability in chance constrained stochastic programming and provide some applications in statistical estimation. Finally, an outlook is devoted to issues that were not discussed in detail and to some open problems. [ABSTRACT FROM AUTHOR]

We consider a complex system consisting of N identical components that are expected to function properly during a given period (mission time). Due to the possibility of failure before completion of the mission time, one allows for maintenance as well as bum-in, the latter in order to cope with the problem of ‘infant mortality’. We present a two-level (Bayesian) Dynamic Programming approach to determine the optimal timing of the maintenance interventions and durations of bum-in, including maintenance-induced bum-in. We also discuss ways to reduce the ‘curse of dimensionality’. [ABSTRACT FROM AUTHOR]

We study the on-line problem of assigning tasks to identical machines whose regular working time — assumed to be unitary — can be extended. If the tasks assigned to a machine do not exceed the regular working time, then the working time of the machine is considered to be 1; otherwise, it is the completion time of the last task assigned to the machine. Each incoming task has to be assigned immediately to a machine and the assignment cannot be changed later. The objective is to minimize the sum of the working times of the machines. Since the regular working time of the machines can be seen as a given capacity, the problem can also be described through the bin packing terminology: the machines are viewed as bins and the tasks as items. A lower bound of 7/6 on the worst-case relative error of any on-line algorithm is shown. Then it is shown that a list scheduling heuristic which assigns the incoming task to the machine with smallest current load has worst-case error equal to 5/4. The bound is improved to 1.228 by a new algorithm which tends to load the partially loaded machines, as long as this does not cause an increase of the working time by more than a fixed and appropriately chosen quantity x » 0. [ABSTRACT FROM AUTHOR]

The problem of interest is to partition a collection of machines into production cells so that a given set of part-manufacturing requirements may be carried out optimally. In the present case transitions of parts between different cells is the only measure of machine partition goodness. The present formulation and approximate solution of this optimization problem is best described as one of successive approximations or as a one-at-a-time method. An initial cellular structure is taken and an easy part assignment optimization routine executed. With the part assignment fixed, a heuristic is employed to find an improved cell structure. These bipartite iterations continue until a convergence criterion is satisfied. Several small computer examples are provided and the straightforward requirements for large problem adaptation. [ABSTRACT FROM AUTHOR]