Maximum flows in generalized processing networks

Processing networks (cf. Koene in Minimal cost flow in processing networks: a primal approach, 1982) and manufacturing networks (cf. Fang and Qi in Optim Methods Softw 18:143–165, 2003) are well-studied extensions of traditional network flow problems that allow to model the decomposition or distillation of products in a manufacturing process. In these models, so called flow ratios \(\alpha _e \in [0,1]\) are assigned to all outgoing edges of special processing nodes. For each such special node, these flow ratios, which are required to sum up to one, determine the fraction of the total outgoing flow that flows through the respective edges. In this paper, we generalize processing networks to the case that these flow ratios only impose an upper bound on the respective fractions and, in particular, may sum up to more than one at each node. We show that a flow decomposition similar to the one for traditional network flows is possible and can be computed in strongly polynomial time. Moreover, we show that there exists a fully polynomial-time approximation scheme (FPTAS) for the maximum flow problem in these generalized processing networks if the underlying graph is acyclic and we provide two exact algorithms with strongly polynomial running-time for the problem on series–parallel graphs. Finally, we study the case of integral flows and show that the problem becomes \({\mathcal {NP}}\)-hard to solve and approximate in this case.     

Revised GRASP with path-relinking for the linear ordering problem

The linear ordering problem (LOP) is an NP\mathcal{NP}-hard combinatorial optimization problem with a wide range of applications in economics, archaeology, the social sciences, scheduling, and biology. It has, however, drawn little attention compared to other closely related problems such as the quadratic assignment problem and the traveling salesman problem. Due to its computational complexity, it is essential in practice to develop solution approaches to rapidly search for solution of high-quality. In this paper we propose a new algorithm based on a greedy randomized adaptive search procedure (GRASP) to efficiently solve the LOP. The algorithm is integrated with a Path-Relinking (PR) procedure and a new local search scheme. We tested our implementation on the set of 49 real-world instances of input-output tables (LOLIB instances) proposed in Reinelt (Linear ordering library (LOLIB) 2002). In addition, we tested a set of 30 large randomly-generated instances proposed in Mitchell (Computational experience with an interior point cutting plane algorithm, Tech. rep., Mathematical Sciences, Rensellaer Polytechnic Institute, Troy, NY 12180-3590, USA 1997). Most of the LOLIB instances were solved to optimality within 0.87 seconds on average. The average gap for the randomly-generated instances was 0.0173% with an average running time of 21.98 seconds. The results indicate the efficiency and high-quality of the proposed heuristic procedure.     

A linear programming duality approach to analyzing strictly nonblocking <Emphasis Type="Italic">d</Emphasis>-ary multilog networks under general crosstalk constraints

When a switching network topology is used for constructing optical cross-connects, as in the circuit switching case, no two routes are allowed to share a link. However, if two routes share too many switching elements, then crosstalk introduced at those switching elements degrades signal quality. Vaez and Lea (IEEE Trans. Commun. 48:(2)316–323, 2000) introduced a parameter c which is the maximum number of distinct switching elements a route can share with other routes in the network. This is called the general crosstalk constraint. This paper presents a new method of analyzing strictly nonblocking multi-log networks under this general crosstalk constraint using linear programming duality.     

Improving an exact approach for solving separable integer quadratic knapsack problems

We consider the specially structured (pure) integer Quadratic Multi-Knapsack Problem (QMKP) tackled in the paper “Exact solution methods to solve large scale integer quadratic knapsack problems” by D. Quadri, E. Soutif and P. Tolla (2009), recently appeared on this journal, where the problem is solved by transforming it into an equivalent 0–1 linearized Multi-Knapsack Problem (MKP). We show that, by taking advantage of the structure of the transformed (MKP), it is possible to derive an effective variable fixing procedure leading to an improved branch-and-bound approach. This procedure reduces dramatically the resulting linear problem size inducing an impressive improvement in the performances of the related branch and bound approach when compared to the results of the approach proposed by D. Quadri, E. Soutif and P. Tolla.     

Labour Flows as Determinants of the Wage–Price Spiral: An Empirical Analysis for The Netherlands

This study presents an empirical analysis of the influence of labour market flows on wage and price formation. A system of wage, price and employment equations after Nickell (Oxford Bulletin of Economics and Statistics 49: 103–128, 1987) is estimated, including labour flows as indicators of labour market tightness in the wage equation. An impulse response analysis using this system shows how changes in the flow of layoffs (flow from employment to unemployment) may be the basis of short‐run Phillips curve effects in The Netherlands     

A taxonomy of international manufacturing networks

Abstract

Manufacturing firms with multiple product groups do not need to involve all factories in the production of all product groups. Some factories may specialize on a small set of products, while others participate in the manufacturing of a broader set of products. However, current theories on international manufacturing networks do not explain in detail how organizations design international manufacturing networks for different products or product groups involving different sets of factories. This research investigates 20 product group networks at five global manufacturing firms. We distinguish between three types of factories: component manufacturing factories, assembly factories, and integrated factories (having both component manufacturing and assembly). Furthermore, we identify four network types: linear, divergent, convergent, and mixed structures. These four types exhibit distinctly different characteristics in terms of key characteristics, factory roles, product types, process types, market types, sourcing, and key managerial challenges. Most networks are relatively small – on an average consisting of four factories and some contain a number of subnetworks that are self-sufficient in terms of material flow and serve separate market regions. We identify two new types of factory roles related to component manufacturing competences, which we call ‘strategic feeder’ and ‘full lead’.     

Subhypergraph counts in extremal and random hypergraphs and the fractional <Emphasis Type="Italic">q</Emphasis>-independence

We study the extremal parameter N(n,m,H) which is the largest number of copies of a hypergraph H that can be formed of at most n vertices and m edges. Generalizing previous work of Alon (Isr. J. Math. 38:116–130, 1981), Friedgut and Kahn (Isr. J. Math. 105:251–256, 1998) and Janson, Oleszkiewicz and the third author (Isr. J. Math. 142:61–92, 2004), we obtain an asymptotic formula for N(n,m,H) which is strongly related to the solution α _q (H) of a linear programming problem, called here the fractional q-independence number of H. We observe that α _q (H) is a piecewise linear function of q and determine it explicitly for some ranges of q and some classes of H. As an application, we derive exponential bounds on the upper tail of the distribution of the number of copies of H in a random hypergraph.     

SIRALINA: efficient two-steps heuristic for storage optimisation in single period task scheduling

In this paper, we study the general problem of one-dimensional periodic task scheduling under storage requirement, irrespective of machine constraints. We have already presented in (Touati and Eisenbeis, Parallel Process. Lett. 14(2):287–313, 2004) a theoretical framework that allows an optimal optimisation of periodic storage requirement in a cyclic schedule. Since our optimisation problem is NP-hard (Touati, PhD thesis, 2002), solving an exact integer linear programming formulation is too expensive in practice. In this article, we propose an efficient two-steps heuristic using model’s properties that allows fast computation times while providing highly satisfactory results. This method includes the solution of an integer linear program with a totally unimodular constraints matrix in first step, then the solution of a linear assignment problem. Our heuristic is implemented for an industrial compiler for embedded VLIW processors.     

A multi-criteria approach to fair and efficient bandwidth allocation

In systems which serve many users there is a need to respect some fairness rules while looking for the overall efficiency. This applies among others to network design where a central issue is how to allocate bandwidth to flows efficiently and fairly. The so-called max–min fairness is widely used to meet these goals. However, allocating the bandwidth to optimize the worst performance may cause a large worsening of the overall throughput of the network. In this paper we show how the concepts of mult-criteria equitable optimization can effectively be used to generate various fair and efficient allocation schemes. We introduce a multi-criteria model equivalent to equitable optimization and we develop a corresponding reference point procedure to generate fair and efficient bandwidth allocations. Our analysis is focused on the nominal network design for elastic traffic that is currently the most significant traffic of IP networks. The procedure is tested on a sample network dimensioning problem for elastic traffic and its abilities to model various preferences are demonstrated.     

Restarting after Branching in the SDP Approach to MAX-CUT and Similar Combinatorial Optimization Problems

Many combinatorial optimization problems have relaxations that are semidefinite programming problems. In principle, the combinatorial optimization problem can then be solved by using a branch-and-cut procedure, where the problems to be solved at the nodes of the tree are semidefinite programs. It is desirable that the solution to one node of the tree should be exploited at the child node in order to speed up the solution of the child. We show how the solution to the parent relaxation can be used as a warm start to construct an appropriate initial dual solution to the child problem. This restart method for SDP branch-and-cut can be regarded as analogous to the use of the dual simplex method in the branch-and-cut method for mixed integer linear programming problems.     

Robust Structural Equations for Designing and Monitoring Strategic International Facility Networks

Using predictive global sensitivity analysis, we develop a structural equations model to abstract from the details of a large‐scale mixed integer program (MIP) to capture essential design trade‐offs of global manufacturing and distribution networks. We provide a conceptual framework that describes a firm's network structure along three dimensions: market focus, plant focus, and network dispersion. Normalized dependent variables are specified that act as proxies for a company's placement into our conceptual network classification via the calculation of just a few key independent variables. We provide robust equation sets for eight cost structure clusters. Many different product types could be classified into one of these groups, which would allow managers to use the equations directly without needing to run the MIP for themselves. Our numerical tests suggest that the formulas representing the network structure drivers—economies of scale, complexity costs, transportation costs, and tariffs—may be sufficient for managers to design their strategic network structures, and perhaps more importantly, to monitor them over time to detect potential need for adjustment.     

Optimal all-to-all personalized exchange in d-nary banyan multistage interconnection networks

All-to-all personalized exchange occurs in many important applications in parallel processing. In the past two decades, algorithms for all-to-all personalized exchange were mainly proposed for hypercubes, meshes, and tori. Recently, Yang and Wang (IEEE Trans Parallel Distrib Syst 11:261–274, 2000) proposed an optimal all-to-all personalized exchange algorithm for binary (each switch is of size 2×2) banyan multistage interconnection networks. It was pointed out in Massini (Discret Appl Math 128:435–446, 2003) that the algorithm in Yang, Wang (IEEE Trans Parallel Distrib Syst 11:261–274, 2000) depends on the network topologies and requires pre-computation and memory allocation for a Latin square. Thus in (Discret Appl Math 128:435–446, 2003), Massini proposed a new optimal algorithm, which is independent of the network topologies and does not require pre-computation or memory allocation for a Latin square. Unfortunately, Massini’s algorithm has a flaw and does not realize all-to-all personalized exchange. In this paper, we will correct the flaw and generalize Massini’s algorithm to be applicable to d-nary (each switch is of size d×d) banyan multistage interconnection networks. Dedicated to Professor Frank K. Hwang on the occasion of his 65th birthday. This research was partially supported by the National Science Council of the Republic of China under the grant NSC94-2115-M-009-006.     

Flow sensors in newspaper production

The paper evaluates potential savings in a newspaper production operation achieved by reducing errors in flow sensor counts at stackers, where newspaper bundles are made for distribution to customers. The reduction in count errors is achieved by installing extra flow sensors at various transfer points in the production flow network and using their counts along with using the deducible information from flow conservation equations.As the product flows in the production network, more diversity within the product line is introduced due to variations in inserts. Stop rules for a product inflowing into multiple reservoirs are developed which would minimize expected over production. More precise projections for product completion times are generated, which allow timely corrective actions.State sensors are installed, which give real time information about state of each equipment as to whether it is in an operational or failed mode. Knowledge of the state of the system provides ability to promptly generate, on a real time basis, alternative system configuration substituting redundant operational units for the failed units.     

An Entropy Measure of Flow Dominance for Predicting Operations Performance

The flow of jobs within a system is an important operating characteristic that influences system performance. While the majority of previous studies on manufacturing performance consider product flows only as an implicit parameter of the design, we introduce an explicit measure of flow dominance based on entropy and test its efficacy in predicting the performance of manufacturing systems. In computing entropy flow dominance (EFD), we aggregate information embedded in the routings of all products within a system into a single measure. EFD is designed to indicate on a 0–1 scale the level of flow dominance, where 1 represents a pure flow shop and 0 represents a pure job shop. The result is a simple measure that provides managers a way to explain and predict complex phenomena. Our experimental results indicate that EFD is a statistically significant determinant of manufacturing system performance. Furthermore, the model including EFD as an independent variable accurately predicts manufacturing system performance as measured by job flow time, flow time standard deviation, and work in process. We note that the same results can also apply to service systems, such as the “back‐room” low‐contact type systems, that have similar characteristics as manufacturing systems.     

Modeling Network Management: An Examination of Internal and External Strategies

Within the last decade scholars have begun to emphasize the importance of exploring management within an inter-organizational context (O’Toole and Laurence Public Administration Review 57(1):45-52, 1997; Agranoff and McGuire 1999; O’Toole and Meier Journal of Public Administration Research and Theory 9(4): 505-526, 1999). These studies have demonstrated the importance of network management on organizational performance. However, McGuire (2002) argues that the literature on networking does not demonstrate the intricate activities of network management that lead to increased performance, asserting case studies are necessary to achieve this goal. This work uses large-n data and presents the concepts of internal and external networking as a framework for understanding how network management contributes to improved organizational performance.     

产品回收逆向物流网络优化设计模型

为了在传统正向物流网络基础上扩建产品回收逆向物流网络,基于混合整数线性规划方法建立了一种单产品、有能力限制的产品回收逆向物流网络优化设计模型,据此确定物流网络中各种设施的数量和位置,并在由此构成的各条物流路径上合理分配物流量,以使各种设施的投资和运营成本之和最小。给出了提高模型求解效率的Benders分解算法,并通过算例验证了模型和算法的有效性。     

Who's Who in Networks. Wanted: The Key Player

Finite population noncooperative games with linear‐quadratic utilities, where each player decides how much action she exerts, can be interpreted as a network game with local payoff complementarities, together with a globally uniform payoff substitutability component and an own‐concavity effect. For these games, the Nash equilibrium action of each player is proportional to her Bonacich centrality in the network of local complementarities, thus establishing a bridge with the sociology literature on social networks. This Bonacich–Nash linkage implies that aggregate equilibrium increases with network size and density. We then analyze a policy that consists of targeting the key player, that is, the player who, once removed, leads to the optimal change in aggregate activity. We provide a geometric characterization of the key player identified with an intercentrality measure, which takes into account both a player's centrality and her contribution to the centrality of the others.     

New combinatorial structures with applications to efficient group testing with inhibitors

Group testing with inhibitors (GTI) is a variant of classical group testing where in addition to positive items and negative items, there is a third class of items called inhibitors. In this model the response to a test is YES if and only if the tested group of items contains at least one positive item and no inhibitor. This model of group testing has been introduced by Farach et al. (Proceedings of compression and complexity of sequences, pp 357–367, 1997) for applications in the field of molecular biology. In this paper we investigate the GTI problem both in the case when the exact number of positive items is given, and in the case when the number of positives is not given but we are provided with an upper bound on it. For the latter case, we present a lower bound on the number of tests required to determine the positive items in a completely nonadaptive fashion. Also under the same hypothesis, we derive an improved lower bound on the number of tests required by any algorithm (using any number of stages) for the GTI problem. As far as it concerns the case when the exact number of positives is known, we give an efficient trivial two-stage algorithm. Instrumental to our results are new combinatorial structures introduced in this paper. In particular we introduce generalized versions of the well known superimposed codes (Du, D.Z., Hwang, F.K. in Pooling designs and nonadaptive group testing, 2006; Dyachkov, A.G., Rykov, V.V. in Probl. Control Inf. Theory 12:7–13, 1983; Dyachkov, A.G., et al. in J. Comb. Theory Ser. A 99:195–218, 2002; Kautz, W.H., Singleton, R.R. in IEEE Trans. Inf. Theory 10:363–377, 1964) and selectors (Clementi, A.E.F, et al. in Proceedings of symposium on discrete algorithms, pp. 709–718, 2001; De Bonis, A., et al. in SIAM J Comput. 34(5):1253–1270, 2005; Indyk, P. in Proceedings of symposium on discrete algorithms, pp. 697–704, 2002) that we believe to be of independent interest.