This paper is concerned with the following problem in network synthesis. Suppose that we are given a network with real-valued capacities on each arc. There is a cost associated with each arc which is proportional to the magnitude of the arc capacity. We wish to determine new arc capacities such...

This paper generalizes the selection problem discussed by J. M. Rhys [Rhys, J. M. W. 1970. Shared fixed cost and network flows. Management Sci. 17 (3, November).], J. D. Murchland [Murchland, J. D. 1968. Rhys's combinatorial station selection problem. London Graduate School of Business Studies,...

The determination of an optimal strategy for reinforcing arcs and nodes in a multi-commodity network is discussed. This strategy will maximize the effort required by an attacker to render the network useless. Under certain assumptions this problem is shown to be equivalent to the problem of...

Some new properties associated with the special class of integer programs known as weighted set covering problems are derived. While it is well known that an optimal integer solution to the set covering problem is a basic feasible solution to the corresponding linear program, we show that there...

This paper addresses duration-of-stay-based shared storage policies for a unit load warehouse. We show that, for single command storage and retrieval, shared storage policies based on duration of stay of individual unit loads have the potential to significantly decrease travel time. An optimal...

Many important problems can be modeled as dynamic (time-expanded) network flow problems. For example, in building evacuation we might use twenty nodes to represent a room at 3 minute intervals over an hour, and use arcs to indicate the feasible passages, over time, among the various rooms. The...

Integer linear programs with 0-1 constraint matrices arise frequently in scheduling and staffing models. For many such problems it is natural to model processor availability by columns of the constraint matrix, where 1's indicate processor availability for production and 0's indicate idle...

A multi-product, multi-facility production scheduling problem is considered over a finite planning horizon. The horizon consists of discrete production periods during each of which at most one product can be assigned to each facility. Product demand rates are assumed to be constant over a period...

A guaranteed time distribution system is organized so that movement of items between any source-destination pair (serviced by the system) is completed within a guaranteed period of time (T). Various express mail services are examples of such distribution systems. The movement of items between...

The n most vital links of a flow network are defined as those n arcs whose simultaneous removal from the network causes the greatest decrease in the throughput capability of the remaining system between a specified pair of nodes. These n arcs are shown to be the n largest capacity arcs in a...