A generalized assignment model for dynamic supply chain capacity planning

We consider a generalization of the well‐known generalized assignment problem (GAP) over discrete time periods encompassed within a finite planning horizon. The resulting model, MultiGAP, addresses the assignment of tasks to agents within each time period, with the attendant single‐period assignment costs and agent‐capacity constraint requirements, in conjunction with transition costs arising between any two consecutive periods in which a task is reassigned to a different agent. As is the case for its single‐period antecedent, MultiGAP offers a robust tool for modeling a wide range of capacity planning problems occurring within supply chain management. We provide two formulations for MultiGAP and establish that the second (alternative) formulation provides a tighter bound. We define a Lagrangian relaxation‐based heuristic as well as a branch‐and‐bound algorithm for MultiGAP. Computational experience with the heuristic and branch‐and‐bound algorithm on over 2500 test problems is reported. The Lagrangian heuristic consistently generates high‐quality and in many cases near‐optimal solutions. The branch‐and‐bound algorithm is also seen to constitute an effective means for solving to optimality MultiGAP problems of reasonable size. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

Analysis of a new vehicle scheduling and location problem

We consider a container terminal discharging containers from a ship and locating them in the terminal yard. Each container has a number of potential locations in the yard where it can be stored. Containers are moved from the ship to the yard using a fleet of vehicles, each of which can carry one container at a time. The problem is to assign each container to a yard location and dispatch vehicles to the containers so as to minimize the time it takes to download all the containers from the ship. We show that the problem is NP‐hard and develop a heuristic algorithm based on formulating the problem as an assignment problem. The effectiveness of the heuristic is analyzed from both worst‐case and computational points of view. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 363–385, 2001     

The shortest queue model with jockeying

In this article we deal with the shortest queue model with jockeying. We assume that the arrivals are Poisson, each of the exponential servers has his own queue, and jockeying among the queues is permitted. Explicit solutions of the equilibrium probabilities, the expected customers, and the expected waiting time of a customer in the system are given, which only depend on the traffic intensity. Numerical results can be easily obtained from our solutions. Several examples are provided in the article.     

A differential equation model of search for randomly arriving and departing targets

In this paper we analyze optimal search strategies in an environment in which multiple, independent targets arrive and depart at random. The analysis revolves around a continuous time differential equation model which captures the time dependent nature of the search process. We explore the impact on optimal strategies of nonzero travel times between regions as well as differing target arrival rates. We derive simple closed form expressions for determining if only one region should be searched.     

Bounds on the availability function

This paper gives bounds on the availability function for an alternating renewal process with exponential failure and general repair times. A bound on the error is also given. Several of the bounds with greatest practical consequence are worked out and illustrated. Repair distributions for which a lower bound on availability is easily computed are gamma (integer shape parameter), log normal, and Weibull. Finally, some simulation results for log normal repair versus gamma repair are given.     

Economic lot scheduling of fully loaded processes with external setups

Without restricting the class of permissible schedules, we derive optimal schedules for economic lot scheduling problems that are fully loaded, have external setups, and have only two products. The fully loaded condition accurately represents certain types of bottlenecks. We show that the optimal schedule must have the Wagner-Whitin property. We also develop a measure of aggregate inventory, derive an optimal steady-state aggregate inventory policy, and provide conditions under which the aggregate inventory level of an optimal schedule must approach a steady state. By restricting the class of permissible schedules to rotation cycle schedules, we extend these results to more than two products.     

Dominating sets for rectilinear center location problems with polyhedral barriers

In planar location problems with barriers one considers regions which are forbidden for the siting of new facilities as well as for trespassing. These problems are important since they model various actual applications. The resulting mathematical models have a nonconvex objective function and are therefore difficult to tackle using standard methods of location theory even in the case of simple barrier shapes and distance functions. For the case of center objectives with barrier distances obtained from the rectilinear or Manhattan metric, it is shown that the problem can be solved in polynomial time by identifying a dominating set. The resulting genuinely polynomial algorithm can be combined with bound computations which are derived from solving closely connected restricted location and network location problems. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 647–665, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10038