Server allocation for zero buffer tandem queues

In this paper we consider the problem of allocating servers to maximize throughput for tandem queues with no buffers. We propose an allocation method that assigns servers to stations based on the mean service times and the current number of servers assigned to each station. A number of simulations are run on different configurations to refine and verify the algorithm. The algorithm is proposed for stations with exponentially distributed service times, but where the service rate at each station may be different. We also provide some initial thoughts on the impact on the proposed allocation method of including service time distributions with different coefficients of variation.     

An efficient computation algorithm for a multiserver feedback retrial queue with a large queueing capacity

Kumar et al. consider the M/M/c/N+c feedback queue with constant retrial rate [1]. They provide a solution for the steady state probabilities based on the matrix-geometric method. We show that there exists a more efficient computation method to calculate the steady state probabilities when N+c$N+c$ is large. We prove that the number of zero-eigenvalues of the characteristic matrix polynomial associated with the balance equation is ⌊(N+c+2)/2⌋$\lfloor (N+c+2)/2\rfloor$. As consequence, the remaining eigenvalues inside the unit circle can be computed in a quick manner based on the Sturm sequences. Therefore, the steady state probabilities can be determined in an efficient way.     

An inexact algorithm for the sequential ordering problem

Given the directed G = (N, A) and the penalty matrix C, the Sequential Ordering Problem (hereafter, SOP) consists of finding the permutation of the nodes from the set N, such that it minimizes a C-based function and does not violate the precedence relationships given by the set A. Strong sufficient conditions for the infeasibility of a SOP's instance are embedded in a procedure for the SOP's pre-processing. Note that it is one of the key steps in any algorithm that attempts to solve SOP. By dropping the constraints related to the precedence relationships, SOP can be converted in the classical Asymmetric Traveling Salesman Problem (hereafter, ASTP). The algorithm obtains (hopefully) satisfactory solutions by modifying the optimal solution to the related Assignment Problem (hereafter, AP) if it is not a Feasible Sequential Ordering (hereafter, FSO). The new solution ‘patches’ the subtours (if any) giving preference to the patches with zero reduced cost in the linking arcs. The AP-based lower bound on the optimal solution to ATSP is tightened by using some of the procedures given in [1]. In any case, a local search for improving the initial FSO is performed; it uses 3- and 4-changed based procedures. Computational results on a broad set of cases are reported.     

A sequential Monte Carlo algorithm for solving BSDEs

We present and analyze a numerical algorithm for solving BSDEs based on Picard iterations and on a sequential control variate method. Its convergence is geometric. Moreover, our algorithm provides a regular solution w.r.t. time and space. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A lexicographic minimax algorithm for multiperiod resource allocation

Resource allocation problems are typically formulated as mathematical programs with some special structure that facilitates the development of efficient algorithms. We consider a multiperiod problem in which excess resources in one period can be used in subsequent periods. The objective minimizes lexicographically the nonincreasingly sorted vector of weighted deviations of cumulative activity levels from cumulative demands. To this end, we first develop a new minimax algorithm that minimizes the largest weighted deviation among all cumulative activity levels. The minimax algorithm handles resource constraints, ordering constraints, and lower and upper bounds. At each iteration, it fixes certain variables at their lower bounds, and sets groups of other variables equal to each other as long as no lower bounds are violated. The algorithm takes advantage of the problem's special structure; e.g., each term in the objective is a linear decreasing function of only one variable. This algorithm solves large problems very fast, orders of magnitude faster than well known linear programming packages. (The latter are, of course, not designed to solve such minimax problems efficiently.) The lexicographic procedure repeatedly employs the minimax algorithm described above to solve problems, each of the same format but with smaller dimension.     

An efficient sequential quadratic programming algorithm for nonlinear programming

In this paper, a new feasible sequential quadratic programming (FSQP) algorithm is proposed to solve the nonlinear programming, where a feasible descent direction is obtained by solving only one QP subproblem. In order to avoid Maratos effect, a high-order revised direction is computed by solving a linear system with involving some “active” constraints. The theoretical analysis shows that global and superlinear convergence can be deduced.     

Non-monotonous sequential subgradient projection algorithm for convex feasibility problem

Acta Mathematicae Applicatae Sinica, English Series - The existing methods of projection for solving convex feasibility problem may lead to slow convergence when the sequences enter some...     

A sparse sequential quadratic programming algorithm

Described here is the structure and theory for a sequential quadratic programming algorithm for solving sparse nonlinear optimization problems. Also provided are the details of a computer implementation of the algorithm along with test results. The algorithm maintains a sparse approximation to the Cholesky factor of the Hessian of the Lagrangian. The solution to the quadratic program generated at each step is obtained by solving a dual quadratic program using a projected conjugate gradient algorithm. An updating procedure is employed that does not destroy sparsity.     

A sequential quadratic programming algorithm for equality-constrained optimization without derivatives

In this paper, we present a new model-based trust-region derivative-free optimization algorithm which can handle nonlinear equality constraints by applying a sequential quadratic programming (SQP) approach. The SQP methodology is one of the best known and most efficient frameworks to solve equality-constrained optimization problems in gradient-based optimization [see e.g. Lalee et al. (SIAM J Optim 8:682–706, 1998), Schittkowski (Optim Lett 5:283–296, 2011), Schittkowski and Yuan (Wiley encyclopedia of operations research and management science, Wiley, New York, 2010)]. Our derivative-free optimization (DFO) algorithm constructs local polynomial interpolation-based models of the objective and constraint functions and computes steps by solving QP sub-problems inside a region using the standard trust-region methodology. As it is crucial for such model-based methods to maintain a good geometry of the set of interpolation points, our algorithm exploits a self-correcting property of the interpolation set geometry. To deal with the trust-region constraint which is intrinsic to the approach of self-correcting geometry, the method of Byrd and Omojokun is applied. Moreover, we will show how the implementation of such a method can be enhanced to outperform well-known DFO packages on smooth equality-constrained optimization problems. Numerical experiments are carried out on a set of test problems from the CUTEst library and on a simulation-based engineering design problem.     

A sequential cutting plane algorithm for solving convex NLP problems

In this paper we look at a new algorithm for solving convex nonlinear programming optimization problems. The algorithm is a cutting plane-based method, where the sizes of the subproblems remain fixed, thus avoiding the issue with constantly growing subproblems we have for the classical Kelley’s cutting plane algorithm. Initial numerical experiments indicate that the algorithm is considerably faster than Kelley’s cutting plane algorithm and also competitive with existing nonlinear programming algorithms.     

A sequential dual simplex algorithm for the linear assignment problem

We present a sequential dual-simplex algorithm for the linear problem which has the same complexity as the algorithms of Balinski [3,4] and Goldfarb [8]: O(n²) pivots, O(n² log n + nm) time. Our algorithm works with the (dual) strongly feasible trees and can handle rectangular systems quite naturally.     

A spectral algorithm for sequential aggregation ofm linear diophantine constraints

An algorithm is developed for the sequential determination of the coefficients of a generalized linear Diophantine constraint which is equivalent to a given system of generalized linear Diophantine constraints.

---

Zusammenfassung Ein Algorithmus wird entwickelt für die sequentielle Bestimmung der Koeffizienten einer verallgemeinerten linearen Diophantischen Restriktion, die einem vorgelegten System verallgemeinerter linearer Diophantischer Restriktionen äquivalent ist.

     

Loading,unloading and premarshalling of stacks in storage areas: Survey and classification

Problems of loading, unloading and premarshalling of stacks as well as combinations thereof appear in several practical applications, e.g. container terminals, container ship stowage planning, tram depots or steel industry. Although these problems seem to be different at first sight, they hold plenty of similarities. To precisely unite all aspects, we suggest a classification scheme and show how problems existing in literature can be described with it. Furthermore, we give an overview of known complexity results and solution approaches.     

Multiple criterion management of a sequential fishery

A static stochastic simulation was used to assess the performance of alternative management strategies in the satisfaction of multiple objective criteria in the context of a sequentially exploited transboundary resource. The model was applied to the Yukon River chum salmon (Oncorhynchus keta) fishery. Four strategies were evaluated using three criteria: probability of satisfying escapement objectives; probability of jointly satisfying escapement and subsistence harvest objectives; and probability of simultaneously reaching escapement, subsistence and commercial harvest objectives. The modeled strategies were also compared with the actual performance of the fishery for 1980–1995. The results indicate that satisfaction of escapement and subsistence harvest goals in the middle Yukon depends on imposing restrictive limits on commercial harvests in the lower Yukon. However, even with full information, escapement objectives in the upper drainage are only satisfied 65–70% and 75–80% of the time for summer and fall chum, respectively. The model was also used to explore the effects of increased average run strength that could arise from reduced bycatch of Yukon origin chum in marine fisheries. The results suggest that reduced marine interceptions are unlikely to substantially increase the probability of satisfying catch and escapement goals for the middle and upper Yukon.     

A sequential equality constrained quadratic programming algorithm for inequality constrained optimization

In this paper, the feasible type SQP method is improved. A new SQP algorithm is presented to solve the nonlinear inequality constrained optimization. As compared with the existing SQP methods, per single iteration, in order to obtain the search direction, it is only necessary to solve equality constrained quadratic programming subproblems and systems of linear equations. Under some suitable conditions, the global and superlinear convergence can be induced.     

On the discrete-time system with server breakdowns: Computational algorithm and optimization algorithm

This paper analyzes a discrete-time Geo/Geo/1 queueing system with the server subject to breakdowns and repairs, in which two different possible types of the server breakdowns are considered. In Type 1, the server may break down only when the system is busy, while in Type 2, the server can break down even if the system is idle. The server lifetimes are assumed to be geometrical and the server repair times are also geometric distributions. We model this system by the level-dependent quasi-birth-death (QBD) process and develop computation algorithms of the stationary distribution of the number of customers in the system using the matrix analytic method. The search algorithm for parameter optimization based on a cost model is developed and performed herein.     

(Approximate) iterated successive approximations algorithm for sequential decision processes

The paper proves the convergence of (Approximate) Iterated Successive Approximations Algorithm for solving infinite-horizon sequential decision processes satisfying the monotone contraction assumption. At every stage of this algorithm, the value function at hand is used as a terminal reward to determine an (approximately) optimal policy for the one-period problem. This policy is then iterated for a (finite or infinite) number of times and the resulting return function is used as the starting value function for the next stage of the scheme. This method generalizes the standard successive approximations, policy iteration and Denardo’s generalization of the latter.     

An efficient algorithm for allocating paged,drum-like storage

Cody and Coffman have studied the problem of distributing a set of a equal-size records among the sectors of a drum-like storage device so as to minimize the average rotational latency cost. This paper is an extension of that work. We employ the same model but a different latency delay function. Motivated by the NP-completeness of the general problem and the fact that an arbitrary assignment can have an expected latency cost almost twice that of an optimal assignment, we propose and analyze a fast heuristic whose performance compares favorably with that of an optimal algorithm.This research was supported in part by the National Science Foundation under Grant no. 28290.     

New sequential quadratic programming algorithm with consistent subproblems

One of the most interesting topics related to sequential quadratic programming algorithms is how to guarantee the consistence of all quadratic programming subproblems. In this decade, much work trying to change the form of constraints to obtain the consistence of the subproblems has been done. The method proposed by De O. Pantoja J.F. A. and coworkers solves the consistent problem of SQP method, and is the best to the authors’ knowledge. However, the scale and complexity of the subproblems in De O. Pantoja’s work will be increased greatly since all equality constraints have to be changed into absolute form. A new sequential quadratic programming type algorithm is presented by means of a special ε-active set scheme and a special penalty function. Subproblems of the new algorithm are all consistent, and the form of constraints of the subproblems is as simple as one of the general SQP type algorithms. It can be proved that the new method keeps global convergence and Local superlinear convergence. Project partly supported by the National Natural Science Foundation of China.