Search

In this paper we present two algorithms for a machine allocation problem occurring in manufacturing systems. For the two algorithms presented we prove worst-case performance ratios of 2 and 3/2, respectively. The machine allocation problem we consider is a general convex resource allocation problem, which makes the algorithms applicable to a variety of resource allocation problems. Numerical results are presented for two real-life manufacturing systems.

In Chapter 3, we have analyzed the iteration complexity of finding an ϵ-optimal solution, if an interior, sufficiently centered pair of primal and dual solutions is known beforehand. We will see in this chapter how we can adapt the algorithms of Chapter 3 to solve semidefinite programming problems without any pre-knowledge. To this end, we use the self-dual embedding technique. This technique will also be used to tackle semidefinite programming problems that may be unbounded, unsolvable, or infeasible.

Modern solvers for linear and quadratic programming often incorporate some variant of the primal-dual path-following method, which is a class of interior point methods. This method turns out to be suited for solving semidefinite programming problems as well. In this chapter, we propose a framework for analyzing primal-dual path-following algorithms for semidefinite programming. Our framework is a direct extension of the v-space approach, which was developed by Kojima et al. [63] in the context of complementarity problems.

This article is a continuation of the paper "Inventory Control and Regenerative processes: Theory" (Bazsa et al.; 1998) and presents closed form expressions for Laplace transforms associated with the cost functions of the classical single item inventory models with indivisible items, a fixed lead time and backlogging. For given instances of these inventory control models these Laplace transforms will be used as input functions in a newly developed Laplace transform inversion algorithm (Iseger; A new method for inverting Laplace transforms; 1998) which yields highly accurate computational results of the associated cost functions.