Journal:Informatica
Volume 20, Issue 2 (2009), pp. 203–216
Abstract
One of the most known applications of Discrete Optimization is on scheduling. In contrast, one of the most known applications of Continuous Nonlinear Optimization is on the control of dynamic systems. In this paper, we combine both views, solving scheduling problems as dynamic systems, modeled as discrete-time nonlinear optimal control problems with state and control continuous variables subjected to upper and lower bounds. Complementarity constraints are used to represent scheduling decisions. One example we discuss in detail is the crude oil scheduling in ports, with numerical results presented.
Journal:Informatica
Volume 17, Issue 2 (2006), pp. 279–296
Abstract
Given a set of objects with profits (any, even negative, numbers) assigned not only to separate objects but also to pairs of them, the unconstrained binary quadratic optimization problem consists in finding a subset of objects for which the overall profit is maximized. In this paper, an iterated tabu search algorithm for solving this problem is proposed. Computational results for problem instances of size up to 7000 variables (objects) are reported and comparisons with other up-to-date heuristic methods are provided.
Journal:Informatica
Volume 13, Issue 3 (2002), pp. 311–332
Abstract
Real life scheduling problems are solved by heuristics with parameters defined by experts, as usual. In this paper a new approach is proposed where the parameters of various heuristics and their random mixtures are optimized to reduce the average deviations from the global optimum.
In many cases the average deviation is a stochastic and multi-modal function of heuristic parameters. Thus a stochastic global optimization is needed. The Bayesian heuristic approach is developed and applied for this optimization. That is main distinctive feature of this work. The approach is illustrated by flow-shop and school scheduling examples. Two versions of school scheduling models are developed for both traditional and profiled schools. The models are tested while designing schedules for some Lithuanian schools. Quality of traditional schedules is defined by the number of teacher “windows”. Schedules of profiled schools are evaluated by user defined penalty functions. That separates clearly subjective and objective data. This is the second specific feature of the proposed approach.
The software is developed for the Internet environment and is used as a tool for research collaboration and distance graduate studies. The software is available at web-sites and can be ran by standard net browsers supporting Java language. The care is taken that interested persons could easily test the results and apply the algorithms and software for their own problems.
Journal:Informatica
Volume 11, Issue 2 (2000), pp. 145–162
Abstract
Many heuristics, such as simulated annealing, genetic algorithms, greedy randomized adaptive search procedures are stochastic. In this paper, we propose a deterministic heuristic algorithm, which is applied to the quadratic assignment problem. We refer this algorithm to as intensive search algorithm (or briefly intensive search). We tested our algorithm on the various instances from the library of the QAP instances – QAPLIB. The results obtained from the experiments show that the proposed algorithm appears superior, in many cases, to the well-known algorithm – simulated annealing.
Journal:Informatica
Volume 3, Issue 2 (1992), pp. 225–240
Abstract
In this paper, we present two heuristics for solving the unconstrained quadratic 0–1 programming problem. First heuristic realizes the steepest ascent from the centre of the hypercube, while the second constructs a series of solutions and chooses the best of them. In order to evaluate their worst-case behaviour We define the performance ratio K which uses the objective function value at the reference point x=1/2. We show for both heuristics that K is bounded by 1 from above and this bound is sharp. Finally, we report on the results of a computational study with proposed and local improvement heuristics.