Dynamic uncapacitated lot sizing with random demand under a fillrate constraint

This paper deals with the single-item dynamic uncapacitated lot sizing problem with random demand. We propose a model based on the “static uncertainty” strategy of Bookbinder and Tan (1988). In contrast to these authors, we use exact expressions for the inventory costs and we apply a fillrate constraint. We present an exact solution method and modify several well-known dynamic lot sizing heuristics such that they can be applied for the case of dynamic stochastic demands. A numerical experiment shows that there are significant differences in the performance of the heuristics whereat the ranking of the heuristics is different from that reported for the case of deterministic demand.     

Offsetting inventory replenishment cycles to minimize storage space

In a recent paper, [Murthy, N.N., Benton, W.C., Rubin, P.A., 2003. Offsetting inventory cycles of items sharing storage. European Journal of Operational Research 150, 304–319] discussed the problem of offsetting inventory replenishment cycles of several items in order to minimize the maximum required storage space. They analyzed the case where replenishment cycles are given integer multiples of a basic period and proposed a heuristic to solve the problem. While they provided a good analysis of the considered problem, the proposed heuristic produces less interesting results. In the following, a simpler, more efficient and easier to implement heuristic is proposed. Numerical results are provided to prove its superiority.     

A comparison of inventory policies for perishable goods

Past research on inventory management of perishables introduced models in which demand is sensitive to the age of the product. For such models, we prove that a fixed-order quantity policy is optimal under certain conditions and show that its expected cost is closer to optimal than that of the base-stock level policy when there is demand for units of all ages. We also show numerically when substituting older products to fulfill the demand for new (or vice versa) is beneficial.     

A heuristic solution technique to attain the minimal total cost bounds of transporting a homogeneous product with varying demands and supplies

Transportation of a product from multi-source to multi-destination with minimal total transportation cost plays an important role in logistics and supply chain management. Researchers have given considerable attention in minimizing this cost with fixed supply and demand quantities. However, these quantities may vary within a certain range in a period due to the variation of the global economy. So, the concerned parties might be more interested in finding the lower and the upper bounds of the minimal total costs with varying supplies and demands within their respective ranges for proper decision making. This type of transportation problem has received attention of only one researcher, who formulated the problem and solved it by LINGO. We demonstrate that this method fails to obtain the correct upper bound solution always. Then we extend this model to include the inventory costs during transportation and at destinations, as they are interrelated factors. The number of choices of supplies and demands within their respective ranges increases enormously as the number of suppliers and buyers increases. In such a situation, although the lower bound solution can be obtained methodologically, determination of the upper bound solution becomes an NP hard problem. Here we carry out theoretical analyses on developing the lower and the upper bound heuristic solution techniques to the extended model. A comparative study on solutions of small size numerical problems shows promising performance of the current upper bound technique. Another comparative study on results of numerical problems demonstrates the effect of inclusion of the inventory costs.     

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.     

多产品单层能力受限批量问题的前向启发式算法的可行性过程

本文讨论多产品、单层、能力受限批量问题的前向启发式算法,指出了这类算法中现有算法的一些不足之处。为了克服这些不足,我们给出了可行解存在的充分必要条件,并在此基础上提出一个可行化算法。     

Periodic review lost-sales inventory models with compound Poisson demand and constant lead times of any length

In almost all literature on inventory models with lost sales and periodic reviews the lead time is assumed to be either an integer multiple of or less than the review period. In a lot of practical settings such restrictions are not satisfied. We develop new models allowing constant lead times of any length when demand is compound Poisson. Besides an optimal policy, we consider pure and restricted base-stock policies under new lead time and cost circumstances. Based on our numerical results we conclude that the latter policy, which imposes a restriction on the maximum order size, performs almost as well as the optimal policy. We also propose an approximation procedure to determine the base-stock levels for both policies with closed-form expressions.     

Incorporating quantity discounts and their inventory impacts into the centralized purchasing decision

Multi-site organizations must balance conflicting forces to determine the appropriate degree of purchasing centralization for their respective supplies. The ability to garner quantity discounts represents one of the primary reasons that organizations centralize procurement. This paper provides methodologies to calculate optimal order quantities and compute total purchasing and inventory costs when products have quantity discount pricing. Procedures for both all-units and incremental quantity discount schedules are provided for four different strategic purchasing configurations (scenarios): complete decentralization, centralized pricing with decentralized purchasing, centralized purchasing with local distribution, and centralized purchasing and warehousing. For ordering decisions under local distribution, procedures to determine optimal order quantities and costs are presented in a precise form that could be easily implemented into spreadsheets by practicing managers. For the more complicated multi-echelon scenarios, we introduce a single-cycle policy with a tailored aggregation refinement step that performs very well under experimentation when compared to a conservative bound.     

Maritime inventory routing with multiple products: A case study from the cement industry

This paper considers a maritime inventory routing problem faced by a major cement producer. A heterogeneous fleet of bulk ships transport multiple non-mixable cement products from producing factories to regional silo stations along the coast of Norway. Inventory constraints are present both at the factories and the silos, and there are upper and lower limits for all inventories. The ship fleet capacity is limited, and in peak periods the demand for cement products at the silos exceeds the fleet capacity. In addition, constraints regarding the capacity of the ships’ cargo holds, the depth of the ports and the fact that different cement products cannot be mixed must be taken into consideration. A construction heuristic embedded in a genetic algorithmic framework is developed. The approach adopted is used to solve real instances of the problem within reasonable solution time and with good quality solutions.     

Emergency response in natural disaster management: Allocation and scheduling of rescue units

Natural disasters, such as earthquakes, tsunamis and hurricanes, cause tremendous harm each year. In order to reduce casualties and economic losses during the response phase, rescue units must be allocated and scheduled efficiently. As this problem is one of the key issues in emergency response and has been addressed only rarely in literature, this paper develops a corresponding decision support model that minimizes the sum of completion times of incidents weighted by their severity. The presented problem is a generalization of the parallel-machine scheduling problem with unrelated machines, non-batch sequence-dependent setup times and a weighted sum of completion times – thus, it is NP-hard. Using literature on scheduling and routing, we propose and computationally compare several heuristics, including a Monte Carlo-based heuristic, the joint application of 8 construction heuristics and 5 improvement heuristics, and GRASP metaheuristics. Our results show that problem instances (with up to 40 incidents and 40 rescue units) can be solved in less than a second, with results being at most 10.9% up to 33.9% higher than optimal values. Compared to current best practice solutions, the overall harm can be reduced by up to 81.8%.     

Component rationing for available-to-promise scheduling in configure-to-order systems

We address the problem of rationing common components among multiple products in a configure-to-order system with order configuration uncertainty. The objective of this problem is to maximize expected revenue by implementing a threshold rationing policy. Under this policy, a product is available to promise if fulfilling the order for the product will not cause the inventory of any one of its required components to fall below the component’s threshold level for that product. The problem is modeled as a two-stage stochastic integer program and solved using the sample average approximation approach. A heuristic is developed to generate good feasible solutions and lower bound estimates. Using industry data, we examine the benefit of component rationing as compared to a First-Come-First-Served policy and show that this benefit is correlated to the average revenue per product and the variability in the revenue across products whose components are constrained.     

A study of heuristic combinations for hyper-heuristic systems for the uncapacitated examination timetabling problem

Research in the domain of examination timetabling is moving towards developing methods that generalise well over a range of problems. This is achieved by implementing hyper-heuristic systems to find the best heuristic or heuristic combination to allocate examinations when constructing a timetable for a problem. Heuristic combinations usually take the form of a list of low-level heuristics that are applied sequentially. This study proposes an alternative representation for heuristic combinations, namely, a hierarchical combination of heuristics. Furthermore, the heuristics in each combination are applied simultaneously rather than sequentially. The study also introduces a new low-level heuristic, namely, highest cost. A set of heuristic combinations of this format have been tested on the 13 Carter benchmarks. The quality of the examination timetables induced using these combinations are comparable to, and in some cases better than, those produced by hyper-heuristic systems combining and applying heuristic combinations sequentially.     

A five facet frame for the design of heuristics —A rejoinder

An argument was put forward by Stainton and Papoulias for an additional category of heuristics to those proposed by Müller-Merbach, which the authors called ‘relational’. In response to the subsequent suggestion by Müller-Merbach of a five facet frame for the design of heuristics, this paper sets out to expand upon and clarify the characteristics of the relational approach, as defined by the authors.     

Replenishment routing problems between a single supplier and multiple retailers with direct delivery

We consider the replenishment routing problems of one supplier who can replenish only one of multiple retailers per period, while different retailers need different periodical replenishment. For simple cases satisfying certain conditions, we obtain the simple routing by which the supplier can replenish each retailer periodically so that shortage will not occur. For complicated cases, using number theory, especially the Chinese remainder theorem, we present an algorithm to calculate a feasible routing so that the supplier can replenish the selected retailers on the selected periods without shortages.     

Constructions from empty polygons

Let P denote a finite set of points, in general position in the plane. In this note we study conditions which guarantee that P contains the vertex set of a convex polygon that has exactly k points of P in its interior.     

A comparison of algorithm RS with algorithm OPTSOL70

In a very recent paper (Almiñana and Pastor (1997)) we proposed a new lagrangian surrogate heuristic, called RS, for solving the location (or unicost) set covering problem. In that paper we show that RS is more accurate than the pair of greedy type heuristics FMC/CMA and that RS outperforms the surrogate heuristic SH. Here we are going to compare algorithms RS with the best designed hybrid algorithm for the location set covering problem, known as OPTSOL70.     

Worst case analysis of greedy and related heuristics for some min-max combinatorial optimization problems

Min-max problems on matroids are NP-hard for a wide variety of matroids. However, greedy type algorithms have data independent worst case performance guarantees, andn-enumerative algorithms yield-optimal solutions ifn is sufficiently close to the rank of the underlying matroid. Data dependent performance guarantees can be obtained for max-min problems over matroids.This research was partially supported by NSERC Grant A5543.     

Trade-off between capacity invested and inventory needed

A multi-item capacitated make-to-order production system with considerable demand fluctuations is discussed. The relationship between the available capacity and the inventory needed to meet customer requirements with a pre-defined service level is modeled. Furthermore, the total cost for both capacity and inventory is minimized and it is shown that, assuming negligible change-over times, the double of the surplus inventory cost has to be equal to the excess capacity cost to ensure minimum total cost.     

Finding preferred subsets of Pareto optimal solutions

Multi-objective optimization algorithms can generate large sets of Pareto optimal (non-dominated) solutions. Identifying the best solutions across a very large number of Pareto optimal solutions can be a challenge. Therefore it is useful for the decision-maker to be able to obtain a small set of preferred Pareto optimal solutions. This paper analyzes a discrete optimization problem introduced to obtain optimal subsets of solutions from large sets of Pareto optimal solutions. This discrete optimization problem is proven to be NP-hard. Two exact algorithms and five heuristics are presented to address this problem. Five test problems are used to compare the performances of these algorithms and heuristics. The results suggest that preferred subset of Pareto optimal solutions can be efficiently obtained using the heuristics, while for smaller problems, exact algorithms can be applied.     

Genetic algorithm with variable neighborhood search for the optimal allocation of goods in shop shelves

Shelves on which products are being displayed are one of the most important resources in retail environment. The decision of shelf-space allocation and management is therefore a critical issue in retail operation management. In this paper a hybrid algorithm that combines a genetic algorithm with a variable neighborhood search is proposed to address the shop shelf allocation problem. Results obtained from an extensive experimental phase show the suitability of the proposed algorithm in addressing the problem at hand.