Inventory control of spares in a transport corporation — A case study

This paper reports on a study carried out in a transport organisation to find the optimal inventory of recoverable spares in a two-level inventory system consisting of a central depot and a set of 20 depots all over the territory of the organisation, with repair facilities. The problems of the present system are diagnosed and it is observed that the upper echelon's inability to meet the lower echelon's demand has resulted in an ever-increasing shortage. A mathematical model is developed to suit the system structure and a set of optimal inventory policies for recoverable spares at both the echelons is obtained for the case studied.     

Linear programming approach to solve interval-valued matrix games

Matrix game theory is concerned with how two players make decisions when they are faced with known exact payoffs. The aim of this paper is to develop a simple and an effective linear programming method for solving matrix games in which the payoffs are expressed with intervals. Because the payoffs of the matrix game are intervals, the value of the matrix game is an interval as well. Based on the definition of the value for matrix games, the value of the matrix game may be regarded as a function of values in the payoff intervals, which is proven to be non-decreasing. A pair of auxiliary linear programming models is formulated to obtain the upper bound and the lower bound of the value of the interval-valued matrix game by using the upper bounds and the lower bounds of the payoff intervals, respectively. By the duality theorem of linear programming, it is proven that two players have the identical interval-type value of the interval-valued matrix game. Also it is proven that the linear programming models and method proposed in this paper extend those of the classical matrix games. The linear programming method proposed in this paper is demonstrated with a real investment decision example and compared with other similar methods to show the validity, applicability and superiority.     

On the best possible competitive ratio for the multislope ski-rental problem

The multislope ski-rental problem is an extension of the classical ski-rental problem, where the player has several lease options besides the pure rent and buy options. In this problem the hardness of an instance, which is the setting of options, significantly affects the player’s performance. There is an algorithm that for a given instance, computes the best possible strategy. However, the output is given as numerical values and therefore the relational nature between an instance and the best possible performance for it has not been known. In this paper we prove that even for the easiest instance, a competitive ratio smaller than \(e/(e - 1) \approx 1.58\) cannot be achieved. More precisely, a tight lower bound on the best possible performance is obtained in a closed form parametrized by the number of options. Furthermore, we establish a matching upper and lower bound on the competitive ratio each for the 3-option and 4-option problems.     

Planning of a decentralized distribution network using bilevel optimization

This paper proposes a bilevel optimization problem to model the planning of a distribution network that allows us to take into account how decisions made at the distribution stage of the supply chain can affect and be affected by decisions made at the manufacturing stage. Usually, the distribution network design problem decides on the opening of depots and the distribution from the depots to customers only and pays no attention to the manufacturing process itself. By way of example, the paper discusses the implications of formulating a bilevel model to integrate distribution and manufacturing, maintaining the hierarchy existing in the decision process. The resulting model is a bilevel mixed integer optimization problem. Hence, only small instances can be optimally solved in an acceptable computing time. In order to be able to solve the optimization model for realistic large systems, a metaheuristic approach based on evolutionary algorithms is developed. The algorithm combines the use of an evolutionary algorithm to control the supply of depots with optimization techniques to determine the delivery from depots to customers and the supply from manufacturing plants to depots. A computational experiment is carried out to assess the efficiency and robustness of the algorithm.     

价格下界随时间递增的占线采购问题

本文研究的是价格不确定且其下界随时间递增的原材料采购问题。在实际的原材料采购问题中，原材料的价格随时间的变动往往是不可预测的。之前的学者在研究价格不确定的占线采购问题时，假设价格在一个统一的常数上下界内，这没有考虑到经过时间的变化，价格的上下界可能也是变化的。本文提出并研究价格下界随时间递增的原材料占线采购问题。构建了相应数学模型，给出了相应的竞争采购策略并证明了竞争比，同时通过证明问题的匹配竞争比下界，说明给出的竞争采购策略是最优的，最后利用数值分析进一步说明竞争策略具有较好的竞争性能。     

Online interval scheduling: randomized and multiprocessor cases

We consider the problem of scheduling a set of equal-length intervals arriving online, where each interval is associated with a weight and the objective is to maximize the total weight of completed intervals. An optimal 4-competitive algorithm has long been known in the deterministic case, but the randomized case remains open. We give the first randomized algorithm for this problem, achieving a competitive ratio of 3.5822. We also prove a randomized lower bound of 4/3, which is an improvement over the previous 5/4 result. Then we show that the techniques can be carried to the deterministic multiprocessor case, giving a 3.5822-competitive 2-processor algorithm, and a 4/3 lower bound for any number of processors. We also give a lower bound of 2 for the case of two processors. A preliminary version of this paper appeared in the Proceedings of COCOON 2007, LNCS, vol. 4598, pp. 176–186. The work described in this paper was fully supported by a grant from City University of Hong Kong (SRG 7001969), and NSFC Grant No. 70525004 and 70702030.     

Constraining the number of positive responses in adaptive,non-adaptive,and two-stage group testing

Group testing is a well known search problem that consists in detecting the defective members of a set of objects O by performing tests on properly chosen subsets (pools) of the given set O. In classical group testing the goal is to find all defectives by using as few tests as possible. We consider a variant of classical group testing in which one is concerned not only with minimizing the total number of tests but aims also at reducing the number of tests involving defective elements. The rationale behind this search model is that in many practical applications the devices used for the tests are subject to deterioration due to exposure to or interaction with the defective elements. In this paper we consider adaptive, non-adaptive and two-stage group testing. For all three considered scenarios, we derive upper and lower bounds on the number of “yes” responses that must be admitted by any strategy performing at most a certain number t of tests. In particular, for the adaptive case we provide an algorithm that uses a number of “yes” responses that exceeds the given lower bound by a small constant. Interestingly, this bound can be asymptotically attained also by our two-stage algorithm, which is a phenomenon analogous to the one occurring in classical group testing. For the non-adaptive scenario we give almost matching upper and lower bounds on the number of “yes” responses. In particular, we give two constructions both achieving the same asymptotic bound. An interesting feature of one of these constructions is that it is an explicit construction. The bounds for the non-adaptive and the two-stage cases follow from the bounds on the optimal sizes of new variants of d-cover free families and (p, d)-cover free families introduced in this paper, which we believe may be of interest also in other contexts.     

A simplified algorithm for the depot location problem

This paper describes a simplified optimization algorithm used for the solution of a classical depot location problem as presented in a Greek Manufacturing Company. Algorithms in the literature for this type of problem are based on the assumption of predetermined fixed costs which are independent of the final size of the depots. This assumption is usually far from reality; the size of each depot does not remain constant during the optimization process and so does the associated fixed cost which is variable with the size of the depot. This assumption is relaxed in the proposed algorithm; the associated fixed cost is modified each time a new customer is allocated to a depot thus changing the required depot size.     

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.     

Pooling designs for clone library screening in?the?inhibitor complex model

In this paper we introduce inhibitors into the complex model and we give a lower bound and an upper bound of tests in a nonadaptive pooling design for some inhibitor complex model. We propose a very efficient pooling design for the general inhibitor complex model and extend it to the error-tolerant case.     

Income Maintenance and Labor Force Participation

The paper studies the optimal tax‐subsidy schedules in an economy where the only decision of the agents is to work, or not, with an application to the case of France. Given an income guarantee provided by the welfare state, the tax schedule that maximizes government revenue provides a benchmark, the Laffer bound, above which it is inefficient to tax. In fact, under mild conditions, a feasible allocation is second best optimal if and only if the associated taxes are lower than the Laffer bound. The only restriction that efficiency puts on the shape of the tax scheme is this upper Laffer bound. The Laffer tax scheme itself can be computed from the joint distribution of the agents' productivities and work opportunity costs. Depending on the economy, it can take widely different forms, and exhibit, for instance, negative marginal tax rates. After estimating the joint distribution of productivities and work opportunity costs on French data, I compute the Laffer bound for two subpopulations, single women and married women with two children or more. Quite surprisingly, the actual incentives to work appear to be very close to the bound.     

Management perspectives in physical distribution

Distribution problems may conveniently be divided into three categories—strategic, tactical and operational—and although each is bound to be affected by the others, they involve different time scales, different constraints and different requirements for information inputs. At a strategic level, models can be constructed for the rate of return on investment and for unit cost to help identify the major elements that affect performance, and in this way any specific change in given components in the distribution system can be traced and its possible effects can then be identified. Another strategic issue is the problem of depot location, and a particular feature of the number of depots in a distribution network is their effect on stock holding. In cases where 80–90% of total costs are independent of total mileage, it is more profitable to examine means for reducing fixed costs (including the size of the delivery fleet) than to invest an inordinate amount of resources on vehicle scheduling. However, the level of sophistication of distribution studies is likely to grow, as management becomes increasingly concerned about rising costs.     

Lower Bounds on Approximation Errors to Numerical Solutions of Dynamic Economic Models

We propose a novel methodology for evaluating the accuracy of numerical solutions to dynamic economic models. It consists in constructing a lower bound on the size of approximation errors. A small lower bound on errors is a necessary condition for accuracy: If a lower error bound is unacceptably large, then the actual approximation errors are even larger, and hence, the approximation is inaccurate. Our lower‐bound error analysis is complementary to the conventional upper‐error (worst‐case) bound analysis, which provides a sufficient condition for accuracy. As an illustration of our methodology, we assess approximation in the first‐ and second‐order perturbation solutions for two stylized models: a neoclassical growth model and a new Keynesian model. The errors are small for the former model but unacceptably large for the latter model under some empirically relevant parameterizations.     

Blocking Rumor by Cut

In this paper, a rumor blocking problem is studied with an objective function which is neither submodular or supermodular. We will prove that this problem is NP-hard and give a data-dependent approximation with sandwich method. In addition, we show that every set function has a pair of monotone nondecreasing modular functions as upper bound and lower bound, respectively.     

回载可分的闭环供应链多配送中心多车辆运输策略

本文从车辆路径的角度研究了具有多个配送中心、多台车辆结合前向物流配送和逆向物流回载的闭环供应链运输策略,考虑回收产品的不同形态和可分批运输的特点,引入库存限制和成本惩罚,建立并分析了问题的数学模型.运用sweep算法把多配送中心转化为单配送中心,引入2σ原则构造了分组的启发式求解方法.算例分析表明该策略的合理有效性.     

Tight bounds for NF-based bounded-space online bin packing algorithms

In Zheng et al. (J Comb Optim 30(2):360–369, 2015) modelled a surgery problem by the one-dimensional bin packing, and developed a semi-online algorithm to give an efficient feasible solution. In their algorithm they used a buffer to temporarily store items, having a possibility to lookahead in the list. Because of the considered practical problem they investigated the 2-parametric case, when the size of the items is at most 1 / 2. Using an NF-based online algorithm the authors proved an ACR of \(13/9 = 1.44\ldots \) for any given buffer size not less than 1. They also gave a lower bound of \(4/3=1.33\ldots \) for the bounded-space algorithms that use NF-based rules. Later, in Zhang et al. (J Comb Optim 33(2):530–542, 2017) an algorithm was given with an ACR of 1.4243,  and the authors improved the lower bound to 1.4230. In this paper we present a tight lower bound of \(h_\infty (r)\) for the r-parametric problem when the buffer capacity is 3. Since \(h_\infty (2) = 1.42312\ldots \), our result—as a special case—gives a tight bound for the algorithm-class given in 2017. To prove that the lower bound is tight, we present an NF-based online algorithm that considers the r-parametric problem, and uses a buffer with capacity of 3. We prove that this algorithm has an ACR that is equal to the lower bounds for arbitrary r.     

The price-setting newsvendor with service and loss constraints

Current performance measurement systems consider not only financial measures, like costs and profits, but also non-financial indicators with respect to customer service, quality and flexibility. Using the newsvendor model, we analyse the respective influence of these possibly conflicting performance measures on important operations and marketing decisions, for instance the order quantity and the selling price of a product. As in the classical newsvendor model for price-independent as well as price-dependent demand distribution, the objective of the firm is to maximise expected profit. In this paper, we also consider a service constraint—a lower bound for the level of product availability—and a loss constraint—an upper bound for the probability of a loss occurring. For both models, we provide conditions for the existence of solutions. We then analyse the influence of demand variability using a set of conditions specifying the quantiles of the predetermined performance measures: a higher variability of demand implies a smaller admissible region of the decision variables. In the price-independent case, the optimal solution has a control-limit structure: the optimal order quantity is thus given either by the classical newsvendor solution or by the control-limits corresponding to the constraints. In the price-setting model with multiplicative demand, this structure is used to check whether small admissible prices are determined by the service constraint or by the loss constraint. Using these structural results, a procedure is developed to more easily enable the computation of the optimal values of the order quantity, selling price and expected profit.     

The newsvendor problem with barter exchange

Barter exchange, as an alternative to move distressed inventory, has become increasingly popular in business. Many companies barter their unsold product for the product they need via barter exchange platforms at full prices. In this paper we consider the newsvendor problem with the barter exchange option. A retailer (the newsvendor) facing stochastic demand not only sells its product, but also buys other product that it needs from the market. It either trades its unsold product for the product it needs on a barter platform or disposes of its unsold product at discounted prices at the end of the selling season like in the classical newsvendor model. We derive the retailer’s optimal order quantity, then analytically and numerically examine the impacts of barter on the retailer’s inventory decisions and profit. We find that barter exchange can help the retailer to manage demand uncertainty and improve profit. The optimal order quantity decreases with barter commission and barter uncertainty, while increases with demand uncertainty and the value of the product that the retailer needs. Barter is more advantageous with lower barter commission, larger demand uncertainty, lower barter uncertainty, and higher value of the product it needs.     

A best first search exact algorithm for the Multiple-choice Multidimensional Knapsack Problem

In this paper, we propose an optimal algorithm for the Multiple-choice Multidimensional Knapsack Problem MMKP. The main principle of the approach is twofold: (i) to generate an initial feasible solution as a starting lower bound, and (ii) at different levels of the search tree to determine an intermediate upper bound obtained by solving an auxiliary problem called MMKP_aux and perform the strategy of fixing items during the exploration. The approach which we develop is of best-first search strategy. The method was able to optimally solve the MMKP. The performance of the exact algorithm is evaluated on a set of small and medium instances, some of them are extracted from the literature and others are randomly generated. This algorithm is parallelizable and it is one of its important feature.     

Online bin packing problem with buffer and bounded size revisited

In this paper we study the online bin packing with buffer and bounded size, i.e., there are items with size within \((\alpha ,1/2]\) where \(0 \le \alpha < 1/2 \), and there is a buffer with constant size. Each time when a new item is given, it can be stored in the buffer temporarily or packed into some bin, once it is packed in the bin, we cannot repack it. If the input is ended, the items in the buffer should be packed into bins too. In our setting, any time there is at most one bin open, i.e., that bin can accept new items, and all the other bins are closed. This problem is first studied by Zheng et al. (J Combin Optim 30(2):360–369, 2015), and they proposed a 1.4444-competitive algorithm and a lower bound 1.3333 on the competitive ratio. We improve the lower bound from 1.3333 to 1.4230, and the upper bound from 1.4444 to 1.4243.