The Heuristic Approach to movement optimization on single-track part of the railway net
This paper represents our solution for the problem of movement organization based on timetable optimization on the problematic part of railway system, i.e. single-track line. The approximate solution of this problem was founded on the heuristic method. The method gives the exact results in the case of limited amount of parameters and also can be used in the case with huge number of parameters due to reasonable computational time.
In this note, we consider a single machine scheduling problem with generalized total tardiness objective function. A pseudo-polynomial time solution algorithm is proposed for a special case of this problem. Moreover, we present a new graphical algorithm for another special case, which corresponds to the classical problem of minimizing the weighted number of tardy jobs on a single machine. The latter algorithm improves the complexity of an existing pseudo-polynomial algorithm by Lawler. Computational results are presented for both special cases considered.
Global Equilibrium Search (GES) is a meta-heuristic framework that shares similar ideas with the simulated annealing method. GES accumulates a compact set of information about the search space to generate promising initial solutions for the techniques that require a starting solution, such as the simple local search method. GES has been successful for many classic discrete optimization problems: the unconstrained quadratic programming problem, the maximum satisfiability problem, the max-cut problem, the multidimensional knapsack problem and the job-shop scheduling problem. GES provides state-of-the-art performance on all of these domains when compared to the current best known algorithms from the literature. GES algorithm can be naturally extended for parallel computing as it performs search simultaneously in distinct areas of the solution space. In this talk, we provide an overview of Global Equilibrium Search and discuss some successful applications.
This book constitutes the proceedings of the 9th International Conference on Discrete Optimization and Operations Research, DOOR 2016, held in Vladivostok, Russia, in September 2016.
The 39 full papers presented in this volume were carefully reviewed and selected from 181 submissions. They were organized in topical sections named: discrete optimization; scheduling problems; facility location; mathematical programming; mathematical economics and games; applications of operational research; and short communications.
A railway connection of two stations by a single railway track is usually found on branch lines of railway network and is very common in various manufacturing supply chains. Our paper isДля книг на иностранных языках concerned with a scheduling problem for two stations with a single railway track with one siding. On single-track railway sidings or passing loops are used to increase the capacity of the line. In our paper we developed exact optimization algorithm by analysing the structure of optimal schedule for the proposed model. The algorithm produces a schedule that completes all transportations between two stations at minimal time. We present algorithm to construct an optimal schedule in O(1) operations. Optimal schedule analyse allows the development of exact optimization algorithms with other models and objective functions, i.e. results can be generalized and used in future work for a number of regular objective functions, commonly used in scheduling.
We discuss a model for image segmentation that is able to overcome the short-boundary bias observed in standard pairwise random field based approaches. To wit, we show that a random field with multi-layered hidden units can encode boundary preserving higher order potentials such as the ones used in the cooperative cuts model of  while still allowing for fast and exact MAP inference. Exact inference allows our model to outperform previous image segmentation methods, and to see the true effect of coupling graph edges. Finally, our model can be easily extended to handle segmentation instances with multiple labels, for which it yields promising results.
In this paper, we consider some scheduling problems on a single machine, where weighted or unweighted total tardiness has to be maximized in contrast to usual minimization problems. These problems are theoretically important and have also practical interpretations. For the weighted tardiness maximization problem, we present an NP-hardness proof and a pseudo-polynomial solution algorithm. For the unweighted total tardiness maximization problem with release dates, NP-hardness is proven. Complexity results for some other classical objective functions (e.g., the number of tardy jobs, total completion time) and various additional constraints (e.g., deadlines, weights and/or release dates of jobs may be given) are presented as well.