Mathematics of Operations Research

We investigate a processor-sharing queue with renewal arrivals and generally distributed service times. Impatient jobs may abandon the queue or renege before completing service. The random time representing a job's patience has a general distribution and may be dependent on its initial service time requirement. A scaling procedure that gives rise to a fluid model with nontrivial yet tractable steady state behavior is presented. This fluid model captures many essential features of the underlying stochastic model, and it is used to analyze the impact of impatience in processor-sharing queues.

We consider a GI/G/1 queueing system where the nth arrival may renege if his service does not commence before an elapsed random time Z_n. Results for the general case include relations analogous to Little's formula L = λW, an expression for the average fraction of customers who renege from the system, expressions for the waiting time distribution for all arrivals to the system, the waiting time distribution for arrivals who reach the server, the distribution for virtual waiting time in the queue, and the distribution of the steady-state number of customers in the system and the number of customers left in the system by a completed service. These expressions are written in terms of the distribution of the work seen by an arbitrary arrival to the system, and an integral equation for this distribution is given along with necessary and sufficient conditions for existence of the distribution. Solutions to the integral equation are found for a number of forms for customer interarrival, service, and reneging distributions, and we show how the previous results on the subject of queueing with reneging follow as special cases of our approach. Some past and potential applications of queues with reneging are also discussed.

We study G/G/n + GI queues in which customer patience times are independent, identically distributed following a general distribution. When a customer's waiting time in queue exceeds his patience time, the customer abandons the system without service. For the performance of such a system, we focus on the abandonment process and the queue length process. We prove that under some conditions, a deterministic relationship between the two stochastic processes holds asymptotically under the diffusion scaling when the number of servers n goes to infinity. These conditions include a minor assumption on the arrival processes that can be time-nonhomogeneous and a key assumption that the sequence of diffusion-scaled queue length processes, indexed by n, is stochastically bounded. We also establish a comparison result that allows one to verify the stochastic boundedness by studying a corresponding sequence of systems without customer abandonment.

We study a single-server queue, operating under the first-in-first-out (FIFO) service discipline, in which each customer independently abandons the queue if his service has not begun within a generally distributed amount of time. Under some mild conditions on the abandonment distribution, we identify a limiting heavy-traffic regime in which the resulting diffusion approximation for both the offered waiting time process (the process that tracks the amount of time an infinitely patient arriving customer would wait for service) and the queue-length process contain the entire abandonment distribution. To use a continuous mapping approach to establish our weak convergence results, we additionally develop existence, uniqueness, and continuity results for nonlinear generalized regulator mappings that are of independent interest. We further perform a simulation study to evaluate the quality of the proposed approximations for the steady-state mean queue length and the steady-state probability of abandonment suggested by the limiting diffusion process.

This paper investigates the solutions to the functional equations that arise inter alia in Undiscounted Markov Renewal Programming. We show that the solution set is a connected, though possibily nonconvex set whose members are unique up to n* constants, characterize n* and show that some of these n* degrees of freedom are locally rather than globally independent.

Our results generalize those obtained in Romanovsky (Romanovsky, I. 1973. On the solvability of Bellman's functional equation for a Markovian decision process. J. Math. Anal. Appl. 42 485–498.) where another approach is followed for a special class of discrete time Markov Decision Processes. Basically our methods involve the set of randomized policies. We first study the sets of pure and randomized maximal-gain policies, as well as the set of states that are recurrent under some maximal-gain policy.

This paper presents an extension of the Poincaré-Hopf theorem to generalized critical points of a function on a compact region with nonsmooth boundary, M, defined by a finite number of smooth inequality constraints. Given a function F: M ↦ ℝⁿ, we define the generalized critical points of F over M, define the index for the critical point, and show that the sum of the indices of the critical points is equal to the Euler characteristic of M. We use the generalized Poincaré-Hopf theorem to present sufficient (local) conditions for the uniqueness of solutions to finite-dimensional variational inequalities and the uniqueness of stationary points in nonconvex optimization problems.

In flow shop scheduling there are m machines and n jobs, such that every job has to be processed on the machines in the fixed order 1,…,m. In the permutation flow shop problem, it is also required that each machine process the set of all jobs in the same order. Formally, given n jobs along with their processing times on each machine, the goal is to compute a single permutation of the jobs σ: [n] → [n] that minimizes the maximum job completion time (makespan) of the schedule resulting from σ. The previously best known approximation guarantee for this problem was O((m log m)^1/2) [Sviridenko, M. 2004. A note on permutation flow shop problem. Ann. Oper. Res. 129 247–252]. In this paper, we obtain an improved O(min{m^1/2,n^1/2}) approximation algorithm for the permutation flow shop scheduling problem, by finding a connection between the scheduling problem and the longest increasing subsequence problem. Our approximation ratio is relative to the lower bounds of maximum job length and maximum machine load, and is the best possible such result. This also resolves an open question from Potts et al. [Potts, C., D. Shmoys, D. Williamson. 1991. Permutation vs. nonpermutation flow shop schedules. Oper. Res. Lett. 10 281–284], by algorithmically matching the gap between permutation and nonpermutation schedules.

We also consider the weighted completion time objective for the permutation flow shop scheduling problem. Using a natural linear programming relaxation and our algorithm for the makespan objective, we obtain an O(min{m^1/2,n^1/2}) approximation algorithm for minimizing the total weighted completion time, improving on the previously best known guarantee of εm for any constant ε > 0 [Smutnicki, C. 1998. Some results of the worst-case analysis for flow shop scheduling. Eur. J. Oper. Res. 109 66–87]. We give a matching lower bound on the integrality gap of our linear programming relaxation.

We demonstrate the impossibility of strongly polynomial algorithms for the allocation problem, in the comparison model and in the algebraic tree computation model, that follow from lower bound results. Consequently, there are no strongly polynomial algorithms for nonlinear (concave) separable optimization over a totally unimodular constraint matrix. This is in contrast to the case when the objective is linear.

We present scaling-based algorithms that use a greedy algorithm as a subroutine. The algorithms are polynomial for the allocation problem and its extensions and are also optimal for the sample allocation problem and the generalized upper bounds allocation problem, in that the complexity meets the lower bound derived from the comparison model. For other extensions of the allocation problem the scaling-based algorithms presented here are the fastest known.

These algorithms are also polynomial time algorithms for solving with ε accuracy the allocation problem and its extension in continuous variables.

We point out the difficulties associated with measuring the quality of an approximate (heuristic) solution by “Percentage-Error” as is customary. We define a set of properties that are to be expected from a proper measure of solution quality and investigate the family of functions which satisfy those conditions. In particular, we show that for any class of 0–1 programming problems appropriate functions do exist and that they are uniquely defined up to monotone transformations. We conclude with several examples of linear functions which are suitable for certain classes of problems.

We examine the class of totally unimodular matrices-that contain no odd cycles, which we call restricted totally unimodular (RTUM). We show that a matrix is RTUM if and only if it can be decomposed in a very simple way into the incidence matrices (or their transposes) of bipartite graphs or directed graphs, and give a linear time algorithm to perform this task. Based on this decomposition, we show that the 0,1 Integer Programming Problem with an RTUM matrix of constraints has the same time complexity as the b-matching and the max flow problems.