Heuristics for the multi‐resource generalized assignment problem

The well‐known generalized assignment problem (GAP) involves the identification of a minimum‐cost assignment of tasks to agents when each agent is constrained by a resource in limited supply. The multi‐resource generalized assignment problem (MRGAP) is the generalization of the GAP in which there are a number of different potentially constraining resources associated with each agent. This paper explores heuristic procedures for the MRGAP. We first define a three‐phase heuristic which seeks to construct a feasible solution to MRGAP and then systematically attempts to improve the solution. We then propose a modification of the heuristic for the MRGAP defined previously by Gavish and Pirkul. The third procedure is a hybrid heuristic that combines the first two heuristics, thus capturing their relative strengths. We discuss extensive computational experience with the heuristics. The hybrid procedure is seen to be extremely effective in solving MRGAPs, generating feasible solutions to more than 99% of the test problems and consistently producing near‐optimal solutions. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 468–483, 2001     

Scheduling multiple products on parallel machines with setup costs

We consider a class of production scheduling models with m identical machines in parallel and k different product types. It takes a time p_i to produce one unit of product type i on any one of the machines. There is a demand stream for product type i consisting of n_i units with each unit having a given due date. Before a machine starts with the production of a batch of products of type i a setup cost c is incurred. We consider several different objective functions. Each one of the objective functions has three components, namely a total setup cost, a total earliness cost, and a total tardiness cost. In our class of problems we find a relatively large number of problems that can be solved either in polynomial time or in pseudo‐polynomial time. The polynomiality or pseudo‐polynomiality is achieved under certain special conditions that may be of practical interest; for example, a regularity pattern in the string of due dates combined with earliness and tardiness costs that are similar for different types of products. The class of models we consider includes as special cases discrete counterparts of a number of inventory models that have been considered in the literature before, e.g., Wagner and Whitin (Manage Sci 5 (1958), 89–96) and Zangwill (Oper Res 14 (1966), 486–507; Manage Sci 15 (1969), 506–527). © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Scheduling parallel machines with inclusive processing set restrictions

We consider the problem of assigning a set of jobs to different parallel machines of the same processing speed, where each job is compatible to only a subset of those machines. The machines can be linearly ordered such that a higher‐indexed machine can process all those jobs that a lower‐indexed machine can process. The objective is to minimize the makespan of the schedule. This problem is motivated by industrial applications such as cargo handling by cranes with nonidentical weight capacities, computer processor scheduling with memory constraints, and grades of service provision by parallel servers. We develop an efficient algorithm for this problem with a worst‐case performance ratio of + ε, where ε is a positive constant which may be set arbitrarily close to zero. We also present a polynomial time approximation scheme for this problem, which answers an open question in the literature. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Factors that affect the optimal amount of central control in complex systems

Whereas much of the previous research in complex systems has focused on emergent properties resulting from self‐organization of the individual agents that make up the system, this article studies one vital role of central organization. In particular, four factors are conjectured to be key in determining the optimal amount of central control. To validate this hypothesis, these factors are represented as controllable parameters in a mathematical model. For different combinations of parameter values, the optimal amount of central control is found, either analytically or by computer simulation. The model is shown to provide results that match well with the level of control found across a broad spectrum of specific complex systems. This model also provides general guidelines as to how combinations of these factors affect the desirable level of control and specific guidelines for selecting and evaluating leaders. These results indicate that all of these factors, though not exhaustive, should be considered carefully when attempting to determine the amount of control that is best for a system. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

A vertex-closing approach to the p-center problem

This article uses a vertex-closing approach to investigate the p-center problem. The optimal set of vertices to close are found in imbedded subgraphs of the original graph. Properties of these subgraphs are presented and then used to characterize the optimal solution, to establish a priori upper and lower bounds, to establish refined lower bounds, and to verify the optimality of solutions. These subgraphs form the foundation of two polynomial algorithms of complexity O(|E| log |E|) and O(|E|²). The algorithms are proven to converge to an optimum for special cases, and computational evidence is provided which suggests that they produce very good solutions more generally. Both algorithms perform very well on problems where p is large relative to the number of vertices n, specifically, when p/n ≥ 0.30. One of the algorithms is especially efficient for solving a sequence of problems on the same graph.     

Do Distinct (National) Operational Styles of Conflict Resolution Exist?

This article contains a reply to a previously published paper on the use and abuse of the so-called Dutch approach to counterinsurgency. In addition to commenting on this paper, the article constitutes an argument to initiate more comparative studies in the field of military and strategic studies. Only comparative studies will help to better understand the effectiveness of military force in preventing, containing and solving violent conflicts.     

UNITED STATES—SOUTH AFRICA RELATION

Abstract

The article evaluates the security challenges that are likely to occur along international borders in East Africa with the advent of the East African Community Common Market in July 2010. In an attempt to illustrate the porosity of borders and the likelihood that criminals could take advantage of the situation, the author describes the ease with which transnational crime could thrive (in the absence of efficient border security measures) under the guise of informal cross-border trade that derives its basis largely from the customs and historical linkages in the region. Border towns in the region are considered zones of risk but also opportunities for quick money-making ventures and deals that tend to attract a variety of criminals. While the danger is not alarmingly high, there is a likelihood that with the opening up of the East African Community to the free movement of goods and people, criminals will exploit this freedom to commit crimes such as human trafficking, drug smuggling and moving terrorists and contraband goods unless mechanisms are put in place to curtail these activities. Should this not happen, the mission of the East African Community could be jeopardised.     

Aligning national “logics” in a European military helicopter program

This article analyzes the public side of the NH90 network consisting of four participating countries (Germany, France, Italy, and the Netherlands) and their industrial partners. Comparable to observations in earlier international projects in the defense sector, the development and production of the NH90 defense helicopter did not match original plans and costs estimates. On the basis of four mechanisms that were intended to facilitate the cooperation between the partnering countries (the General Memorandum of Understanding; coalition formation; the role of the central agency; and the process of vertical escalation) the question is posed whether or not there was a true alignment of national interests and “logics.” The lack of standardization, as well as program delays and issues concerning the division of the work-share, lead to the emerging alignment being characterized as “quasi-alignment” at best.     

Economic ordering decisions with market choice flexibility

Standard approaches to classical inventory control problems treat satisfying a predefined demand level as a constraint. In many practical contexts, however, total demand is comprised of separate demands from different markets or customers. It is not always clear that constraining a producer to satisfy all markets is an optimal approach. Since the inventory‐related cost of an item depends on total demand volume, no clear method exists for determining a market's profitability a priori, based simply on per unit revenue and cost. Moreover, capacity constraints often limit a producer's ability to meet all demands. This paper presents models to address economic ordering decisions when a producer can choose whether to satisfy multiple markets. These models result in a set of nonlinear binary integer programming problems that, in the uncapacitated case, lend themselves to efficient solution due to their special structure. The capacitated versions can be cast as nonlinear knapsack problems, for which we propose a heuristic solution approach that is asymptotically optimal in the number of markets. The models generalize the classical EOQ and EPQ problems and lead to interesting optimization problems with intuitively appealing solution properties and interesting implications for inventory and pricing management. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.