The Trended Inventory Lot Sizing Problem with Shortages Under a New Replenishment Policy

In the past few years, considerable attention has been given to the inventory lot sizing problem with trended demand over a fixed horizon. The traditional replenishment policy is to avoid shortages in the last cycle. Each of the remaining cycles starts with a replenishment and inventory is held for a certain period which is followed by a period of shortages. A new replenishment policy is to start each cycle with shortages and after a period of shortages a replenishment should be made. In this paper, we show that this new type of replenishment policy is superior to the traditional one. We further propose four heuristic procedures that follow the new replenishment policy. These are the constant demand approximation method, the equal cycle length heuristic, the extended Silver approach, and the extended least cost solution procedure. We also examine the cost and computation time performances of these heuristic procedures through an empirical study. The number of test problems solved to optimality, average and maximum cost deviation from optimum were used as measures of cost performance. The results of the 10 000 test problems reveal that the extended least cost approach is most cost effective.     

Effective heuristics for the dynamic demand joint replenishment problem

This paper considers the dynamic demand joint replenishment problem where there is a joint setup cost in each time period when any member of the product family is replenished and a separate setup cost for each different item replenished. We present two forward-pass heuristics, a two-phase heuristic, and a simulated annealing metaheuristic (SAM) and investigate their relative effectiveness in solving a comprehensive set of test problems. The experimental results indicate the two-phase heuristic and the SAM perform better than existing approaches for the problem.     

An efficient optimal solution method for the joint replenishment problem

During the last two decades, many heuristic procedures for the joint replenishment problem have appeared in the literature. The only available optimal solution procedure was based on an enumerative approach and was computationally prohibitive. In this paper we present an alternative optimal approach based on global optimisation theory. By applying Lipschitz optimisation one can find a solution with an arbitrarily small deviation from an optimal value. An efficient procedure is presented which uses a dynamic Lipschitz constant and generates a solution in little time. The running time of this procedure grows only linearly in the number of items.     

The multi-item newsvendor problem with a budget constraint and fixed ordering costs

This paper deals with a multi-item newsvendor problem subject to a budget constraint on the total value of the replenishment quantities. Fixed costs for non-zero replenishments have been explicitly considered. Dynamic programming procedures are presented for two situations: (i) where the end item demand distributions are assumed known (illustrated for the case of normally distributed demand) and (ii) a distribution free approach where only the first two moments of the distributions are assumed known. In addition, simple and efficient heuristic algorithms have been developed. Computational experiments show that the performance of the heuristics are excellent based on a set of test problems.     

考虑顾客退货和固定成本的联合补货与定价策略

为了吸引更多顾客,许多电子商务零售商允许顾客在一定时间内退货,导致其利润明显减少。同时,在补货时不仅产生依赖补货量的变动成本,而且会产生与补货量无关的固定成本。基于此,以最大化电子商务零售商的利润为目标,建立考虑顾客退货和固定成本的联合补货与定价模型,其中顾客的退货量与满足的需求呈正比。在一般需求情形下,部分刻画多期问题的最优策略;在特殊需求情形下,证明(s,S,p)策略对单期问题最优,并对多期问题的最优策略进行严格刻画。根据已有刻画为多期问题构造启发式策略。数值结果表明启发式策略近似最优;当初始库存水平足够高/低时,最优补货水平和定价随退货率与固定成本单调变化。关键词:联合补货与定价模型;顾客退货;固定成本;随机动态规划;最优策略     

Heuristic Methods for the Multi-product Dynamic Lot Size Problem

Many heuristics exist for the single-item dynamic lot-size problem, for example, the Silver-Meal, the part period balancing and a simple variant of the part period balancing. The worst case performances of these heuristics have been shown to be zero, 1/3 and 1/2 respectively. These heuristics can be generalized to the dynamic version of the joint replenishment problem, that is, the multi-product dynamic lot-size problem. Such a generalization of the Silver-Meal heuristic has been shown to perform well on a set of test problems. This paper generalizes the part period balancing heuristic, and a simple variant of it to the multiproduct dynamic lot-size problem, and shows that the worst case performances of the generalized heuristics remain 1/3 and 1/2 respectively. An improved version of the generalized Silver-Meal heuristic is also given.     

Separate vs. joint replenishment policies with maximum storage requirement costs

Multi-item inventory problems give rise to the possibility of time-phasing the replenishments of different items over the inventory cycle. Such a policy reduces the peak storage requirement, compared to a policy of simultaneous replenishment. This, in turn, increases the amount of warehouse space which is permanently available for leasing throughout the cycle. However, where cost savings may be achieved through combining setups of different items, as in the well known joint replenishment problem, such a time-phasing policy may increase total setup costs. This paper considers the two item joint replenishment problem, where a cost (equivalent to the opportunity cost of warehouse space) attaches to the peak storage requirement which occurs within the inventory cycle. Existing joint replenishment models do not consider such costs, but their consideration suggests that joint replenishment is not always optimal. We analyze possible policies under both joint and separate replenishment, and provide optimal closed form solutions. A numerical example to illustrate the tradeoff between joint and separate replenishment is provided.     

An optimal solution technique for the joint replenishment problem with storage and transport capacities and budget constraints

The joint replenishment problem, which is concerned with the problem of coordinating the replenishment of a group of items that may be ordered jointly, has been studied extensively and many heuristic solution procedures have been presented in the literature. To obtain the minimum of the total cost, the main complexity lies in determining the appropriate lower bound of the basic cycle time. Also there is a lack of a global optimal solution technique of the problem. This paper presents its extended model to include some practical issues and develops a simple procedure to calculate the appropriate lower bound of the basic cycle time. By a comparative study of a numerical example, it demonstrates the inabilities of the available lower bound formulae in the literature. It also develops a generalized global optimal solution algorithm of the extended model and illustrates this with a numerical example. Then a comparative study of the results of seven numerical examples is carried out to highlight the global optimality of the solution technique.     

The coordinated replenishment dynamic lot-sizing problem with quantity discounts

In the classical coordinated replenishment dynamic lot-sizing problem, the primary motivation for coordination is in the presence of the major and minor setup costs. In this paper, a separate element of coordination made possible by the offer of quantity discounts is considered. A mathematical programming formulation for the extended problem under the all-units discount price structure and the incremental discount price structure is provided. Then, using variable redefinitions, tighter formulations are presented in order to obtain tight lower bounds for reasonable size problems. More significantly, as the problem is NP-hard, we present an effective polynomial time heuristic procedure, for the incremental discount version of the problem, that is capable of solving reasonably large size problems. Computational results for the heuristic procedure are reported in the paper.     

A New Heuristic for the Quadratic Assignment Problem

We propose a new heuristic for the solution of the quadratic assignment problem. The heuristic combines ideas from tabu search and genetic algorithms. Run times are very short compared with other heuristic procedures. The heuristic performed very well on a set of test problems.     

A heuristic for the multi-period petrol station replenishment problem

In the multi-period petrol station replenishment problem (MPSRP) the aim is to optimize the delivery of several petroleum products to a set of petrol stations over a given planning horizon. One must determine, for each day of the planning horizon, how much of each product should be delivered to each station, how to load these products into vehicle compartments, and how to plan vehicle routes. The objective is to maximize the total profit equal to the revenue, minus the sum of routing costs and of regular and overtime costs. This article describes a heuristic for the MPSRP. It contains a route construction and truck loading procedures, a route packing procedure, and two procedures enabling the anticipation or the postponement of deliveries. The heuristic was extensively tested on randomly generated data and compared to a previously published algorithm. Computational results confirm the efficiency of the proposed methodology.     

A dynamic joint replenishment policy with auto-correlated demand

We consider a joint replenishment problem where the product demands are auto-correlated but independent of each other. A dynamic periodic review policy is developed, and its parameters are determined by a heuristic which aims at minimizing the total inventory cost, which includes the holding cost, the set up cost and the shortage cost. The heuristic updates the review interval and the target inventory level of every product at each review point based on the current inventory status and the past demand data. A simulation model is developed to compare the performance of this proposed policy with an existing periodic review policy. The results show that the proposed policy has consistently achieved significant saving in all the different experimental scenarios.     

A partial enumeration heuristic for multi-objective flowshop scheduling problems

This paper addresses the flowshop scheduling problem with multiple performance objectives in such a way as to provide the decision maker with approximate Pareto optimal solutions. It is well known that the partial enumeration constructive heuristic NEH and its adaptations perform well for single objectives such as makespan, total tardiness and flowtime. In this paper, we develop a similar heuristic using the concept of Pareto dominance when comparing partial and complete schedules. The heuristic is tested on problems involving combinations of the above criteria. For the two-machine case, and the pairs of objectives: (i) makespan and maximum tardiness, (ii) makespan and total tardiness, the heuristic is compared with branch-and-bound algorithms proposed in the literature. For two and more than two machines, and the criteria combinations considered in this article, the heuristic performance is tested against constructive heuristics reported in the literature. By means of an illustrative example, it is shown that a genetic algorithm from the literature performs better when starting from heuristic solutions rather than random solutions.     

Generating quadratic assignment test problems with known optimal permutations

The quadratic assignment problem (QAP) is a well-known combinatorial optimization problem of which the travelling-salesman problem is a special case. Although the QAP has been extensively studied during the past three decades, this problem remains very hard to solve. Problems of sizes greater than 15 are generally impractical to solve. For this reason, many heuristics have been developed. However, in the literature, there is a lack of test problems with known optimal solutions for evaluating heuristic algorithms. Only recently Paulubetskis proposed a method to generate test problems with known optimal solutions for a special type of QAP. This paper concerns the generation of test problems for the QAP with known optimal permutations. We generalize the result of Palubetskis and provide test-problem generators for more general types of QAPs. The test-problem generators proposed are easy to implement and were also tested on several well-known heuristic algorithms for the QAP. Computatinal results indicate that the test problems generated can be used to test the effectiveness of heuristic algorithms for the QAP. Comparison with Palubetskis' procedure was made, showing the superiority of the new test-problem generators. Three illustrative test problems of different types are also provided in an appendix, together with the optimal permutations and the optimal objective function values.     

Single machine earliness and tardiness scheduling

We examine the problem of scheduling a given set of jobs on a single machine to minimize total early and tardy costs without considering machine idle time. We decompose the problem into two subproblems with a simpler structure. Then the lower bound of the problem is the sum of the lower bounds of two subproblems. A lower bound of each subproblem is obtained by Lagrangian relaxation. Rather than using the well-known subgradient optimization approach, we develop two efficient multiplier adjustment procedures with complexity O(nlog n) to solve two Lagrangian dual subproblems. A branch-and-bound algorithm based on the two efficient procedures is presented, and is used to solve problems with up to 50 jobs, hence doubling the size of problems that can be solved by existing branch-and-bound algorithms. We also propose a heuristic procedure based on the neighborhood search approach. The computational results for problems with up to 3 000 jobs show that the heuristic procedure performs much better than known heuristics for this problem in terms of both solution efficiency and quality. In addition, the results establish the effectiveness of the heuristic procedure in solving realistic problems to optimality or near optimality.     

Single vehicle routing with predefined client sequence and multiple warehouse returns: the case of two warehouses

We examine three interesting cases of the single vehicle routing problem with a predefined client sequence and two load replenishment warehouses. Given the location and demand of the clients, we seek the minimal cost route, which includes optimal load replenishment visits to the warehouses in order to fully satisfy the client demand. The cases studied vary with respect to inventory availability at each warehouse and are of increasing complexity. We have developed solution algorithms that address this complexity, ranging from a standard dynamic programming algorithm for the simplest case, to labeling algorithms and a new partitioning heuristic. The efficiency of these algorithms has been studied by solving a wide range of problem instances, and by comparing the results with those obtained from a state-of-the-art MILP solver.     

Capacitated replenishment and disposal planning for multiple products with resalable returns

We consider a replenishment and disposal planning problem (RDPP) that arises in settings where customer returns are in as-good-as-new condition. These returns can be placed into inventory to satisfy future demand or can be disposed of, in case they lead to excess inventory. Our focus is on a multi-product setting with dynamic demands and returns over a finite planning horizon with explicit replenishment and disposal capacities. The problem is to determine the timing of replenishment and disposal setups, along with the associated quantities for the products, so as to minimize the total costs of replenishment, disposal, and inventory holding throughout the planning horizon. We examine two variants of the RDPP of interest both of which are specifically motivated by a spare part kitting application. In one variant, the replenishment capacity is shared among multiple products while the disposal capacity is product specific. In the other variant, both the replenishment and disposal capacities are shared among the products. We propose a Lagrangian Relaxation approach that relies on the relaxation of the capacity constraints and develop a smoothing heuristic that uses the solution of the Lagrangian problem to obtain near-optimal solutions. Our computational results demonstrate that the proposed approach is very effective in obtaining high-quality solutions with a reasonable computational effort.     

Augmenting the lot sizing order quantity when demand is probabilistic

In this paper we consider a single item, discrete time, lot sizing situation where demand is random and its parameters (e.g., mean and standard deviation) can change with time. For the appealing criterion of minimizing expected total relevant costs per unit time until the moment of the next replenishment we develop two heuristic ways of selecting an appropriate augmentation quantity beyond the expected total demand through to the planned (deterministic) time of the next replenishment. The results of a set of numerical experiments show that augmentation is important, particularly when orders occur frequently (i.e., the fixed cost of a replenishment is low relative to the costs of carrying one period of demand in stock) and the coefficient of variability of demand is relatively low, but also under other specified circumstances. The heuristic procedures are also shown to perform very favourably against a hindsight, baseline (s, S) policy, especially for larger levels of non-stationarity.     

The travelling salesperson problem with hotel selection

In this paper, we present the travelling salesperson problem with hotel selection (TSPHS), an extension of the TSP with a number of interesting applications. We present a mathematical formulation, explain the difference with related optimization problems and indicate what makes this problem inherently more difficult. We develop a simple but efficient heuristic that uses two constructive initialization procedures and an improvement procedure consisting of several neighbourhood search operators designed specifically for this problem, as well as some typical neighbourhoods from the literature. We generate several benchmark instances of varying sizes and compare the performance of our heuristic with CPLEX (10.0). We also generate some problems with known optimal solutions and use these to further demonstrate that our heuristic achieves good results in very limited computation times.