Two-Level Hierarchical Transportation Networks: A New Set of Problems and Practical Applications*

This paper defines and solves a set of new problems for two-level hierarchical transportation networks. Given a set of points, the objective is to find the path of a primary link such that a weighted sum of the lengths of the perpendiculars from each point to the primary link and the distance between the feet of the two extreme perpendiculars is minimized. The perpendiculars are the connecting or secondary links and the primary link could be a straight line or a curve. The paper provides an algorithm and computational results for the case in which the primary link is a straight line. Implementation approaches are also discussed.     

The optimum traversal of a graph

For a given graph (network) having costs [c_ij] associated with its links, the present paper examines the problem of finding a cycle which traverses every link of the graph at least once, and which incurs the minimum cost of traversal. This problem (called thegraph traversal problem, or theChinese postman problem [9]) can be formulated in ways analogous to those used for the well-known travelling salesman problem, and using this apparent similarity, Bellman and Cooke [1] have produced a dynamic programming formulation. This method of solution of the graph traversal problem requires computational times which increase exponentially with the number of links in the graph. Approximately the same rate of increase of computational effort with problem size would result by any other method adapting a travelling salesman algorithm to the present problem.This paper describes an efficient algorithm for the optimal solution of the graph traversal problem based on the matching method of Edmonds [5, 6]. The computational time requirements of this algorithm increase as a low order (2 or 3) power of the number of links in the graph. Computational results are given for graphs of up to 50 vertices and 125 links.The paper then discusses a generalised version of the graph traversal problem, where not one but a number of cycles are required to traverse the graph. In this case each link has (in addition to its cost) a quantity q_ij associated with it, and the sum of the quantities of the links in any one cycle must be less than a given amount representing the cycle capacity. A heuristic algorithm for the solution of this problem is given. The algorithm is based on the optimal algorithm for the single-cycle graph traversal problem and is shown to produce near-optimal results.There is a large number of possible applications where graph traversal problems arise. These applications include: the spraying of roads with salt-grit to prevent ice formation, the inspection of electric power lines, gas, or oil pipelines for faults, the delivery of letter post, etc.     

On linear bilevel problems with multiple objectives at the lower level

Bilevel programming problems provide a framework to deal with decision processes involving two decision makers with a hierarchical structure. They are characterized by the existence of two optimization problems in which the constraint region of the upper level problem is implicitly determined by the lower level optimization problem. This paper focuses on bilevel problems for which the lower level problem is a linear multiobjective program and constraints at both levels define polyhedra. This bilevel problem is reformulated as an optimization problem over a nonconvex region given by a union of faces of the polyhedron defined by all constraints. This reformulation is obtained when dealing with efficient solutions as well as weakly efficient solutions for the lower level problem. Assuming that the upper level objective function is quasiconcave, then an extreme point exists which solves the problem. An exact and a metaheuristic algorithm are developed and their performance is analyzed and compared.     

Distributed Decision‐Making in Supply Chains and Private E‐Marketplaces

This paper develops a distributed decision‐making framework for the players in a supply chain or a private e‐marketplace to collaboratively arrive at a global Pareto‐optimal solution. In this model, no player has complete knowledge about all the costs and constraints of the other players. The decision‐making framework employs an iterative procedure, based on the Integer L‐shaped method, in which a master problem is solved to propose global solutions, and each player uses his local problems to construct feasibility and optimality cuts on the master problem. The master problem is modeled as a mixed‐integer program, and the players' local problems are formulated as linear programs. Collaborative planning scenarios in private e‐marketplaces and in supply chains were formulated and solved for test data. The results show that this distributed model is able to achieve near‐optimal solutions considerably faster than the traditional centralized approach.     

Finding disjoint paths with related path costs

We consider routing in survivable networks that provide protection against node or link failures. In these networks resilience against failures is provided by routing connections on pairs of disjoint paths called primary and backup paths. The primary path of a connection carries its traffic under normal circumstances and in the eventuality of a network failure effecting the primary path the connection traffic (all or some portion of it) is rerouted over its backup path. In an online setting as connection requests arrive a pair of disjoint primary and backup paths of least total cost (under some link cost metric) are selected to route the connections. In many situations the cost metric used for the primary path differs from the cost metric used for the backup path. Also in many realistic settings these two cost metrics are related to each other. In this paper we study the problem of finding a pair of edge or node disjoint paths of least total cost where the cost of the primary path is the total cost of its links while the cost for the backup path is α times the sum of the cost of its links, for some given α < 1. We show that the problem is hard to approximate to within a factor for any positive . In addition we show that the problem is complete for a set of hard to approximate problems. On the positive side we show that a simple algorithm achieves an approximation ratio of for the problem.     

The weighted link ring loading problem

In the weighted link ring loading problem, we are given an n-node undirected ring network. Each of its links is associated with a weight. Traffic demands are given for each pair of nodes in the ring. The load of a link is the sum of the flows routed through the link, and the weighted load of a link is the product of its weight and the smallest integer not less than its load. The objective of the problem is to find a routing scheme such that the maximum weighted load on the ring is minimized. In this paper we consider three variants: (i) demands may be split into two parts, and then each part is sent in a different direction; (ii) demands are allowed to be split into two parts but restricted to be integrally split; (iii) each demand must be entirely routed in either of the two directions, clockwise or counterclockwise. We first prove that the first variant is polynomially solvable. We then present a pseudo-polynomial time algorithm for the second one. Finally, for the third one, whose NP-hardness can be drawn from the result in the literature, we derive a polynomial-time approximation scheme (PTAS).     

纵向差异下的连接外部性和网络结构分析

在寡头竞争的市场环境里,相互竞争的企业通常会与竞争对手建立连接,从而影响他们在产品市场上竞争的方式。本文我们建立两阶段博弈模型研究企业建立连接的激励以及由此而形成的网络结构形态。在博弈的第一期,具有纵向差异化的企业决定是否与其竞争对手建立连接;企业观察到连接结果后在第二期进行价格竞争。本文的分析显示均衡网络结构与连接效应、连接成本和消费者偏好有关,均衡网络可能仅是一个企业与其它所有企业建立连接的星型网络结构,也可能是没有任何企业建立连接的空网络结构。本文还分析了均衡网络和社会有效网络之间的关系,发现均衡网络和社会有效网络并不总是一致的,从社会计划者的角度看,企业建立连接可能存在激励不足,因此公共政策应该鼓励企业建立连接。     

Determining the optimal double-component assignment for a stochastic computer network

This study determines the optimal double-component assignment based on the system reliability criterion for a computer system, in which the computer system is represented as a network with a set of links and a set of vertices. The double-component assignment is to assign a set of transmission lines (resp. facilities) to the links (resp. vertices) of the network, in which each transmission line (resp. facility) has multiple states due to maintenance or failure. Thus, the computer system according to any double-component assignment is called a stochastic computer network. The system reliability is the probability that the specific units of data are successfully transmitted through the stochastic computer network. An optimization algorithm which integrates the genetic algorithm, minimal paths, and Recursive Sum of Disjoint Products is utilized to find the optimal double-component assignment with maximal system reliability. Several computer networks are utilized to demonstrate the efficiency of the proposed algorithm compared with other algorithms. By solving this problem, data can be more reliably transmitted and thus the organization operation is executed more smoothly.     

Solving the Classification Problem in Discriminant Analysis Via Linear and Nonlinear Programming Methods*

This paper demonstrates the feasibility of applying nonlinear programming methods to solve the classification problem in discriminant analysis. The application represents a useful extension of previously proposed linear programming-based solutions for discriminant analysis. The analysis of data obtained by conducting a Monte Carlo simulation experiment shows that these new procedures are promising. Future research that should promote application of the proposed methods for solving classification problems in a business decision-making environment is discussed.     

Product sequencing in multiple-piece-flow assembly lines

Modern markets demand mass customization, that is, the manufacture of customized products at low cost. Mass customization represents a major challenge for the organization of assembly lines, which were originally designed for the manufacture of homogeneous products. The multiple-piece-flow assembly line is an organizational innovation that can address this challenge. Here, several customized workpieces, each associated with a separate customer order and, hence, a separate due date, are handled simultaneously in one cycle. Consequently, the idle times decrease as do the manufacturing costs. Multiple-piece-flow assembly lines are used, for instance, in manufacturing industrial equipment.To the best of our knowledge, this paper is the first to investigate product sequencing in multiple-piece-flow assembly lines. We formalize the underlying planning problem, establish a mixed-integer model, examine its relation to several classic optimization problems, and describe useful problem properties. We leverage these properties to design an effective iterative variable neighborhood heuristic (IVNH). A detailed simulation based on real-world data and the rolling-horizon planning framework confirms that the IVNH is well suited for practical use. Furthermore, extensive computational experiments on well-structured randomly generated data sets show that the IVNH identifies optimal or near-optimal solutions within short run times. It outperformed an off-the-shelf optimization software, and in certain practice settings, the IVNH was even able to substantially reduce average order delays.     

An Interactive Framework for Multi-Person,Multiobjective Decisions

Group decision making in the presence of multiple conflicting objectives is complex and difficult. This paper describes and evaluates an iterative technique to facilitate multiple objective decision making by multiple decision makers. The proposed method augments an interactive multiobjective optimization procedure with a preference ranking tool and a consensus ranking heuristic. Two multiple objective linear programming (MOLP) solution approaches, the SIMOLP method of Reeves and Franz [39] and the interactive weighted Tchebycheff procedure of Steuer and Choo [49], are recommended optimization strategies to be used independently or in concert. Computational experience suggests that the proposed framework is an effective decision-making tool. The procedure quickly located excellent compromise solutions in a series of test problems with hypothetical decision makers. In addition, human decision makers gave positive evaluations of the procedure and the production plans the procedure provided for a resource allocation case problem.     

An investigation into the vehicle routing problem with time windows and link capacity constraints

In this work, we investigate a new, yet practical, variant of the vehicle routing problem called the vehicle routing problem with time windows and link capacity constraints (VRPTWLC). The problem considers new constraints imposed on road links with regard to vehicle passing tonnage, which is motivated by a business project with a Hong Kong transportation company that transports hazardous materials (hazmats) across the city and between Hong Kong and mainland China. In order to solve this computationally challenging problem, we develop a tabu search heuristic with an adaptive penalty mechanism (TSAP) to help manage the company's vehicle fleet. A new data set and its generation scheme are also presented to help validate our solutions. Extensive computational experiments are conducted, showing the effectiveness of the proposed solution approach.     

Distributed wireless link scheduling in the SINR model

We present an approximation algorithm for wireless link scheduling under the physical SINR interference model. In the link scheduling problem, it is given a set of \(n\) links in a metric space, each of which is a sender–receiver pair, and the objective is to schedule the links using the minimum amount of time. We focus on a variant of this fundamental problem where the power is fixed, i.e., the power assignment of links is given as part of the input. Specifically, we consider an important category of power assignments called length-monotone sublinear power assignment, which includes the widely studied uniform, mean and linear power assignments. We present a distributed algorithm that can schedule all links in \(O(\log \varDelta (I_{max}+\log ^3n))\) rounds with high probability, where \(\varDelta \) is the ratio between the longest link and the shortest link and \(I_{max}\) is the maximum nearly-equilength class affectance of the link set. It is shown that the proposed algorithm is \(O(\log \varDelta )\) approximate to the optimal schedule in dense networks with \(I_{max}\in \varOmega (\log ^3n)\). To the best of our knowledge, our algorithm is the first distributed one whose approximation ratio is independent of the network size \(n\). Our result also shows that the \(\varOmega (\log n)\) lower bound (Halldórsson and Mitra in: ICALP, 2011) on the approximation ratio does not hold for link sets with \(\log \varDelta \in o(\log n)\).     

Assembly Line Balancing with Resource Dependent Task Times*

Paced assembly lines are widely used in repetitive manufacturing applications. Most previous research on the design of paced lines has assumed that each task along the line can be performed by only one worker (or a fixed number of workers). In many cases, however, task duration times may be reduced by increasing the number of workers or changing the equipment assigned to work stations. Thus, the problem becomes one of assigning resource alternatives (e.g., workers and/or equipment) and tasks to work stations to minimize total cost for a desired production rate. For this problem, we present three procedures. The first formulates the problem as a shortest path problem and guarantees optimality. The second and third are heuristic adaptations of the shortest path procedure that are capable of solving large problems. The procedures are compared in terms of solution quality and computation time on a set of 128 randomly generated problems for which optimal solutions could be found. Our simulation results indicate that the choice of procedure depends on problem complexity and resource costs.     

Job scheduling with dual criteria and sequence-dependent setups: mathematical versus genetic programming

Flexibility, speed, and efficiency are major challenges for operations managers in today's knowledge-intensive organizations. Such requirements are converted into three production scheduling criteria: (a) minimize the impact of setup times in flexible production lines when moving from one product to another, (b) minimize number of tardy jobs, and (c) minimize overall production time, or makespan, for a given set of products or services. There is a wide range of solution methodologies for such NP-hard scheduling problems. While mathematical programming models provide optimal solutions, they become too complex to model for large scheduling problems. Simultaneously, heuristic approaches are simpler and very often independent of the problem size, but provide “good” rather than optimal solutions. This paper proposes and compares two alternative solutions: 0-1 mixed integer linear programming and genetic programming. It also provides guidelines that can be used by practitioners in the process of selecting the appropriate scheduling methodology.     

Toward Computerizing a Causal Modeling Approach to Strategic Problem Framing*

This paper proposes an object-oriented approach to the development of interactive software for the purpose of managerial problem solving. A prototype is being developed using CSM causal mapping to represent each manager's perceptions of the relationships between key variables of a firm's strategic situation. This paper suggests the design of GDSS that would enable a group of managers to discuss, learn from each other, and possibly develop consensus about decisions or their causes. Issues involving future development are discussed.     

The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach

In this paper, we consider a variant of the Location-Routing Problem (LRP), namely the LRP with simultaneous pickup and delivery (LRPSPD). The LRPSPD seeks to minimize total cost by simultaneously locating the depots and designing the vehicle routes that satisfy pickup and delivery demand of each customer at the same time. We propose two polynomial-size mixed integer linear programming formulations for the problem and a family of valid inequalities to strengthen the formulations. While the first formulation is a node-based formulation, the second one is a flow-based formulation. Furthermore, we propose a two-phase heuristic approach based on simulated annealing, tp_SA, to solve the large-size LRPSPD and two initialization heuristics to generate an initial solution for the tp_SA. We then empirically evaluate the strengths of the proposed formulations with respect to their ability to find optimal solutions or strong lower bounds, and investigate the performance of the proposed heuristic approach. Computational results show that the flow-based formulation performs better than the node-based formulation in terms of the solution quality and the computation time on small-size problems. However, the node-based formulation can yield competitive lower bounds in a reasonable amount of time on medium-size problems. Meantime, the proposed heuristic approach is computationally efficient in finding good quality solutions for the LRPSPD.     

Solution Structure of Some Inverse Combinatorial Optimization Problems

In this paper we consider some inverse combinatorial optimization problems, that is, for a given set of feasible solutions of an optimization problem, we wish to know: under what weight vectors (or capacity vectors) will these feasible solutions become optimal solutions? We analysed shortest path problem, minimum cut problem, minimum spanning tree problem and maximum-weight matching problem, and found that in each of these cases, the solution set of the inverse problem is charaterized by solving another combinatorial optimization problem. The main tool in our approach is Fulkerson's theory of blocking and anti-blocking polyhedra with some necessary revisions.     

INTEGER GOAL PROGRAMMING IN ADVERTISING MEDIA SELECTION

The media selection decision allocates advertising dollars among competing media so as to optimize promotional and corporate objectives. Linear programming attempts to model this process have been complicated by multiple and often conflicting management goals, the need for integer solutions, and nonlinearities. This study offers a technique that is sufficiently robust to simultaneously handle these problems. An alternative media selection framework is presented and the results of an illustrative application of integer goal programming are discussed. The proposed model improves on linear programming by success fully providing for optimal, integer solutions in settings that more realistically reflect the complexity of the media decision environment.     

Integrating the Content and Process of Strategic MIS Planning with Competitive Strategy*

This paper presents a framework that links strategic MIS planning and business strategy and relates it to competitive advantage and company performance. To achieve this objective, the paper first delineates the dimensions of strategic MIS planning, focusing on both content and process issues. The notion of fit within dimensions, between sets of dimensions (process and content), and between MIS planning and competitive strategy is also introduced. Next, employing the Miles-Snow typology of business strategy, the paper posits normative differences in the dimensions of strategic MIS planning along different business (or competitive) strategies. The implications of our study for both decision makers and scholars are discussed. Propositions that tie competitive strategy, strategic MIS planning, and company financial performance are then presented. The paper concludes by providing direction for future research.