bluuebunny/crossref_metadata_2025 huggingface dataset:
When Is the Classroom Assignment Problem Hard?
Authors: Carter Michael W. , Tovey Craig A.
Published: November 2008

The classroom assignment (or hotel room or interval scheduling) problem is to assign classes, which meet at different time intervals, to rooms. Two classes may not meet simultaneously in the same room, nor may a class meet in two different rooms. Thousands of colleges and secondary schools face this problem every semester. There has been some confusion as to how hard this problem is. Many colleges claim that it is easy, while others complain that it is next to impossible. In the literature, some authors claim or conjecture polynomial time algorithms, while others develop heuristic approaches. The goal of this paper is to resolve the confusion by identifying cases where the problem will be easy and others where it will be hard. We focus on the kinds of cases that schedulers are apt to encounter in practice.
Bounds on a Trauma Outcome Function via Optimization
Authors: Falk James E. , Palocsay Susan W. , Sacco William J. , Copes Wayne S. , Champion Howard R.
Published: November 2008

One measure of the effectiveness of institutional trauma and burn management based on collected patient data involves the computation of a standard normal Z statistic. A potential weakness of the measure arises from incomplete patient data. In this paper, we apply methods of fractional programming and global optimization to efficiently calculate bounds on the computed effectiveness of an institution. The measure of effectiveness (i.e., the trauma outcome function) is briefly described, the optimization problems associated with its upper and lower bounds are defined and characterized, and appropriate solution procedures are developed. We solve an example problem to illustrate the method.
Design and Management of Curtailable Electricity Service to Reduce Annual Peaks
Authors: Oren Shmuel S. , Smith Stephen A.
Published: November 2008

Curtailable electricity service is a voluntary option in which customers receive credits for permitting the utility a certain number of discretionary interruptions per year. This paper describes a methodology that allows an electric utility to design and manage these service offerings to achieve maximal peak load reduction. This methodology was developed in a project jointly sponsored by the Electric Power Research Institute (EPRI) and New England Electric Service (NEES). A spreadsheet decision support tool was developed for and used by the NEES system dispatcher, who must decide on a daily basis, when to call for an interruption. The methodology also provides guidelines for designing new service offerings, by determining the service attributes and corresponding pricing that will lead to the most efficient use of customer interruptions. Simulated application of the spreadsheet model to NEES's historical loads indicated that significant cost savings can be achieved during years with high daily peak loads. Although the methodology was developed for NEES, it can be applied at other electric utilities, including those who use curtailable service offerings to reduce peak energy costs or to improve tight reserve margins.
Unidirectional Loop Network Layout Problem in Automated Manufacturing Systems
Authors: Kouvelis Panagiotis , Kim Michael W.
Published: November 2008

In this paper, we address the design of unidirectional loop network layouts for automated manufacturing environments. We show that the problem is NP-complete. Using a workstation interchange argument, we develop dominance relationships for easy identification of local optimal solutions. Our results suggest the need for simple heuristics to solve the problem. We identify cases in which the heuristics perform optimally, and we analyze the worst case behavior of the heuristics. We develop an optimal branch-and-bound procedure that is computationally efficient for medium-sized problems. We also present a decomposition principle helpful for dealing with large workflow matrices. We report computational results on the heuristics and the branch-and-bound procedure. We show that one of the heuristics performs impressively well in terms of solution quality and computational time requirements.
A Noniterative Algorithm for the Multiproduct Production and Work Force Planning Problem
Authors: Singhal Kalyan
Published: November 2008

Discrete optimal control theory is used to develop an efficient noniterative algorithm for solving the multiproduct production and work force planning problems with a quadratic cost function. The quadratic cost models allow uncertainties to be handled directly because they minimize the expected cost if unbiased expected demand forecasts are given. A real-world problem may involve as many as 200,000 variables. The noniterative algorithm makes the computations, irrespective of the number of products, not only feasible but also extremely easy and efficient.
Multiclass Queueing Systems: Polymatroidal Structure and Optimal Scheduling Control
Authors: Shanthikumar J. George , Yao David D.
Published: November 2008

In many multiclass queueing systems, certain performance measures of interest satisfy strong conservation laws. That is, the total performance over all job types is invariant under any nonidling service control rule, and the total performance over any subset (say A) of job types is minimized or maximized by offering absolute priority to the types in A over all other types. We develop a formal definition of strong conservation laws, and show that as a necessary consequence of these strong conservation laws, the state space of the performance vector is a (base of a) polymatroid. From known results in polymatroidal theory, the vertices of this polyhedron are easily identified, and these vertices correspond to absolute priority rules. A wide variety of multiclass queueing systems are shown to have this polymatroidal structure, which greatly facilitates the study of the optimal scheduling control of such systems. When the defining set function of the performance space belongs to the class of generalized symmetric functions, additional applications are discussed, which include establishing convexity and concavity properties in various queueing systems.
Craft in Operations Research
Authors: Miser Hugh J.
Published: November 2008

As in any science, day-to-day work in operations research involves diverse craft skills. This informal essay discusses some early examples, based on the work of W. J. Youden, one of the unsung heroes of OR work during World War II. It is based on a banquet talk given September 5, 1991 at the Eighth International Symposium on Military Operational Research held at the Royal Military College of Science, Shrivenham, United Kingdom.
A Criterion for Comparing Strength of Preference with an Application to Bargaining
Authors: Peters Hans
Published: November 2008

A criterion called “improving faster than” is proposed and characterized to compare the strength or preference of value functions. The result can be applied in decision models where no risk is involved or, at least, explicitly modeled. A bargaining theory example illustrates the criterion.
Improving the Effectiveness of FDA Drug Inspection
Authors: Klimberg Ronald , Revelle Charles , Cohon Jared
Published: November 2008

The evaluation and the allocation of inspection resources is a problem faced by private sector firms as well as by several government agencies. This paper reports the development and the use by the Food and Drug Administration (FDA) of decision making tools for measuring the performance of their drug inspection activities in which data are collected only intermittently, and a multiobjective integer program to assist FDA decision makers in planning and evaluating the effectiveness of their drug inspection activities.
Stochastic and Dynamic Vehicle Routing in the Euclidean Plane with Multiple Capacitated Vehicles
Authors: Bertsimas Dimitris J. , van Ryzin Garrett
Published: November 2008

In 1991, D. J. Bertsimas and G. van Ryzin introduced and analyzed a model for stochastic and dynamic vehicle routing in which a single, uncapacitated vehicle traveling at a constant velocity in a Euclidean region must service demands whose time of arrival, location and on-site service are stochastic. The objective is to find a policy to service demands over an infinite horizon that minimizes the expected system time (wait plus service) of the demands. This paper extends our analysis in several directions. First, we analyze the problem of m identical vehicles with unlimited capacity and show that in heavy traffic the system time is reduced by a factor of 1/m2 over the single-server case. One of these policies improves by a factor of two on the best known system time for the single-server case. We then consider the case in which each vehicle can serve at most q customers before returning to a depot. We show that the stability condition in this case depends strongly on the geometry of the region. Several policies that have system times within a constant factor of the optimum in heavy traffic are proposed. Finally, we discuss extensions to mixed travel cost and system time objectives.
Optimal Search Density for a Stationary Target Among Stationary False Targets
Authors: Kalbaugh D. V.
Published: November 2008

This paper considers rational methods for the design of search densities when the intended target is stationary among stationary, Poisson-distributed false contacts. Attention is restricted to situations in which the searcher must immediately decide, based on sensed information, whether a contact is the intended target and, if the answer is yes, end the search and commit to the contact. Discrimination of false contact from target is modeled as reliable only with given probabilities. We seek to allocate search effort to maximize the probability of finding the intended target in a fixed time. Modeling space and time as discrete, we apply the Kuhn-Tucker theorem to obtain a set of necessary conditions for an optimum. For the particular case of a discrete space and time approximation of search for a normally distributed target in R2 and a uniform density of false contacts, we develop a computer algorithm that converges to a solution of the necessary conditions. Numerical results are presented.
A Massively Parallel Algorithm for Nonlinear Stochastic Network Problems
Authors: Nielsen Soren S. , Zenios Stavros A.
Published: November 2008

We develop an algorithm for solving nonlinear, two-stage stochastic problems with network recourse. The algorithm is based on the framework of row-action methods. The problem is formulated by replicating the first-stage variables and then adding nonanticipativity side constraints. A series of (independent) deterministic network problems are solved at each step of the algorithm, followed by an iterative step over the nonanticipativity constraints. The solution point of the iterates over the nonanticipativity constraints is obtained analytically. The row-action nature of the algorithm makes it suitable for parallel implementations. A data representation of the problem is developed that permits the massively parallel solution of all the scenario subproblems concurrently. The algorithm is implemented on a Connection Machine CM-2 with up to 32K processing elements and achieves computing rates of 276 MFLOPS. Very large problems—8,192 scenarios with a deterministic equivalent nonlinear program with 868,367 constraints and 2,474,017 variables—are solved within a few minutes. We report extensive numerical results regarding the effects of stochasticity on the efficiency of the algorithm.
On Aggregation of Items in Single-Stage Production Systems with Limited Inventory Levels
Authors: Pieńkosz Krzysztof , Toczyłowski Eugeniusz
Published: November 2008

The paper considers the aggregation of similar products in the lot size scheduling problems for single-stage systems with limited upper bounds on inventory levels. The necessary and sufficient conditions of consistent aggregation, which guarantee that the optimal aggregate solution can be disaggregated into an optimal solution of the original problem, are presented.
Decomposition for Scheduling Flexible Manufacturing Systems
Authors: Inman Robert R. , Jones Philip C.
Published: November 2008

In some flexible manufacturing systems, tool magazine capacity naturally divides parts into families so that substantial setups occur only when switching production between families. For this situation (positive setup times and costs only between families), we show that the production planning problem decomposes into two simpler problems: an aggregate scheduling problem, and a disaggregation. First, we derive a disaggregation that determines the optimal intrafamily product schedules corresponding to a given family schedule in polynomial time. Second, we show how to aggregate so that the decomposition maintains optimality for family schedules satisfying the property that production does not begin until inventory is zero (the Zero-Switch rule).
The On-Time Machines: Some Analyses of Airline Punctuality
Authors: Caulkins Jonathan P. , Barnett Arnold , Larkey Patrick D. , Yuan Yuehong , Goranson Jesse
Published: November 2008

The Department of Transportation (DOT) rates commercial airlines' on-time performance every month, but its ratings may unfairly penalize airlines that disproportionately fly into airports at which it is inherently more difficult to land in on-time. We propose several rating methods that we consider more equitable and apply them to 36 months of DOT data. Rating airlines' promptness is an example of the more general problem of evaluating players who compete in overlapping but not identical sets of tournaments, where there is no exogenous knowledge about the quality of the players or the “difficulty” of the tournaments.
Exact and Approximate Evaluation of Batch-Ordering Policies for Two-Level Inventory Systems
Authors: Axsäter Sven
Published: November 2008

We consider a two-level inventory system with one warehouse and N identical retailers. Lead times (transportation times) are constant and the retailers face independent Poisson demand. In a previous paper, we derived a recursive procedure for determining the policy costs for an average item in case of one-for-one replenishment policies. In this paper, we show how these results can be used for the exact or approximate evaluation of more general policies where both the retailers and the warehouse order in batches. We compare our methods to the method recently suggested by A. Svoronos and P. Zipkin.
On the Minimization of the Makespan Subject to Flowtime Optimality
Authors: Eck Brian Thomas , Pinedo Michael
Published: November 2008

When scheduling n jobs on m identical machines in parallel, two performance criteria are of particular interest: the makespan (the completion time of the last job) and the flowtime (the sum of the completion times of all n jobs). Whereas minimizing makespan is NP-hard, many schedules minimize flowtime, and they are easy to characterize. This paper considers the problem of minimizing the makespan among flowtime-optimal schedules. Heuristics have appeared in the literature that result in flowtime-optimal schedules with makespans which are always less than or equal to 5/4 times the minimum flowtime-optimal makespan. In this note, we present new heuristics for this problem, one of which yields a worst-case bound of 28/27 for the two-machine case. The new heuristics have a running time of O(n log n). Extensions are discussed for general m.
Design and Implementation of an Expert System for Controlling Health Care Costs
Authors: Martin Jack L. , Harrison Terry P.
Published: November 2008

Many firms with self-funded medical insurance administered by outside parties fail to review the administrators' performance effectively. Often the firms do not know the extent of overpayments because they lack the expert knowledge to evaluate the paid claims. We examine the use of a simple expert system in conjunction with optimization methods for identifying claims payment errors. The knowledge base is constructed using expertise from the areas of claims processing, auditing, medical diagnosis, and procedure coding practices. Once potential errors are identified, a mathematical program is used to select claims for audit based on maximizing expected benefits subject to various firm-specific processing limitations. We use an efficient Lagrangian relaxation to solve instances of this pure binary programming problem with as many as 150,000 variables. We report on our experience in the use of this system on behalf of a Fortune 100 firm's claims data base.
Minimax Resource Allocation Problems with Resource-Substitutions Represented by Graphs
Authors: Klein Rachelle S. , Luss Hanan , Rothblum Uriel G.
Published: November 2008

Resource allocation problems focus on the allocation of limited resources among competing activities. We examine such problems when certain substitutions among resources are possible. The substitutional relations can be represented by a graph comprised of multiple components. In each component, the nodes correspond to resources and the arcs correspond to feasible substitutions. The objective is of the minimax form, where each term is a continuous, strictly decreasing function of a single activity level. The objective is to minimize the largest term, subject to a limited supply of multiple resources. Potential applications to such problems are found, for example, in the manufacture of high tech products. We develop an efficient algorithm to solve such problems. At each iteration, a relaxed minimax problem is solved. A max-flow algorithm is then applied to determine whether the solution of the relaxed problem is feasible for the original problem. If the solution is infeasible, a tighter relaxed problem is formulated and resolved. The algorithm is also extended to find the lexicographic minimax solution. Computational results are presented.
A Random Activity Network Generator
Authors: Demeulemeester E. , Dodin B. , Herroelen W.
Published: November 2008

Exact and heuristic procedures are often developed to obtain optimal and near-optimal solutions to decision problems modeled as activity networks. Testing the accuracy and efficiency of these procedures requires the use of activity networks with various sizes, structures, and parameters. The size of the network is determined by its number of nodes and arcs, where the structure is chosen from the set of all structures for the specified network size. The network parameters depend on the nature of the decision problem. Often, it is desirable for test problems to be generated at random from the space of all feasible networks. This paper deals with the problem of generating the size and structure of the network at random from the space of all feasible networks. It develops a theory which guarantees the randomness of the network structure. The theory is the basis for two methods. One can be used to generate dense networks, where the other is used to generate nondense networks. The methods, which are practical and easy to use, have been programmed for use on mainframe or personal computers. CPU time requirements are negligible. Copies of the computer program can be obtained from the authors.
Optimal Expulsion Control—A Dual Approach to Admission Control of an Ordered-Entry System
Authors: Xu Susan H. , Shanthikumar J. George
Published: November 2008

In this paper we obtain the optimal admission control policy for a first-come, first-served (FCFS) M/M/m ordered-entry queueing system to maximize the expected discounted (and the long-run average) profit (reward minus cost). We introduce a new approach for determining the optimal admission control policy. The underlying idea of this approach is to construct a dual system: a preemptive last-come, first-served (LCFS-P) M/M/m ordered-entry queueing system that is subject to expulsion control. We show that an LCFS-P system with expulsion control is isomorphic to an FCFS system with admission control, and the two systems share the same optimal control policy. Eluding the conventional dynamic programming formulation, we approach the solution from behaviors of individual customers and their impact on the social outcome. This makes our analysis simple and intuitive and reveals a better insight into the structural properties of the optimal control policy. Besides providing formulas to compute the optimal threshold, we use the operational characteristics of the dual system to obtain an easily computable approximation for the optimal threshold. The applicability of the approach transcends well beyond the problem addressed in this paper.
New Lower and Upper Bounds for Scheduling Around a Small Common Due Date
Authors: Hoogeveen J. A. , Oosterhout H. , van de Velde S. L.
Published: November 2008

We consider the single-machine problem of scheduling n jobs to minimize the sum of the deviations of the job completion times from a given small common due date. For this NP-hard problem, we develop a branch-and-bound algorithm based on Lagrangian lower and upper bounds that are found in O(n log n) time. We identify conditions under which the bounds concur; these conditions can be expected to be satisfied by many instances with n not too small. In our experiments with processing times drawn from a uniform distribution, the bounds concur for n ≥ 40. For the case where the bounds do not concur, we present a refined lower bound that is obtained by solving a subset-sum problem of small dimension to optimality. We further develop a 4/3-approximation algorithm based upon the Lagrangian upper bound.
Production-Inventory Systems with Unreliable Machines
Authors: Berg M. , Posner M. J. M. , Zhao H.
Published: November 2008

A broad class of production-inventory systems is studied in which a number of producing machines are susceptible to failure following which they must be repaired to make them operative again. The machines' production can also be stopped deliberately due to stocking capacity limitations or any other relevant considerations. The interplay between the processes involved, namely, production, demand, and failure/repair or reliability, in conjunction with the shutdown policy used, determine the inventory accumulation process and possible shortages. We first obtain the stationary distribution of the inventory process for different assumptions on the random behavior of the production, demand, and reliability processes. By employing level-crossing techniques, a mathematical analysis is carried out for a “core” model, which then serves the role of the nucleus for the study of a wide range of models. We compute performance measures that characterize the operation of the production-inventory system with respect to its service-level to customers, expected inventory stocked, machines' utilization, repairmen utilization, and so on. A numerical illustration is provided which shows the effect of machine breakdowns on service and inventory levels.
A Procurement Decision Support System in Business Volume Discount Environments
Authors: Sadrian Amir A. , Yoon Yong S.
Published: November 2008

Emergence of a new discount pricing schedule called Business Volume Discount becomes a major obstacle for procurement managers in finding the best purchasing strategy. In the context of business volume discount, a supplier offers discounts on total dollar amount of sales volume, not on the quantity or variety of the products purchased from the supplier. This paper describes a Procurement Decision Support System (PDSS) that has been successfully implemented to improve the purchasing activities of regional Bell telephone companies. In most purchasing operations, a flexible procurement plan is considered a necessity because of the uncertainties associated with product demand and procurement budget. PDSS provides this flexibility by combining two different purchasing strategies—purchasing on an annual commitment basis, and on an as-ordered basis. Although the development of the system is motivated by a particular application (procurement of transmission plug-in) in one of the regional telephone companies, the system is being used for a variety of procurement decisions involving business volume discount in the telecommunications industry. The results of the implementation indicate that cost savings of up to 15% are achieved. PDSS use is not limited to the companies in the telecommunications industry. The PDSS model is applicable to any organization having a centralized procurement operation with business volume discount.
Economic Lot Scheduling Problem with Raw Material Considerations
Authors: Gallego Guillermo , Joneja Dev
Published: November 2008

We extend the traditional model of the economic lot scheduling problem by considering various issues associated with the management of the raw materials for production. Several items are produced on a single machine at finite production rates with setup times, and setup and inventory holding costs. Raw materials are used for the production of these items. In the presence of setup and holding costs for the raw materials, we first formulate a planning model which provides a sharp lower bound on the cost of any policy for the problem. The solution is used to obtain policies which are guaranteed to be very close to optimal in the worst case. Finally, we consider the problem of obtaining good feasible schedules for both the machine and the raw materials.
Process Control with Learning
Authors: Dada Maqbool , Marcellus Richard
Published: November 2008

We study the control of a production process which moves at a random time from an in-control state to an out-of-control state where an increased number of defective units is produced. After each unit is produced, a decision maker has three choices: continue production, invest in routine maintenance that restores the process to control, and invest in a more expensive learn maintenance that, in addition, may decrease the tendency of the process to go out of control. The optimal policy structure is shown to be of the control-limit type with the property that learning is not optimal if the tendency of the process to go out of control is small enough. If there is no opportunity to inspect the process's output, an optimal policy can be interpreted as a fixed production run. For this case an exact algorithm is developed. When the process's output is inspected, an optimal policy can be interpreted as a random production run. Approximation techniques are presented for this case. The fixed production run model is an alternative technique for determining production lot sixes. The random production run model is an alternative to traditional Shewhart process control.
On the Conservation Law and the Performance Space of Single Server Systems
Authors: Georgiadis Leonidas , Viniotis Ioannis
Published: November 2008

We consider a multiclass GI/G/1 queueing system, operating under an arbitrary work-conserving scheduling policy π. We derive an invariance relation for the Cesaro sums of waiting times under π, which does not require the existence of limits of the Cesaro sums. This allows us to include important classes in the set of admissible policies such as time-dependent and adaptive policies. For these classes of policies, ergodicity is not known a priori and may not even exist. Therefore, the classical invariance relations that involve statistical averages do not hold. For an M/G/1 system, we derive inequalities involving the Cesaro sums of waiting times that further characterize the achievable performance region of the system.
Finite-Memory Suboptimal Design for Partially Observed Markov Decision Processes
Authors: White Chelsea C. , Scherer William T.
Published: November 2008

We develop bounds on the value function and a suboptimal design for the partially observed Markov decision process. These bounds and suboptimal design are based on the M most recent observations and actions. An a priori measure of the quality of these bounds is given. We show that larger M implies tighter bounds. An operations count analysis indicates that (#A#Z)M+1(#S) multiplications and additions are required per successive approximations iteration of the suboptimal design algorithm, where A, Z, and S are the action, observation, and state spaces, respectively, suggesting the algorithm is of potential use for problems with large state spaces. A preliminary numerical study indicates that the quality of the suboptimal design can be excellent.
Flow Shop Scheduling with Resource Flexibility
Authors: Daniels Richard L. , Mazzola Joseph B.
Published: November 2008

This paper explores the improvements in manufacturing efficiency that can be achieved by broadening the scope of production scheduling to include both the sequencing of work and the coordination of the resource inputs required to perform work. Recognizing that some resources are inherently flexible and thus can be reassigned dynamically to processing centers as needed, and that job processing times are often a function of the amount of resource dedicated to specific operations, we formulate the flexible-resource scheduling problem with the objective of simultaneously determining the permutation job sequence, resource allocation policy, and operation start times that optimize system performance. Focusing on flexible-resource scheduling in flow shop production systems, we discuss problem complexity, identify properties of and establish lower bounds for optimal schedules, develop optimal and heuristic solution approaches, and report the results of extensive computational experimentation designed to explore the operational benefits of resource flexibility. The computational results demonstrate that the performance improvements associated with flexible-resource scheduling are substantial, and suggest that the heuristic provides an effective means for solving larger problems.
A Monotonic Build-Up Simplex Algorithm for Linear Programming
Authors: Anstreicher Kurt M. , Terlaky Tamás
Published: November 2008

We devise a new simplex pivot rule which has interesting theoretical properties. Beginning with a basic feasible solution, and any nonbasic variable having a negative reduced cost the pivot rule produces a sequence of pivots such that ultimately the originally chosen nonbasic variable enters the basis, and all reduced costs which were originally nonnegative remain nonnegative. The pivot rule thus monotonically builds up to a dual feasible, and hence optimal, basis. A surprising property is that the pivot sequence results in intermediate bases which are neither primal nor dual feasible. We prove the correctness of the procedure, and relate it to other pivoting rules for linear programming.
A Constructive Method for Improving Lower Bounds for a Class of Quadratic Assignment Problems
Authors: Chakrapani Jaishankar , Skorin-Kapov Jadranka
Published: November 2008

A new approach to evaluate lower bounds for a class of quadratic assignment problems (QAP) is presented. An instance of a QAP of size n is specified by two n × n matrices D and F, and is denoted by QAP(D, F). This approach is presented for QAPs where D is the matrix of rectilinear distances between points on a regular grid. However, it can easily be generalized to a wider class of problems. Two matrices Fopt and Fres are constructed such that F = Fopt + Fres, and the optimal solution to QAP(D, Fopt) is known. Any existing lower bound can then be applied to QAP(D, Fres), which in sum with the optimal value for QAP(D, Fopt), provides a lower bound to QAP(D, F). Thus, this method could serve as a reduction process to possibly improve the results from a variety of bounding techniques. This approach is tested on two bounds from the literature, the Gilmore-Lawler bound (GLB) and an eigenvalue bound (PB), for various problems of size ranging from 6–49. Computational results show a good improvement in bounds for all the test problems. An extension of our method to a more general class of QAPs is also presented.
The Cafeteria Process—Tandem Queues with 0-1 Dependent Service Times and the Bowl Shape Phenomenon
Authors: Weber Richard R. , Weiss Gideon
Published: November 2008

Customers move through a series of M service stations. Each customer, independent of all others, requires service from only one of the stations, for a duration of 1 time unit, this being station i with probability pi. The customer has zero service at all the other stations, but there is no overtaking between the customers, and so queueing occurs. In the case where there is unlimited waiting room between the servers, we show that the system is interchangeable—permuting the order of the stations has no effect on the distribution of the output stream. When there is no waiting room between the stations we investigate optimal loads of the servers in terms of optimal pi's for up to 10 stations, and observe that optimal loads exhibit the bowl phenomenon. We also obtain some bounds on the throughput for equal loads as a function of M.
The Joint Replenishment Problem with Time-Varying Costs and Demands: Efficient, Asymptotic and ε-Optimal Solutions
Authors: Federgruen Awi , Tzur Michal
Published: November 2008

We address the Joint Replenishment Problem (JRP) where, in the presence of joint setup costs, dynamic lot sizing schedules need to be determined for m items over a planning horizon of N periods, with general time-varying cost and demand parameters. We develop a new, so-called, partitioning heuristic for this problem, which partitions the complete horizon of N periods into several relatively small intervals, specifies an associated joint replenishment problem for each of these, and solves them via a new, efficient branch-and-bound method. The efficiency of the branch-and-bound method is due to the use of a new, tight lower bound to evaluate the nodes of the tree, a new branching rule, and a new upper bound for the cost of the entire problem. The partitioning heuristic can be implemented with complexity O(mN2log log N). It can be designed to guarantee an ε-optimal solution for any ε > 0, provided that some of the model parameters are uniformly bounded from above or below. In particular, the heuristic is asymptotically optimal as N → ∞ for any fixed number of items m, and it remains asymptotically optimal when both m and N are simultaneously increased to infinity. Most importantly, a numerical study shows that the partitioning heuristic performs exceptionally well. Even for small problems, the average optimality gap is only 0.38% and in none of the problem categories is it larger than 0.78%.
Markov Chain Sampling and the Product Estimator
Authors: Fishman George S.
Published: November 2008

Several recent papers have suggested using a product estimator in Monte Carlo Markov chain sampling for estimating the volume of a convex body, the permanent of a matrix and the distribution of first-passage time for a positive recurrent Markov chain. The present paper analyzes the properties of this estimator when each replication starts in an arbitrarily selected state. In particular, it describes a procedure for determining optimal warm-up intervals and optimal sample sizes to achieve a specified level of statistical accuracy at minimal cost. Also, it examines the variation in the optimal solution in response to changes in the parameters of the problem.
Approximation of the Mean Queue Length of an M/G/c Queueing System
Authors: Ma Bobby N. W. , Mark Jon W.
Published: November 2008

A relatively robust method for the approximate analysis of the mean queue length of an M/G/c queueing system is proposed. The approximation method is developed based on the following assumptions: the residual service time of one busy server is independent of those of the other busy servers, and the system in which all the servers are busy is treated in the same way as a single-server system with c times the service rate of one of the servers. The application of these two assumptions is coupled through the introduction of a parameter np. If the number of customers in the system is larger than np, assumption 2 is used; otherwise assumption 1 is used. We found that certain properties of np allow an estimation of the mean queue length of a large M/G/c queueing system through the approximate analysis of the mean queue length of a much smaller M/G/c queueing system. Numerical results show that the approximation is accurate even when the coefficient of variation of the service time and the number of channels of the system are as large as 20 and 200, respectively.
Polling, Greedy and Horizon Servers on a Circle
Authors: Harel Arie , Stulman Alan
Published: November 2008

Service in a loop-based polling system consists of a single server moving around a closed tour, stopping to perform services wherever requests are encountered. There are N stations (unit buffer queues) spaced one unit of distance apart, and the server moves at a unit speed. All queues are identical, and the service time is deterministic. We compare the two well known cyclic polling and greedy servers with a new control policy called the horizon server. The cyclic polling server moves in one direction, even if no requests are waiting, and stops whenever it encounters a request. The greedy server selects the nearest request for its next service. At any station the greedy server can reverse its direction if a new request arrives nearby, and if no requests are waiting the greedy server does not move. The horizon server, with parameter d, ignores all requests for service from a distance farther than d,. Within its horizon (≤ d) it acts like the greedy server. Analytical solutions for N = 2 and 3 and numerical results for N≤ 6 show that the horizon server, with the optimum value of d, outperforms the polling and the greedy servers.
An Efficient Algorithm for the Multiperiod Capacity Expansion of One Location in Telecommunications
Authors: Saniee Iraj
Published: November 2008

The minimum cost multiperiod capacity expansion of one location in telecommunications network planning can be formulated as a time-dependent knapsack problem. The problem consists of meeting integral demands at distinct time periods at minimum total discounted cost through a selection of items (with integral costs and capacities) from a collection of N distinct types of objects. This note presents an efficient pseudopolynomial time solution to this time-dependent knapsack problem. The technique involves an initial dynamic programming run with time complexity O(N(D + C)) followed by a shortest path algorithm with worst-case time complexity O(C2T) through a suitably defined network, where D and C are the maxima of the values of the demands and capacities, and T is the number of time periods to be considered. The application of this technique to the problem of optimal capacity expansion of one location in telecommunications network planning is described and computational results are reported.
A Decomposition Algorithm for Local Access Telecommunications Network Expansion Planning
Authors: Balakrishnan Anantaram , Magnanti Thomas L. , Wong Richard T.
Published: November 2008

Growing demand, increasing diversity of services, and advances in transmission and switching technologies are prompting telecommunication companies to rapidly expand and modernize their networks. This paper develops and tests a decomposition methodology to generate cost-effective expansion plans, with performance guarantees, for one major component of the network hierarchy—the local access network. The model captures economies of scale in facility costs and tradeoffs between installing concentrators and expanding cables to accommodate demand growth. Our solution method exploits the special tree and routing structure of the expansion planning problem to incorporate valid inequalities, obtained by studying the problem’s polyhedral structure, in a dynamic program which solves an uncapacitated version of the problem. Computational results for three realistic test networks demonstrate that our enhanced dynamic programming algorithm, when embedded in a Lagrangian relaxation scheme (with problem preprocessing and local improvement), is very effective in generating good upper and lower bounds: Implemented on a personal computer, the method generates solutions within 1.2–7.0% of optimality. In addition to developing a successful solution methodology for a practical problem, this paper illustrates the possibility of effectively combining decomposition methods and polyhedral approaches.
Analysis of Distribution Strategies in the Industrial Paper and Plastics Industry
Authors: Cohen Morris A. , Agrawal Narendra , Agrawal Vipul , Raman Ananth
Published: November 2008

The costs, benefits and strategic role of intermediate echelons in distribution networks are not well understood in many industries. This paper describes a study of such multilevel systems in the industrial paper and plastics industry. We quantify the impact of redistributors, who buy products from manufacturers and sell them exclusively to other distributors. The methodology was applied to an industry-wide study. We derived statistics based on optimal distributor policies for channel choice and stock control. Based on our analysis, we found that effective use of redistribution, in conjunction with these policies, has the potential to generate savings of $446 million for the industry.
Optimal Control of Arrivals to Token Ring Networks with Exhaustive Service Discipline
Authors: Tseng Kent H. , Hsiao Man-Tung T.
Published: November 2008

The optimal control of arrivals to a two-station token ring network is analyzed in this paper. By adopting a maximum system throughput under a system time-delay constraint optimality criterion, we study a network optimality problem with the assumption that both stations have global information (i.e., the number of packets at each station). The controlled arrivals are assumed to be state-dependent Poisson streams and have exponentially distributed service time. The optimality problem will be formulated using dynamic programming with a convex cost function. Combining with duality theory, we then show that the optimal control is almost bang-bang and in the special case when both queues have the same service rate and sufficiently large buffers, the optimal control is further shown to be switchover. A nonlinear program is used to numerically determine the optimal local control for the purpose of comparison. The results obtained under global and local information can be used to provide a measure of the tradeoff between maximum throughput efficiency and protocol complexity. Numerical examples illustrating the theoretical results are also provided.
Probability Models of Needle Exchange
Authors: Kaplan Edward H.
Published: November 2008

Needle exchange is an intervention for slowing HIV transmission among drug injectors. Most studies of needle exchange rely on changes in self-reported risky behaviors among program participants. This paper reports two models based on objectively observed operational data, such as needle distribution rates, client visit dates, needle circulation times, and the fraction of returned needles testing HIV positive. Application of the models to data from the New Haven needle exchange suggests that HIV transmission has been slowed significantly among program participants.
An Exact Algorithm for Maximum Entropy Sampling
Authors: Ko Chun-Wa , Lee Jon , Queyranne Maurice
Published: November 2008

We study the experimental design problem of selecting a most informative subset, having prespecified size, from a set of correlated random variables. The problem arises in many applied domains, such as meteorology, environmental statistics, and statistical geology. In these applications, observations can be collected at different locations, and possibly, at different times. Information is measured by “entropy.” In the Gaussian case, the problem is recast as that of maximizing the determinant of the covariance matrix of the chosen subset. We demonstrate that this problem is NP-hard. We establish an upper bound for the entropy, based on the eigenvalue interlacing property, and we incorporate this bound in a branch-and-bound algorithm for the exact solution of the problem. We present computational results for estimated covariance matrices that correspond to sets of environmental monitoring stations in the United States.
Bounds on Expected Project Tardiness
Authors: Birge John R. , Maddox Marilyn J.
Published: November 2008

A frequent goal in scheduling projects and production operations is determining the financial impact of project duration or production lead time. This paper considers net project value effects that increase proportionally to time in excess of a deadline. New bounds on the expected value of these tardiness costs are given. The bounds provide robust measurements without requiring extensive assumptions about activity distributions.
One-Attribute Sequential Assignment Match Processes in Discrete Time
Authors: David Israel , Yechiali Uri
Published: November 2008

We consider a sequential matching problem where M offers arrive in a random stream and are to be sequentially assigned to N waiting candidates. Each candidate, as well as each offer, is characterized by a random attribute drawn from a known discrete-valued probability distribution function. An assignment of an offer to a candidate yields a (nominal) reward R > 0 if they match, and a smaller reward r ≤ R if they do not. Future rewards are discounted at a rate 0 ≤ α ≤ 1. We study several cases with various assumptions on the problem parameters and on the assignment regime and derive optimal policies that maximize the total (discounted) reward. The model is related to the problem of donor-recipient assignment in live organ transplants, studied in an earlier work.
A Time Window Approach to Simultaneous Scheduling of Machines and Material Handling System in an FMS
Authors: Bilge Ümit , Ulusoy Gündüz
Published: November 2008

This paper exploits the interactions between the machine scheduling and the scheduling of the material handling system in an FMS by addressing them simultaneously. The material transfer between machines is done by a number of identical automated guided vehicles (AGVs) which are not allowed to return to the load/unload station after each delivery. This operating policy introduces an additional complexity to the problem because it results in sequence-dependent travel times for the deadheading trips between successive loaded trips of the AGVs. The problem is formulated as a nonlinear mixed integer programming model. Its objective is makespan minimization. The formulation consists of constraint sets of a machine scheduling subproblem and a vehicle scheduling subproblem which interact through a set of time window constraints for the material handling trip starting times. An iterative procedure is developed where, at each iteration, a new machine schedule is generated by a heuristic procedure, the operation completion times obtained from this schedule are used to construct time windows for the trips, and a feasible solution is searched for the second subproblem, which is handled as a sliding time window problem. The procedure is numerically tested on 90 example problems.