Decentralized planning has long been recognized as an important decision making problem. Many approaches based on the concepts of large-scale system decomposition have generally lacked the ability to model the type of truly independent subsystems which often exist in practice. Multilevel programming models partition control over decision variables among ordered levels within a hierarchical planning structure. A planner at one level of the hierarchy may have his objective function and set of feasible decisions determined, in part, by other levels. However, his control instruments may allow him to influence the policies at other levels and thereby improve his own objective function. This paper examines the special case of the two-level linear programming problem. Geometric characterizations and algorithms are presented with some examples. The goal is to demonstrate the tractability of such problems and motivate a wider interest in their study.

Decentralized planning has long been recognized as an important decision making problem. Many approaches based on the concepts of large scale system decomposition have generally lacked the ability to model the type of truly independent subsystems which have often existed in practice. Similarly, tractable game-theoretic approaches have not allowed for a continuous solution space in which one player's decision restricts the feasible choices of another. This correspondence offers a formulation to help model this type of decision making hierarchy. Characterizations and algorithmic approaches for a class of two-level problems are discussed.

Automated guided vehicles (AGVs) are a highly sophisticated and increasingly popular type of material handling device in flexible manufacturing systems. This paper details solution methodologies for the static routing problem in which demand assignment of the AGVs are known; the focus is to obtain an implementable solution within a reasonable amount of computer time. The objective is to minimize the makespan, while routing AGVs on a bidirectional network in a conflict-free manner. This problem is solved via column generation. The master problem in this column generation procedure has the makespan and vehicle interference constraints. Columns in the master problem are routes iteratively generated for each AGV. The subproblem is a constrained shortest path problem with time-dependent costs on the edges. An improvement procedure is developed to better the solution obtained at the end of the master-subproblem interactions. Several methods of iterating between the master and subproblem are experimented with in-depth computational experiments. Our empirical results indicate that the procedure as a whole usually generates solutions that are within a few percent of a proposed bound, within reasonable computer time.

In this paper we develop a new conditional penalty for the fixed charge transportation problem. This penalty is stronger than both the Driebeek penalties and the Lagrangean penalties of Cabot and Erenguc. Computational testing shows that the use of these penalties leads to significant reductions in enumeration and solution times for difficult problems in the size range tested. We also study the effect of problem parameters on the difficulty of the problem. The ratio of fixed charges to variable costs, the shape of the problem, arc density in the underlying network and fixed charge arc density are shown to have a significant effect on problem difficulty for problems involving up to 40 origins and 40 destinations.

In this paper, we develop a Lagrangean relaxation-based heuristic procedure to generate near-optimal solutions to very-large-scale capacitated lot-sizing problems (CLSP) with setup times and limited overtime. Our computational results show that large problems involving several thousand products and several thousand 0/1 integer variables can be solved in a reasonable amount of computer time to within one percent of their optimal solution. The proposed procedure is general enough to be applied directly or with slight modification to real-life production problems.