Worst‐case performance of approximation algorithms for tool management problems

Since the introduction of flexible manufacturing systems, researchers have investigated various planning and scheduling problems faced by the users of such systems. Several of these problems are not encountered in more classical production settings, and so‐called tool management problems appear to be among the more fundamental ones of these problems. Most tool management problems are hard to solve, so that numerous approximate solution techniques have been proposed to tackle them. In this paper, we investigate the quality of such algorithms by means of worst‐case analysis. We consider several polynomial‐time approximation algorithms described in the literature, and we show that all these algorithms exhibit rather poor worst‐case behavior. We also study the complexity of solving tool management problems approximately. In this respect, we investigate the interrelationships among tool management problems, as well as their relationships with other well‐known combinatorial problems such as the maximum clique problem or the set covering problem, and we prove several negative results on the approximability of various tool management problems. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 445–462, 1999     

Building Trust in the Mission Area: a Weapon Against Terrorism?

Military units on missions abroad face, among other challenges, terrorism. Terrorists are hard to recognize since they operate non-uniformed. Detection of terrorists in the area of operation can best be done by winning the trust of the local population, who can provide information. However, since the military rotates its units regularly, it is hard to build up a trusting relationship with the local population. Other players in the field of international operations are civil aid organisations. They remain in the area for a lengthy period of time, and often build up trusting relationships with the local population. Trust between civil aid organisations and the military is a triple edged sword, as it enables co-operation: the civil aid organisations get the protection they need from the military, the military gets the information it needs through civil aid organisations and the local population is supported in rebuilding society by repressing terrorism.     

HARNESSING GLOBAL TRADE DATA FOR BIOLOGICAL ARMS CONTROL

Unlike treaties dealing with nuclear and chemical weapons, the Biological Weapons Convention still lacks formal verification measures, 31 years after entering into force. Here we propose a global export-import monitoring system of biological dual-use items as an additional measure for a web of biological arms controls that could complement traditional export controls. We suggest that such a measure may help to guide consultation or verification processes in the biological area.     

Interval scheduling: A survey

In interval scheduling, not only the processing times of the jobs but also their starting times are given. This article surveys the area of interval scheduling and presents proofs of results that have been known within the community for some time. We first review the complexity and approximability of different variants of interval scheduling problems. Next, we motivate the relevance of interval scheduling problems by providing an overview of applications that have appeared in literature. Finally, we focus on algorithmic results for two important variants of interval scheduling problems. In one variant we deal with nonidentical machines: instead of each machine being continuously available, there is a given interval for each machine in which it is available. In another variant, the machines are continuously available but they are ordered, and each job has a given “maximal” machine on which it can be processed. We investigate the complexity of these problems and describe algorithms for their solution. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Framing Protest and Insurgency: Boko Haram and MASSOB in Nigeria

Why do some protest movements erupt into rebellion, whereas others protest peacefully under similar circumstances? Addressing this question, this paper investigates the cases of Boko Haram (rebellion) and MASSOB (non-violent protest) in contemporary Nigeria. Conventional explanations of rebellion focusing on opportunity, inequality, and repression cannot explain why these movements have pursued different protest strategies. This paper tries to explain this puzzle by investigating the signifying work and meaning construction of both movements drawing on the framing approach from social movement studies. The framing analysis shows that the different protest behavior largely results from the differing cultural context of both movements, from the agency of the framers, and from successful frame alignment, which results in frame resonance and, thereby, the successful mobilization for collective action.     

Group testing procedures with quantitative features and incomplete identification

We present a group testing model for items characterized by marker random variables. An item is defined to be good (defective) if its marker is below (above) a given threshold. The items can be tested in groups; the goal is to obtain a prespecified number of good items by testing them in optimally sized groups. Besides this group size, the controller has to select a threshold value for the group marker sums, and the target number of groups which by the tests are classified to consist only of good items. These decision variables have to be chosen so as to minimize a cost function, which is a linear combination of the expected number of group tests and an expected penalty for missing the desired number of good items, subject to constraints on the probabilities of misclassifications. We treat two models of this kind: the first one is based on an infinite population size, whereas the second one deals with the case of a finite number of available items. All performance measures are derived in closed form; approximations are also given. Furthermore, we prove monotonicity properties of the components of the objective function and of the constraints. In several examples, we study (i) the dependence of the cost function on the decision variables and (ii) the dependence of the optimal values of the decision variables (group size, group marker threshold, and stopping rule for groups classified as clean) and of the target functionals (optimal expected number of tests, optimal expected penalty, and minimal expected cost) on the system parameters.© 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Inventory pooling games for expensive,low‐demand spare parts

We consider several independent decision makers who stock expensive, low‐demand spare parts for their high‐tech machines. They can collaborate by full pooling of their inventories via free transshipments. We examine the stability of such pooling arrangements, and we address the issue of fairly distributing the collective holding and downtime costs over the participants, by applying concepts from cooperative game theory. We consider two settings: one where each party maintains a predetermined stocking level and one where base stock levels are optimized. For the setting with fixed stocking levels, we unravel the possibly conflicting effects of implementing a full pooling arrangement and study these effects separately to establish intuitive conditions for existence of a stable cost allocation. For the setting with optimized stocking levels, we provide a simple proportional rule that accomplishes a population monotonic allocation scheme if downtime costs are symmetric among participants. Although our whole analysis is motivated by spare parts applications, all results are also applicable to other pooled resource systems of which the steady‐state behavior is equivalent to that of an Erlang loss system. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

African nations as proxies in covert cyber operations

The growth of the African Internet, and services related to the Internet, has been rapid over the last decade. Following this market expansion, a variety of service providers have started to provide access. A fast-growing market puts pressure on the providers to deliver services first and only then seek to secure the networks. Over time, industrialised nations have become more able to detect and trace cyber attacks against their networks. These tracking features are constantly developing and the precision in determining the origin of an attack is increasing. A state-sponsored cyber attacker, such as intelligence agencies and electronic warfare units, will seek to avoid detection, especially when the attacks are politically sensitive intelligence-gathering and intrusion forays into foreign states' networks. One way for the attacker to create a path that links the attacks and the originating country is by actions through a proxy. The less technologically mature developing nations offer an opportunity for cyber aggression due to their lower level of security under the quick expansion of the Internet-based market. Developing countries could be used as proxies, without their knowledge and consent, through the unauthorised usage of these countries' information systems in an attempt to attack a third country by a state-sponsored offensive cyber operation. If the purpose of the cyber attack is to destabilise a targeted society and the attack succeeds, the used proxies are likely to face consequences in their relations with foreign countries, even if the proxy was unaware of the covert activity.     

About the contributors

From the beginning of history, war has been an almost exclusively male affair and those who took part in it were often extolled as the most manliest of men. The recent feminization of the armed forces of many developed countries does not prove that women's liberation is making progress, as most people believe. Rather, it is part symptom, part cause, of the decline of those forces. Other things being equal, the fewer and less important the wars fought by any armed force the more women it has; the more women it has, the less likely it is to undertake serious wars.     

Bounded flexibility in days‐on and days‐off scheduling

This article presents a flexible days‐on and days‐off scheduling problem and develops an exact branch and price (B&P) algorithm to find solutions. The main objective is to minimize the size of the total workforce required to cover time‐varying demand over a planning horizon that may extend up to 12 weeks. A new aspect of the problem is the general restriction that the number of consecutive days on and the number of consecutive days off must each fall within a predefined range. Moreover, the total assignment of working days in the planning horizon cannot exceed some maximum value. In the B&P framework, the master problem is stated as a set covering‐type problem whose columns are generated iteratively by solving one of three different subproblems. The first is an implicit model, the second is a resource constrained shortest path problem, and the third is a dynamic program. Computational experiments using both real‐word and randomly generated data show that workforce reductions up to 66% are possible with highly flexible days‐on and days‐off patterns. When evaluating the performance of the three subproblems, it was found that each yielded equivalent solutions but the dynamic program proved to be significantly more efficient. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 60: 678–701, 2013