Polynomial‐time approximation scheme for concurrent open shop scheduling with a fixed number of machines to minimize the total weighted completion time

In this article, we consider the concurrent open shop scheduling problem to minimize the total weighted completion time. When the number of machines is arbitrary, the problem has been shown to be inapproximable within a factor of 4/3 ‐ ε for any ε > 0 if the unique games conjecture is true in the literature. We propose a polynomial time approximation scheme for the problem under the restriction that the number of machines is fixed. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

The knapsack problem with a minimum filling constraint

We study a knapsack problem with an additional minimum filling constraint, such that the total weight of selected items cannot be less than a given threshold. The problem has several applications in shipping, e‐commerce, and transportation service procurement. When the threshold equals the knapsack capacity, even finding a feasible solution to the problem is NP‐hard. Therefore, we consider the case when the ratio α of threshold to capacity is less than 1. For this case, we develop an approximation scheme that returns a feasible solution with a total profit not less than (1 ‐ ε) times the total profit of an optimal solution for any ε > 0, and with a running time polynomial in the number of items, 1/ε, and 1/(1‐α). © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

Optimal dispatching strategies for vehicles having exponentially distributed trip times

A transportation system has N vehicles with no capacity constraint which take passengers from a depot to various destinations and return to the depot. The trip times are considered to be independent and identically distributed random variables. The dispatch strategy at the depot is to dispatch immediately, or to hold any returning vehicles with the objective of minimizing the average wait per passenger at the depot, if passengers arrive at a uniform rate. Optimal control strategies and resulting waits are determined in the special case of exponentially distributed trip time for various N up to N = 15. For N ? 1, the nature of the solution is always to keep a reservoir of vehicles in the depot, and to decrease (increase) the time headway between dispatches as the size of the reservoir gets larger (smaller). For sufficiently large N, one can approximate the number of vehicles in the reservoir by a continuum and obtain analytic experession for the optimal dispatch rate as a function of the number of vehicles in the reservoir. For the optimal strategy, it is shown that the average number of vehicles in the depot is of order N^1/3. These limit properties are expected to be quite insensitive to the actual trip time distribution, but the convergence of the exact properties to the continuum approximation as N → ∞ is very slow.     

Minimizing makespan on a single batch processing machine with nonidentical job sizes

We deal with the problem of minimizing makespan on a single batch processing machine. In this problem, each job has both processing time and size (capacity requirement). The batch processing machine can process a number of jobs simultaneously as long as the total size of these jobs being processed does not exceed the machine capacity. The processing time of a batch is just the processing time of the longest job in the batch. An approximation algorithm with worst‐case ratio 3/2 is given for the version where the processing times of large jobs (with sizes greater than 1/2) are not less than those of small jobs (with sizes not greater than 1/2). This result is the best possible unless P = NP. For the general case, we propose an approximation algorithm with worst‐case ratio 7/4. A number of heuristics by Uzosy are also analyzed and compared. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 226–240, 2001     

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.     

Vehicle routing problems with regular objective functions on a path

We investigate the problem of scheduling a fleet of vehicles to visit the customers located on a path to minimize some regular function of the visiting times of the customers. For the single‐vehicle problem, we prove that it is pseudopolynomially solvable for any minsum objective and polynomially solvable for any minmax objective. Also, we establish the NP‐hardness of minimizing the weighted number of tardy customers and the total weighted tardiness, and present polynomial algorithms for their special cases with a common due date. For the multivehicle problem involving n customers, we show that an optimal solution can be found by solving or O(n) single‐vehicle problems. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 61: 34–43, 2014     

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     

Split delivery routing

This article examines a relaxed version of the generic vehicle routing problem. In this version, a delivery to a demand point can be split between any number of vehicles. In spite of this relaxation the problem remains computationally hard. Since only small instances of the vehicle routing problem are known to be solved using exact methods, the vehicle route construction for this problem version is approached using heuristic rules. The main contribution of this article to the existing body of literature on vehicle routing issues in (a) is presenting a new vehicle routing problem amenable to practical applications, and (b) demonstrating the potential for cost savings over similar “traditional” vehicle routing when implementing the model and solutions presented here. The solution scheme allowing for split deliveries is compared with a solution in which no split deliveries are allowed. The comparison is conducted on six sets of 30 problems each for problems of size 75, 115, and 150 demand points (all together 540 problems). For very small demands (up to 10% of vehicle's capacity) no significant difference in solutions is evident for both solution schemes. For the other five problem sets for which point demand exceeds 10% of vehicle's capacity, very significant cost savings are realized when allowing split deliveries. The savings are significant both in the total distance and the number of vehicles required. The vehicles' routes constructed by our procedure tend to cover cohesive geographical zones and retain some properties of optimal solutions.     

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     

A two-echelon multi-station inventory model for navy applications

The two inventory echelons under consideration are the depot, D, and k tender ships E₁, …, E_k. The tender ships supply the demand for certain parts of operational boats (the customers). The statistical model assumes that the total monthly demands at the k tenders are stationary independent Poisson random variables, with unknown means λ₁, …, λ_k. The stock levels on the tenders, at the heginning of each month, can be adjusted either by ordering more units from the depot, or by shipping bach to the depot an excess stock. There is no traffic of stock between tenders which is not via the depot. The lead time from the depot to the tenders is at most 1 month. The lead time for orders of the depot from the manufacturer is L months. The loss function due to erroneous decision js comprised of linear functions of the extra monthly stocks, and linear functions of shortages at the tenders and at the depot over the N months. A Bayes sequential decision process is set up for the optimal adjustment levels and orders of the two echelons. The Dynamic Programming recursive functions are given for a planning horizon of N months.     

Vehicle fleet refueling strategies to maximize operational range

The focus of this research is on self-contained missions requiring round-trip vehicle travel from a common origin. For a single vehicle the maximal distance that can be reached without refueling is defined as its operational range. Operational range is a function of a vehicle's fuel capacity and fuel consumption characteristics. In order to increase a vehicle's range beyond its operational range replenishment from a secondary fuel source is necessary. In this article, the problem of maximizing the range of any single vehicle from a fleet of n vehicles is investigated. This is done for four types of fleet configurations: (1) identical vehicles, (2) vehicles with identical fuel consumption rates but different fuel capacities, (3) vehicles which have the same fuel capacity but different fuel consumption rates, and (4) vehicles with both different fuel capacities and different consumption rates. For each of the first three configurations the optimal refueling policy that provides the maximal range is determined for a sequential refueling chain strategy. In such a strategy the last vehicle to be refueled is the next vehicle to transfer its fuel. Several mathematical programming formulations are given and their solutions determined in closed form. One of the major conclusions is that for an identical fleet the range of the farthest vehicle can be increased by at most 50% more than the operational range of a single vehicle. Moreover, this limit is reached very quickly with small values of n. The performance of the identical fleet configuration is further investigated for a refueling strategy involving a multiple-transfer refueling chain, stochastic vehicle failures, finite refueling times, and prepositioned fleets. No simple refueling ordering rules were found for the most general case (configuration 4). In addition, the case of vehicles with different fuel capacities is investigated under a budget constraint. The analysis provides several benchmarks or bounds for which more realistic structures may be compared. Some of the more complex structures left for future study are described.     

需求可拆分的应急物资调度问题的蚁群算法

应急物资调度问题是个典型的需求可拆分的车辆路径问题,区别于传统的车辆路径问题,将每个需求节点只能由一辆车访问的约束去除,允许需求节点由多辆车进行访问。针对应急物资调度问题的特点,建立相应的多目标车辆路径数学规划模型(SDVRP),并根据模型特点设计改进蚁群优化算法。最后,进行相应的算例分析,验证了该模型和算法的有效性。     

Scheduling parallel machines with inclusive processing set restrictions and job rejection

In this article, we study a parallel machine scheduling problem with inclusive processing set restrictions and the option of job rejection. In the problem, each job is compatible to a subset of machines, and machines are linearly ordered such that a higher‐indexed machine can process all those jobs that a lower‐indexed machine can process (but not conversely). To achieve a tight production due date, some of the jobs might be rejected at certain penalty. We first study the problem of minimizing the makespan of all accepted jobs plus the total penalty cost of all rejected jobs, where we develop a ‐approximation algorithm with a time complexity of . We then study two bicriteria variants of the problem. For the variant problem of minimizing the makespan subject to a given bound on the total rejection cost, we develop a ‐approximation algorithm with a time complexity of . For the variant problem of maximizing the total rejection cost of the accepted jobs subject to a given bound on the makespan, we present a 0.5‐approximation algorithm with a time complexity of . © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 667–681, 2017     

Allocation policies and cost approximations for multilocation inventory systems

Consider a central depot that supplies several locations experiencing random demands. Periodically, the depot may place an order for exogenous supply. Orders arrive after a fixed leadtime, and are then allocated among the several locations. Each allocation reaches its destination after a further delay. We consider the special case where the penalty-cost/holding-cost ratio is constant over the locations. Several approaches are given to approximate the dynamic program describing the problem. Each approach provides both a near-optimal order policy and an approximation of the optimal cost of the original problem. In addition, simple but effective allocation policies are discussed.     

An extension of the (szwarc) truck assignment problem

In this journal in 1967. Szware presented an algorithm for the optimal routing of a common vehicle fleet between m sources and n sinks with p different types of commodities. The main premise of the formulation is that a truck may carry only one commodity at a time and must deliver the entire load to one demand area. This eliminates the problem of routing vehicles between sources or between sinks and limits the problem to the routing of loaded trucks between sources and sinks and empty trucks making the return trip. Szwarc considered only the transportation aspect of the problem (i. e., no intermediate points) and presented a very efficient algorithm for solution of the case he described. If the total supply is greater than the total demand, Szwarc shows that the problem is equivalent to a (mp + n) by (np + m) Hitchcock transportation problem. Digital computer codes for this algorithm require rapid access storage for a matrix of size (mp + n) by (np + m); therefore, computer storage required grows proportionally to p². This paper offers an extension of his work to a more general form: a transshipment network with capacity constraints on all arcs and facilities. The problem is shown to be solvable directly by Fulkerson's out-of-kilter algorithm. Digital computer codes for this formulation require rapid access storage proportional to p instead of p². Computational results indicate that, in addition to handling the extensions, the out-of-kilter algorithm is more efficient in the solution of the original problem when there is a mad, rate number of commodities and a computer of limited storage capacity.     

Aggregating courier deliveries

We consider the problem of efficiently scheduling deliveries by an uncapacitated courier from a central location under online arrivals. We consider both adversary‐controlled and Poisson arrival processes. In the adversarial setting we provide a randomized (3βΔ/2δ ? 1) ‐competitive algorithm, where β is the approximation ratio of the traveling salesman problem, δ is the minimum distance between the central location and any customer, and Δ is the length of the optimal traveling salesman tour overall customer locations and the central location. We provide instances showing that this analysis is tight. We also prove a 1 + 0.271Δ/δ lower‐bound on the competitive ratio of any algorithm in this setting. In the Poisson setting, we relax our assumption of deterministic travel times by assuming that travel times are distributed with a mean equal to the excursion length. We prove that optimal policies in this setting follow a threshold structure and describe this structure. For the half‐line metric space we bound the performance of the randomized algorithm in the Poisson setting, and show through numerical experiments that the performance of the algorithm is often much better than this bound.     

Approximation of multiclass queueing networks with highly variable arrivals under deterministic routing

In this paper, we present the heavy‐traffic bottleneck phenomenon under multiclass deterministic routing and discuss how it can be addressed by decomposition approximation. Examples show that Bitran and Tirupati's method and Whitt's enhancements for deterministic routing may not properly account for this phenomenon. We propose refinements to these methods based on Whitt's variability functions. Results of numerical experiments on simple networks and semiconductor manufacturing process show significant improvement in the approximation of expected waiting time at bottleneck stations. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Simple paths with exact and forbidden lengths

We study new decision and optimization problems of finding a simple path between two given vertices in an arc weighted directed multigraph such that the path length is equal to a given number or it does not fall into the given forbidden intervals (gaps). A fairly complete computational complexity classification is provided and exact and approximation algorithms are suggested.     

Optimal refueling strategies for a mixed-vehicle fleet

The problem treated here involves a mixed fleet of vehicles comprising two types of vehicles: K₁ tanker-type vehicles capable of refueling themselves and other vehicles, and K₂ nontanker vehicles incapable of refueling. The two groups of vehicles have different fuel capacities as well as different fuel consumption rates. The problem is to find the tanker refueling sequence that maximizes the range attainable for the K₂ nontankers. A tanker refueling sequence is a partition of the tankers into m subsets (2 ≤ m ≤ K₁). A given sequence of the partition provides a realization of the number of tankers participating in each successive refueling operation. The problem is first formulated as a nonlinear mixed-integer program and reduced to a linear program for a fixed sequence which may be solved by a simple recursive procedure. It is proven that a “unit refueling sequence” composed of one tanker refueling at each of K₁ refueling operations is optimal. In addition, the problem of designing the “minimum fleet” (minimum number of tankers) required for a given set of K₂ nontankers to attain maximal range is resolved. Also studied are extensions to the problem with a constraint on the number of refueling operations, different nontanker recovery base geometry, and refueling on the return trip.