Suchergebnisse

AbstractWe 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

AbstractGiven an edge‐distance graph of a set of suppliers and clients, the bottleneck problem is to assign each client to a selected supplier minimizing their maximum distance. We introduce minimum quantity commitments to balance workloads of suppliers, provide the best possible approximation algorithm, and study its generalizations and specializations. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006

AbstractIn this paper, we study a m‐parallel machine scheduling problem with a non‐crossing constraint motivated by crane scheduling in ports. We decompose the problem to allow time allocations to be determined once crane assignments are known and construct a backtracking search scheme that manipulates domain reduction and pruning strategies. Simple approximation heuristics are developed, one of which guarantees solutions to be at most two times the optimum. For large‐scale problems, a simulated annealing heuristic that uses random neighborhood generation is provided. Computational experiments are conducted to test the algorithms. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007.

AbstractThis article studies a min‐max path cover problem, which is to determine a set of paths for k capacitated vehicles to service all the customers in a given weighted graph so that the largest path cost is minimized. The problem has wide applications in vehicle routing, especially when the minimization of the latest service completion time is a critical performance measure. We have analyzed four typical variants of this problem, where the vehicles have either unlimited or limited capacities, and they start from either a given depot or any depot of a given depot set. We have developed approximation algorithms for these four variants, which achieve approximation ratios of max{3 ‐ 2/k,2}, 5, max{5 ‐ 2/k,4}, and 7, respectively. We have also analyzed the approximation hardness of these variants by showing that, unless P = NP, it is impossible for them to achieve approximation ratios less than 4/3, 3/2, 3/2, and 2, respectively. We have further extended the techniques and results developed for this problem to other min‐max vehicle routing problems.© 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010

AbstractA major challenge in making supply meet demand is to coordinate transshipments across the supply chain to reduce costs and increase service levels in the face of demand fluctuations, short lead times, warehouse limitations, and transportation and inventory costs. In particular, transshipment through crossdocks, where just‐in‐time objectives prevail, requires precise scheduling between suppliers, crossdocks, and customers. In this work, we study the transshipment problem with supplier and customer time windows where flow is constrained by transportation schedules and warehouse capacities. Transportation is provided by fixed or flexible schedules and lot‐sizing is dealt with through multiple shipments. We develop polynomial‐time algorithms or, otherwise, provide the complexity of the problems studied. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005