Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems

Until recently, fast algorithms for the maximum flow problem have typically proceeded by constructing layered networks and establishing blocking flows in these networks. However, in recent years, new distance-directed algorithms have been suggested that do not construct layered networks but instead maintain a distance label with each node. The distance label of a node is a lower bound on the length of the shortest augmenting path from the node to the sink. In this article we develop two distance-directed augmenting path algorithms for the maximum flow problem. Both the algorithms run in O(n²m) time on networks with n nodes and m arcs. We also point out the relationship between the distance labels and layered networks. Using a scaling technique, we improve the complexity of our distance-directed algorithms to O(nm log U), where U denotes the largest arc capacity. We also consider applications of these algorithms to unit capacity maximum flow problems and a class of parametric maximum flow problems.     

Finding the Kth shortest path in a time‐schedule network

We consider the problem of finding the Kth shortest path for a time‐schedule network, where each node in the network has a list of prespecified departure times, and departure from the node can take place only at one of these departure times. We develop a polynomial time algorithm independent of K for finding the Kth shortest path. The proposed algorithm constructs a map structure at each node in the network, using which we can directly find the Kth shortest path without having to enumerate the first K − 1 paths. Since the same map structure is used for different K values, it is not necessary to reconstruct the table for additional paths. Consequently, the algorithm is suitable for directly finding multiple shortest paths in the same network. Furthermore, the algorithm is modified slightly for enumerating the first K shortest paths and is shown to have the lowest possible time complexity under a condition that holds for most practical networks. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Algorithm to solve a chance‐constrained network capacity design problem with stochastic demands and finite support

We consider the problem of determining the capacity to assign to each arc in a given network, subject to uncertainty in the supply and/or demand of each node. This design problem underlies many real‐world applications, such as the design of power transmission and telecommunications networks. We first consider the case where a set of supply/demand scenarios are provided, and we must determine the minimum‐cost set of arc capacities such that a feasible flow exists for each scenario. We briefly review existing theoretical approaches to solving this problem and explore implementation strategies to reduce run times. With this as a foundation, our primary focus is on a chance‐constrained version of the problem in which α% of the scenarios must be feasible under the chosen capacity, where α is a user‐defined parameter and the specific scenarios to be satisfied are not predetermined. We describe an algorithm which utilizes a separation routine for identifying violated cut‐sets which can solve the problem to optimality, and we present computational results. We also present a novel greedy algorithm, our primary contribution, which can be used to solve for a high quality heuristic solution. We present computational analysis to evaluate the performance of our proposed approaches. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 236–246, 2016     

Branch‐and‐price‐and‐cut for the manpower routing problem with synchronization constraints

In this article, we propose a branch‐and‐price‐and‐cut (BPC) algorithm to exactly solve the manpower routing problem with synchronization constraints (MRPSC). Compared with the classical vehicle routing problems (VRPs), the defining characteristic of the MRPSC is that multiple workers are required to work together and start at the same time to carry out a job, that is, the routes of the scheduling subjects are dependent. The incorporation of the synchronization constraints increases the difficulty of the MRPSC significantly and makes the existing VRP exact algorithm inapplicable. Although there are many types of valid inequalities for the VRP or its variants, so far we can only adapt the infeasible path elimination inequality and the weak clique inequality to handle the synchronization constraints in our BPC algorithm. The experimental results at the root node of the branch‐and‐bound tree show that the employed inequalities can effectively improve the lower bound of the problem. Compared with ILOG CPLEX, our BPC algorithm managed to find optimal solutions for more test instances within 1 hour. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 138–171, 2016     

Decomposition algorithms for finding the shortest path between a source node and a sink node of a network

Decomposition algorithms for finding a shortest path between a source node and a sink node of an arbitrary distance network are developed. Different decomposition algorithms are proposed for different network topologies. Since Shier's algorithm compares very favorably with other decomposition algorithms in all the network topologies, we compare our algorithms against Shier's algorithm. It is shown that the efficiency of the proposed algorithms compares very favorably with Shier's algorithm. For special types of networks the computational requirements of the proposed algorithm is a polynomial of O(n²).     

On efficient algorithms for finding efficient salvo policies

We consider the salvo policy problem, in which there are k moments, called salvos, at which we can fire multiple missiles simultaneously at an incoming object. Each salvo is characterized by a probability p_i: the hit probability of a single missile. After each salvo, we can assess whether the incoming object is still active. If it is, we fire the missiles assigned to the next salvo. In the salvo policy problem, the goal is to assign at most n missiles to salvos in order to minimize the expected number of missiles used. We consider three problem versions. In Gould's version, we have to assign all n missiles to salvos. In the Big Bomb version, a cost of B is incurred when all salvo's are unsuccessful. Finally, we consider the Quota version in which the kill probability should exceed some quota Q. We discuss the computational complexity and the approximability of these problem versions. In particular, we show that Gould's version and the Big Bomb version admit pseudopolynomial time exact algorithms and fully polynomial time approximation schemes. We also present an iterative approximation algorithm for the Quota version, and show that a related problem is NP-complete.     

Algorithms for the minimax transportation problem

In this paper, we consider a variant of the classical transportation problem as well as of the bottleneck transportation problem, which we call the minimax transportation problem. The problem considered is to determine a feasible flow x_ij from a set of origins I to a set of destinations J for which max_(i,j)εIxJ{c_ijx_ij} is minimum. In this paper, we develop a parametric algorithm and a primal-dual algorithm to solve this problem. The parametric algorithm solves a transportation problem with parametric upper bounds and the primal-dual algorithm solves a sequence of related maximum flow problems. The primal-dual algorithm is shown to be polynomially bounded. Numerical investigations with both the algorithms are described in detail. The primal-dual algorithm is found to be computationally superior to the parametric algorithm and it can solve problems up to 1000 origins, 1000 destinations and 10,000 arcs in less than 1 minute on a DEC 10 computer system. The optimum solution of the minimax transportation problem may be noninteger. We also suggest a polynomial algorithm to convert this solution into an integer optimum solution.     

Pricing bridges to cross a river

We consider a pricing problem in directed, uncapacitated networks. Tariffs must be defined by an operator, the leader, for a subset of m arcs, the tariff arcs. Costs of all other arcs in the network are assumed to be given. There are n clients, the followers, and after the tariffs have been determined, the clients route their demands independent of each other on paths with minimal total cost. The problem is to find tariffs that maximize the operator's revenue. Motivated by applications in telecommunication networks, we consider a restricted version of this problem, assuming that each client utilizes at most one of the operator's tariff arcs. The problem is equivalent to pricing bridges that clients can use in order to cross a river. We prove that this problem is APX‐hard. Moreover, we analyze the effect of uniform pricing, proving that it yields both an m approximation and a (1 + lnD)‐approximation. Here, D is upper bounded by the total demand of all clients. In addition, we consider the problem under the additional restriction that the operator must not reject any of the clients. We prove that this problem does not admit approximation algorithms with any reasonable performance guarantee, unless P = NP, and we prove the existence of an n‐approximation algorithm. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Decomposition algorithms for minimal cut problems

Consider a network G(N. A) with n nodes, where node 1 designates its source node and node n designates its sink node. The cuts (Z_i, =), i= 1…, n - 1 are called one-node cuts if 1 ? Z_i,. n q Z_i, Z₁-_? {1}, Z_i ? Z_i+1 and Z_i and Z_i+l differ by only one node. It is shown that these one-node cuts decompose G into 1 m n/2 subnetworks with known minimal cuts. Under certain circumstances, the proposed one-node decomposition can produce a minimal cut for G in 0(n² ) machine operations. It is also shown that, under certain conditions, one-node cuts produce no decomposition. An alternative procedure is also introduced to overcome this situation. It is shown that this alternative procedure has the computational complexity of 0(n³).     

The discrete search problem and the construction of optimal allocations

Suppose one object is hidden in the k-th of n boxes with probability p(k). The boxes are to be searched sequentially. Associated with the j-th search of box k is a cost c(j,k) and a conditional probability q(j,k) that the first j - 1 searches of box k are unsuccessful while the j-th search is successful given that the object is hidden in box k. The problem is to maximize the probability that we find the object if we are not allowed to offer more than L for the search. We prove the existence of an optimal allocation of the search effort L and state an algorithm for the construction of an optimal allocation. Finally, we discuss some problems concerning the complexity of our problem.     

An FPTAS for scheduling a two‐machine flowshop with one unavailability interval

We study a deterministic two‐machine flowshop scheduling problem with an assumption that one of the two machines is not available in a specified time period. This period can be due to a breakdown, preventive maintenance, or processing unfinished jobs from a previous planning horizon. The problem is known to be NP‐hard. Pseudopolynomial dynamic programming algorithms and heuristics with worst case error bounds are given in the literature to solve the problem. They are different for the cases when the unavailability interval is for the first or second machine. The existence of a fully polynomial time approximation scheme (FPTAS) was formulated as an open conjecture in the literature. In this paper, we show that the two cases of the problem under study are equivalent to similar partition type problems. Then we derive a generic FPTAS for the latter problems with O(n⁵/ε⁴) time complexity. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

New heuristic methods for the capacitated multi‐facility Weber problem

In this paper we consider the capacitated multi‐facility Weber problem with the Euclidean, squared Euclidean, and ?_p‐distances. This problem is concerned with locating m capacitated facilities in the Euclidean plane to satisfy the demand of n customers with the minimum total transportation cost. The demand and location of each customer are known a priori and the transportation cost between customers and facilities is proportional to the distance between them. We first present a mixed integer linear programming approximation of the problem. We then propose new heuristic solution methods based on this approximation. Computational results on benchmark instances indicate that the new methods are both accurate and efficient. © 2006 Wiley Periodicals, Inc. Naval Research Logistics 2006     

Sojourn times in G/M/1 fork‐join networks

We consider a processing network in which jobs arrive at a fork‐node according to a renewal process. Each job requires the completion of m tasks, which are instantaneously assigned by the fork‐node to m task‐processing nodes that operate like G/M/1 queueing stations. The job is completed when all of its m tasks are finished. The sojourn time (or response time) of a job in this G/M/1 fork‐join network is the total time it takes to complete the m tasks. Our main result is a closed‐form approximation of the sojourn‐time distribution of a job that arrives in equilibrium. This is obtained by the use of bounds, properties of D/M/1 and M/M/1 fork‐join networks, and exploratory simulations. Statistical tests show that our approximation distributions are good fits for the sojourn‐time distributions obtained from simulations. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Mathematical aspects of the 3 × n job-shop sequencing problem

The paper discusses mathematical properties of the well-known Bellman-Johnson 3 × n sequencing problem. Optimal rules for some special cases are developed. For the case min B_i ≥ maxA_j we find an optimal sequence of the 2 × n problem for machines B and C and move one item to the front of the sequence to minimize (7); when min B_i ≥ max C_j we solve a 2 × n problem for machines A and B and move one item to the end of the optimal sequence so as to minimize (9). There is also given a sufficient optimality condition for a solution obtained by Johnson's approximate method. This explains why this method so often produces an optimal solution.     

Probabilistic analysis of an asymptotically optimal solution for the completion time variance problem

Scheduling a set of n jobs on a single machine so as to minimize the completion time variance is a well‐known NP‐hard problem. In this paper, we propose a sequence, which can be constructed in O(n log n) time, as a solution for the problem. Our primary concern is to establish the asymptotical optimality of the sequence within the framework of probabilistic analysis. Our main result is that, when the processing times are randomly and independently drawn from the same uniform distribution, the sequence is asymptotically optimal in the sense that its relative error converges to zero in probability as n increases. Other theoretical results are also derived, including: (i) When the processing times follow a symmetric structure, the problem has 2^{⌊(n−1)/2⌋} optimal sequences, which include our proposed sequence and other heuristic sequences suggested in the literature; and (ii) when these 2^{⌊(n−1)/2⌋} sequences are used as approximate solutions for a general problem, our proposed sequence yields the best approximation (in an average sense) while another sequence, which is commonly believed to be a good approximation in the literature, is interestingly the worst. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 373–398, 1999     

Approximation schemes for ordered vector packing problems

In this paper we deal with the d‐dimensional vector packing problem, which is a generalization of the classical bin packing problem in which each item has d distinct weights and each bin has d corresponding capacities. We address the case in which the vectors of weights associated with the items are totally ordered, i.e., given any two weight vectors a_i, a_j, either a_i is componentwise not smaller than a_j or a_j is componentwise not smaller than a_i. An asymptotic polynomial‐time approximation scheme is constructed for this case. As a corollary, we also obtain such a scheme for the bin packing problem with cardinality constraint, whose existence was an open question to the best of our knowledge. We also extend the result to instances with constant Dilworth number, i.e., instances where the set of items can be partitioned into a constant number of totally ordered subsets. We use ideas from classical and recent approximation schemes for related problems, as well as a nontrivial procedure to round an LP solution associated with the packing of the small items. © 2002 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

A decomposable transshipment algorithm for a multiperiod transportation problem

A dynamic version of the transportation (Hitchcock) problem occurs when there are demands at each of n sinks for T periods which can be fulfilled by shipments from m sources. A requirement in period t₂ can be satisfied by a shipment in the same period (a linear shipping cost is incurred) or by a shipment in period t₁ < t₂ (in addition to the linear shipping cost a linear inventory cost is incurred for every period in which the commodity is stored). A well known method for solving this problem is to transform it into an equivalent single period transportation problem with mT sources and nT sinks. Our approach treats the model as a transshipment problem consisting of T, m source — n sink transportation problems linked together by inventory variables. Storage requirements are proportional to T² for the single period equivalent transportation algorithm, proportional to T, for our algorithm without decomposition, and independent of T for our algorithm with decomposition. This storage saving feature enables much larger problems to be solved than were previously possible. Futhermore, we can easily incorporate upper bounds on inventories. This is not possible in the single period transportation equivalent.     

Parallel machine scheduling with eligibility constraints: A composite dispatching rule to minimize total weighted tardiness

We study a parallel machine scheduling problem, where a job j can only be processed on a specific subset of machines M_j, and the M_j subsets of the n jobs are nested. We develop a two‐phase heuristic for minimizing the total weighted tardiness subject to the machine eligibility constraints. In the first phase, we compute the factors and statistics that characterize a problem instance. In the second phase, we propose a new composite dispatching rule, the Apparent Tardiness Cost with Flexibility considerations (ATCF) rule, which is governed by several scaling parameters of which the values are determined by the factors obtained in the first phase. The ATCF rule is a generalization of the well‐known ATC rule which is very widely used in practice. We further discuss how to improve the dispatching rule using some simple but powerful properties without requiring additional computation time, and the improvement is quite satisfactory. We apply the Sequential Uniform Design Method to design our experiments and conduct an extensive computational study, and we perform tests on the performance of the ATCF rule using a real data set from a large hospital in China. We further compare its performance with that of the classical ATC rule. We also compare the schedules improved by the ATCF rule with what we believe are Near Optimal schedules generated by a general search procedure. The computational results show that especially with a low due date tightness, the ATCF rule performs significantly better than the well‐known ATC rule generating much improved schedules that are close to the Near Optimal schedules. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 249–267, 2017     

The vehicle-routing problem with delivery and back-haul options

In this article we consider a version of the vehicle-routing problem (VRP): A fleet of identical capacitated vehicles serves a system of one warehouse and N customers of two types dispersed in the plane. Customers may require deliveries from the warehouse, back hauls to the warehouse, or both. The objective is to design a set of routes of minimum total length to serve all customers, without violating the capacity restriction of the vehicles along the routes. The capacity restriction here, in contrast to the VRP without back hauls is complicated because amount of capacity used depends on the order the customers are visited along the routes. The problem is NP-hard. We develop a lower bound on the optimal total cost and a heuristic solution for the problem. The routes generated by the heuristic are such that the back-haul customers are served only after terminating service to the delivery customers. However, the heuristic is shown to converge to the optimal solution, under mild probabilistic conditions, as fast as N^−0.5. The complexity of the heuristic, as well as the computation of the lower bound, is O(N³) if all customers have unit demand size and O(N³ log N) otherwise, independently of the demand sizes. © 1996 John Wiley & Sons, Inc.     

On the design of a tandem queue with blocking: Modeling,analysis, and gradient estimation

We demonstrate here how recent advances in the study of discrete-event stochastic systems provide fruitful results for the modeling, analysis, and design of manufacturing systems. We consider a multistage make-to-stock system where outputs from the final stage are used to satisfy customer demands. We address the problem of finding the appropriate trade-off between reduced order waiting time and increased process speeds. Using the idea of infinitesimal perturbation analysis (IPA), we establish a simple procedure where sample-path derivatives can be obtained along an arbitrary sample path. Under suitable conditions, we demonstrate that these derivative estimators are unbiased and strongly consistent and can be used in a classical stochastic optimization scheme to solve the problem. The role of continuity and convexity on the validity of the estimator is also addressed. Although the focus of this article is not to solve for the optimal solution, we provide a theoretical justification for such a pursuit. The approach is appealing as it is numerically stable, easy to implement, and can be extended to other system performance measures. © 1994 John Wiley & Sons, Inc.