We present a lagrangean heuristic based on the time-indexed formulation of the Single Machine Scheduling Problem with Release Dates. We observe that lagrangian relaxation of job constraints leads to a Weighted Stable Set problem on an Interval Graph. The problem is polynomially solvable by a dynamic programming algorithm. Computational experience is reported on instances up … Read more
In this note we present an improved approximation algorithm for the (uncapacitated) metric facility location problem. This algorithm uses the idea of cost scaling, the greedy algorithm of \cite{JMS}, and the greedy augmentation procedure of \cite{CG,GK}. Citation Working Paper, MIT and the University of Iowa Article Download View A 1.52-Approximation Algorithm for the Uncapacitated Facility … Read more
For a large number of applications Operations Research has a proven track record: it can deliver high quality solutions for planning problems. Important examples can be found in the airline industry, logistics and production management. This report will describe real-world examples of a novel way of applying Operations Research: As plans have to be adjusted … Read more
In 1961 Leon Steinberg formulated a “backboard wiring” problem that has resisted solution for 40 years. Steinberg’s wiring problem is to determine the locations of 34 computer components on a 4 by 9 grid so as to minimize the total length of the wiring required to interconnect them. The problem is an example of a … Read more
We introduce a new distribution center (DC) location model that incorporates working inventory and safety stock inventory costs at the distribution centers. In addition, the model incorporates transport costs from the suppliers to the DCs that explicitly reflect economies of scale through the use of a fixed cost term. The model is formulated as a … Read more
This paper addresses a multi-period investment model for capacity expansion in an uncertain environment. Using a scenario tree approach to model the evolution of uncertain demand and cost parameters, and fixed-charge cost functions to model the economies of scale in expansion costs, we develop a multi-stage stochastic integer programming formulation for the problem. A reformulation … Read more
Attempts at reducing the externalities of freight transport in Europe are generally focused on the incorporation of a more significant use of rail into freight itineraries. One new scenario for increasing the share of rail in intermodal transport involves the development of a dedicated subnetwork of freight rail lines. Within this European Union project, the … Read more