Applications – OR and Management Sciences

A Two-Stage Stochastic Integer Programming Approach to Integrated Staffing and Scheduling with Application to Nurse Management

Categories (Mixed) Integer Nonlinear Programming, Scheduling, Stochastic Programming Tags , , , , ,

We study the problem of integrated staffing and scheduling under demand uncertainty. The problem is formulated as a two-stage stochastic integer program with mixed-integer recourse. The here-and-now decision is to find initial staffing levels and schedules, well ahead in time. The wait-and-see decision is to adjust these schedules at a time epoch closer to the … Read more

Models and Solution Techniques for Production Planning Problems with Increasing Byproducts

Categories Applications - OR and Management Sciences, Chemical Engineering, Facility Planning and Design Tags , ,

We consider a production planning problem where the production process creates a mixture of desirable products and undesirable byproducts. In this production process, at any point in time the fraction of the mixture that is an undesirable byproduct increases monotonically as a function of the cumulative mixture production up to that time. The mathematical formulation … Read more

Uniqueness Conditions for A Class of $\ell_0hBcMinimization Problems

Categories Applications - OR and Management Sciences, Applications - Science and Engineering, Data-Mining Tags ,

We consider a class of $\ell_0$-minimization problems, which is to search for the partial sparsest solution to an underdetermined linear system with additional constraints. We introduce several concepts, including $l_p$-induced quasi-norm ($0

Worst-Case Performance Analysis of Some Approximation Algorithms for Minimizing Makespan and Flow-Time

Categories Approximation Algorithms, Scheduling Tags , , ,

In 1976, Coffman and Sethi conjectured that a natural extension of LPT list scheduling to the bicriteria scheduling problem of minimizing makespan over flowtime optimal schedules, called LD algorithm, has a simple worst-case performance bound: (5m-2)/(4m-1) , where m is the number of machines. We study structure of potential minimal counterexamples to this conjecture and … Read more

An Improvised Approach to Robustness in Linear Optimization

Categories Applications - OR and Management Sciences, Robust Optimization Tags ,

We treat uncertain linear programming problems by utilizing the notion of weighted analytic centers and notions from the area of multi-criteria decision making. In addition to many practical advantages, due to the flexibility of our approach, we are able to prove that the robust optimal solutions generated by our algorithms are at least as desirable … Read more

Polynomial time algorithms for the Minimax Regret Uncapacitated Lot Sizing Model

Categories Production and Logistics, Robust Optimization Tags , , ,

We study the Minimax Regret Uncapacitated Lot Sizing (MRULS) model, where the production cost function and the demand are subject to uncertainty. We propose a polynomial time algorithm which solves the MRULS model in O(n^6) time. We improve this running time to O(n^5) when only the demand is uncertain, and to O(n^4) when only the … Read more

Approaches to a real-world train timetabling problem in a railway node

Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Transportation Tags , , ,

We consider the Train Timetabling Problem (TTP) in a railway node (i.e. a set of stations in an urban area interconnected by tracks), which calls for determining the best schedule for a given set of trains during a given time horizon, while satisfying several track operational constraints. In particular, we consider the context of a … Read more

Decision Making Based on a Nonparametric Shape-Preserving Perturbation of a Reference Utility Function

Categories Finance and Economics, Robust Optimization, Stochastic Programming Tags , , , ,

This paper develops a robust optimization based decision-making framework using a nonparametric perturbation of a reference utility function. The perturbation preserves the risk-aversion property but solves the problem of ambiguity and inconsistency in eliciting the reference utility function. We study the topology of the perturbation, and show that in the decision-making framework the price of … Read more

Performance Analysis of Content-Centric and Content-Delivery Networks with Evolving Object Popularity

Categories Network Optimization, Telecommunications Tags , , ,

The Internet is currently mostly exploited as a means to perform massive digital content distribution. Such a usage profile was not specifically taken into account while initially designing the architecture of the network: as a matter of fact, the Internet was instead conceived around the concept of host-to-host communications between two remote machines. To solve … Read more

Survivable Network Coding

Categories Linear Programming, Network Optimization, Telecommunications

Given a telecommunication network, modeled by a graph with capacities, we are interested in comparing the behavior and usefulness of two information propagation schemes, namely multicast and network coding, when the aforementioned network is subject to single arc failure. We consider the case with a single source node and a set of terminal nodes. The … Read more