We propose a method for the control of multi-class queueing networks over a finite time horizon. We approximate the multi-class queueing network by a fluid network and formulate a fluid optimization problem which we s...
详细信息
We propose a method for the control of multi-class queueing networks over a finite time horizon. We approximate the multi-class queueing network by a fluid network and formulate a fluid optimization problem which we solve as a separated continuouslinear program. The optimal fluid solution partitions the time horizon to intervals in which constant fluid flow rates are maintained. We then use a policy by which the queueing network tracks the fluid solution. To that end we model the deviations between the queuing and the fluid network in each of the intervals by a multi-class queueing network with some infinite virtual queues. We then keep these deviations stable by an adaptation of a maximum pressure policy. We show that this method is asymptotically optimal when the number of items that is processed and the processing speed increase. We illustrate these results through a simple example of a three stage re-entrant line.
We consider the separated continuous linear programming problem with linear data. We characterize the form of its optimal solution, and present an algorithm which solves it in a finite number of steps, using an analog...
详细信息
We consider the separated continuous linear programming problem with linear data. We characterize the form of its optimal solution, and present an algorithm which solves it in a finite number of steps, using an analog of the simplex method, in the space of bounded measurable functions.
This paper focuses on the continuous assignment problem with the eventual aim to solve scheduling problems with irregular cost functions. It consists of partitioning a region of R-d into subregions of prescribed volum...
详细信息
This paper focuses on the continuous assignment problem with the eventual aim to solve scheduling problems with irregular cost functions. It consists of partitioning a region of R-d into subregions of prescribed volumes so that the total cost is minimized. The dual problem of the continuous assignment problem is an unconstrained maximization of a non-smooth concave function. The preemptive variant of the scheduling problem with irregular cost functions corresponds to the one-dimensional continuous assignment problem and a lower bound for the non-preemptive variant can be derived. It is computationally tested in a branch-and-bound algorithm.
Separated continuouslinear programs (SCLP) are a class of continuouslinear programs which, among other things, can serve as a useful model for dynamic network problems where storage is permitted at the nodes. Recent...
详细信息
Separated continuouslinear programs (SCLP) are a class of continuouslinear programs which, among other things, can serve as a useful model for dynamic network problems where storage is permitted at the nodes. Recent work on SCLP has produced a detailed duality theory, conditions under which an optimal solution exists with a finite number of breakpoints, a purification algorithm, as well as a convergent algorithm for solving SCLP under certain assumptions on the problem data. This paper combines much of this work to develop a possible approach for solving a wider range of SCLP problems, namely those with fairly general costs. The techniques required to implement the algorithm are no more than standard (finite-dimensional) linearprogramming and line searching, and the resulting algorithm is simplex-like in nature. We conclude the paper with the numerical results obtained by using a simple implementation of the algorithm to solve a small problem.
Separated continuouslinear programs (SCLP) are type of infinite-dimensional linear program which can serve as useful model for variety of dynamic network problems where storage is permitted at the nodes. This paper p...
详细信息
Separated continuouslinear programs (SCLP) are type of infinite-dimensional linear program which can serve as useful model for variety of dynamic network problems where storage is permitted at the nodes. This paper proves the convergence of general class of algorithms for solving SCLP under certain restrictions on the problem data. This is the rst such proof for any nondiscretization algorithm for solving any form of continuouslinear programs.
In a fluid re-entrant line, fluid moves through a sequence of K buffers, partitioned by their service to I stations. We consider the initial fluid in the system, with no external input. Our objective is to empty all t...
详细信息
In a fluid re-entrant line, fluid moves through a sequence of K buffers, partitioned by their service to I stations. We consider the initial fluid in the system, with no external input. Our objective is to empty all the fluid in the line with minimum total inventory. We present a polynomial time algorithm for this problem, for the case I = 2.
作者：
Luo, XDBertsimas, DMIT
Alfred P Sloan Sch Management Cambridge MA 02139 USA MIT
Ctr Operat Res Cambridge MA 02139 USA
During the last few decades, significant progress has been made in solving large-scale finite-dimensional and semi-infinite linearprogramming problems. In contrast, little progress has been made in solving linear pro...
详细信息
During the last few decades, significant progress has been made in solving large-scale finite-dimensional and semi-infinite linearprogramming problems. In contrast, little progress has been made in solving linear programs in infinite-dimensional spaces despite their importance as models in manufacturing and communication systems. Inspired by the research on separated continuouslinear programs, we propose a new class of continuous linear programming problems that has a variety of important applications in communications, manufacturing, and urban traffic control. This class of continuouslinear programs contains the separated continuouslinear programs as a subclass. Using ideas from quadratic programming, we propose an efficient algorithm for solving large-scale problems in this new class under mild assumptions on the form of the problem data. We prove algorithmically the absence of a duality gap for this class of problems without any boundedness assumptions on the solution set. We show this class of problems admits piecewise constant optimal control when the optimal solution exists. We give conditions for the existence of an optimal solution. We also report computational results which illustrate that the new algorithm is effective in solving large-scale realistic problems (with several hundred continuous variables) arising in manufacturing systems.
Dynamic network flow problems in which there is a delay on the flows in the arcs have been in existence since the early days of modern optimization. However, most previous work in this area has only considered models ...
详细信息
Dynamic network flow problems in which there is a delay on the flows in the arcs have been in existence since the early days of modern optimization. However, most previous work in this area has only considered models which are discrete in the time variable. In this paper we present a continuous-time model for a very broad class of dynamic network problems with are time-delays. The model is a direct extension of the separated continuouslinear program (SCLP) to include time-delays and is called the separated continuouslinear program with time-delays (SCLPTD). By suitable transformations we are able to rewrite SCLPTD in a manner which is very close to SCLP itself. This then allows us to use all the recent theory and algorithms for SCLP to derive similar results for SCLPTD. In particular, the theory we present includes a characterization of the extreme-point solutions, an existence theorem for piecewise analytic optimal extreme-point solutions, and a strong duality theorem. We also present a class of convergent algorithms for the solution of SCLPTD in certain instances.
This paper surveys the recent developments in the theoretical study of separated continuouslinear programs (SCLP). This problem serves as a useful model for various dynamic network problems where storage is permitted...
详细信息
This paper presents a detailed duality theory for a class of continuouslinear programs called separated continuouslinear programs (SCLP), based on a particular dual problem SCLP*. Using weak duality, a notion of com...
详细信息
This paper presents a detailed duality theory for a class of continuouslinear programs called separated continuouslinear programs (SCLP), based on a particular dual problem SCLP*. Using weak duality, a notion of complementary slackness is introduced, and several sufficient conditions for optimality of SCLP are derived along with the existence of complementary slack variables for basic feasible solutions for SCLP. Following this, a fairly general condition for the absence of a duality gap between SCLP and SCLP* is given, as are several conditions for the existence of an optimal solution for SCLP*. Finally, using all these ingredients, a strong duality result between SCLP and SCLP* is proven when the problem data are piecewise analytic. A simple counterexample is presented to show that strong duality may not follow if the assumptions of piecewise analyticity do not hold.
暂无评论