Lot‐sizing Decisions Under Limited‐time Price Reduction*

We consider the optimal lot‐sizing policy for an inventoried item when the vendor offers a limited‐time price reduction. We use the discounted cash flow (DCF) approach in our analysis, thereby eliminating the sources of approximation found in most of the earlier studies that use an average annual cost approach. We first characterize the optimal lot‐sizing policies and their properties, then develop an algorithm for determining the optimal lot sizes. We analytically demonstrate that the lot sizes derived using an average annual cost approach for the different variants of the problem are, in general, larger than the DCF optimum. While DCF analysis is more rigorous and yields precise lot sizes, we recognize that the associated mathematical models and the solution procedure are rather complex. Since simple and easy‐to‐understand policies have a strong practical appeal to decision makers, we propose a DCF version of a simple and easy‐to‐implement heuristic called the “Early Purchase” (EP) strategy and discuss its performance. We supplement our analytical developments with a detailed computational analysis and discuss the implications of our findings for decision making.     

Approximation Algorithms for the Multiple Knapsack Problem with Assignment Restrictions

Motivated by a real world application, we study the multiple knapsack problem with assignment restrictions (MKAR). We are given a set of items, each with a positive real weight, and a set of knapsacks, each with a positive real capacity. In addition, for each item a set of knapsacks that can hold that item is specified. In a feasible assignment of items to knapsacks, each item is assigned to at most one knapsack, assignment restrictions are satisfied, and knapsack capacities are not exceeded. We consider the objectives of maximizing assigned weight and minimizing utilized capacity.We focus on obtaining approximate solutions in polynomial computational time. We show that simple greedy approaches yield 1/3-approximation algorithms for the objective of maximizing assigned weight. We give two different 1/2-approximation algorithms: the first one solves single knapsack problems successively and the second one is based on rounding the LP relaxation solution. For the bicriteria problem of minimizing utilized capacity subject to a minimum requirement on assigned weight, we give an (1/3,2)-approximation algorithm.     

End‐of‐Life Inventory Problem with Phaseout Returns

We consider the service parts end‐of‐life inventory problem of a capital goods manufacturer in the final phase of its life cycle. The final phase starts as soon as the production of parts terminates and continues until the last service contract expires. Final order quantities are considered a popular tactic to sustain service fulfillment obligations and to mitigate the effect of obsolescence. In addition to the final order quantity, other sources to obtain serviceable parts are repairing returned defective items and retrieving parts from phaseout returns. Phaseout returns happen when a customer replaces an old system platform with a next‐generation one and returns the old product to the original equipment manufacturer (OEM). These returns can well serve the demand for service parts of other customers still using the old generation of the product. In this study, we study the decision‐making complications as well as cost‐saving opportunities stemming from phaseout occurrence. We use a finite‐horizon Markov decision process to characterize the structure of the optimal inventory control policy. We show that the optimal policy consists of a time‐varying threshold level for item repair. Furthermore, we study the value of phaseout information by extending the results to cases with an uncertain phaseout quantity or an uncertain schedule. Numerical analysis sheds light on the advantages of the optimal policy compared to some heuristic policies.     

Coordinating replenishments in a supply chain with quality control considerations

We study the impact of coordinated replenishment, a popular supply chain initiative, on a quality control system. We use the (Q, S) policy to manage a two-item inventory control system. If the items are jointly replenished, the number ordered for each item varies from lot to lot. As the number varies, the sampling plan will also be changed. Companies have to determine sampling plans to minimize quality cost when the order is mixed with several items and the number of each item varies from order to order. Management's primary concern is to determine the optimal sampling sizes and acceptance numbers for all items in an order.     

EFFECTS OF RANDOM SHIFTS OF TESTING EQUIPMENT ON PROCESS CONTROL SYSTEM DESIGN AND SELECTION OF PROCESS CONTROL POLICIES*

This paper studies issues associated with designing process control systems when the testing equipment is subjected to random shifts. We consider a production process with two states: in control and out of control. The process may shift randomly to the out‐of‐control state over time. The process is monitored by periodically sampling finished items from the process. The equipment used to test sampled items also is assumed to have two states and may shift randomly during the testing process. We formulate a cost model for finding the optimal process control policy that minimizes the expected unit time cost. Numerical results show that shifts of the testing equipment may significantly affect the performance of a process control policy. We also studied the effects of the testing equipment's shifts on the selection of process control policies.     

Process Mean Determination with Quantity Discounts in Raw Material Cost*

Setting the mean (target value) for a container-filling process is an important decision for a producer when the material cost is a significant portion of the production cost. Because the process mean determines the process conforming rate, it affects other production decisions, including, in particular, the production setup and raw material procurement policies. In this paper, we consider the situation in which quantity discounts exist in the raw material acquisition cost, and incorporate the quantity-discount issue into an existing model that was developed for simultaneously determining the process mean, production setup, and raw material procurement policies for a container-filling process. The product of interest is assumed to have a lower specification limit, and the items that do not conform to the specification limit are scrapped with no salvage value. The production cost of an item is proportional to the amount of the raw material used in producing the item. A two-echelon model is formulated for a single-product production process, and an algorithm is developed for finding the optimal solution. A sensitivity analysis is performed to study the effects of the model parameters on the optimal solution.     

Approximability of the subset sum reconfiguration problem

The subset sum problem is a well-known NP-complete problem in which we wish to find a packing (subset) of items (integers) into a knapsack with capacity so that the sum of the integers in the packing is at most the capacity of the knapsack and at least a given integer threshold. In this paper, we study the problem of reconfiguring one packing into another packing by moving only one item at a time, while at all times maintaining the feasibility of packings. First we show that this decision problem is strongly NP-hard, and is PSPACE-complete if we are given a conflict graph for the set of items in which each vertex corresponds to an item and each edge represents a pair of items that are not allowed to be packed together into the knapsack. We then study an optimization version of the problem: we wish to maximize the minimum sum among all packings in a reconfiguration. We show that this maximization problem admits a polynomial-time approximation scheme, while the problem is APX-hard if we are given a conflict graph.     

Coordinated Logistics: Joint Replenishment with Capacitated Transportation for a Supply Chain

In this study, we consider the integrated inventory replenishment and transportation operations in a supply chain where the orders placed by the downstream retailer are dispatched by the upstream warehouse via an in‐house fleet of limited size. We first consider the single‐item single‐echelon case where the retailer operates with a quantity based replenishment policy, (r,Q), and the warehouse is an ample supplier. We model the transportation operations as a queueing system and derive the operating characteristics of the system in exact terms. We extend this basic model to a two‐echelon supply chain where the warehouse employs a base‐stock policy. The departure process of the warehouse is characterized in distribution, which is then approximated by an Erlang arrival process by matching the first two moments for the analysis of the transportation queueing system. The operating characteristics and the expected cost rate are derived. An extension of this system to multiple retailers is also discussed. Numerical results are presented to illustrate the performance and the sensitivity of the models and the value of coordinating inventory and transportation operations.     

Replenishment Policies for Multi‐Product Stochastic Inventory Systems with Correlated Demand and Joint‐Replenishment Costs

This study analyzes optimal replenishment policies that minimize expected discounted cost of multi‐product stochastic inventory systems. The distinguishing feature of the multi‐product inventory system that we analyze is the existence of correlated demand and joint‐replenishment costs across multiple products. Our objective is to understand the structure of the optimal policy and use this structure to construct a heuristic method that can solve problems set in real‐world sizes/dimensions. Using an MDP formulation we first compute the optimal policy. The optimal policy can only be computed for problems with a small number of product types due to the curse of dimensionality. Hence, using the insight gained from the optimal policy, we propose a class of policies that captures the impact of demand correlation on the structure of the optimal policy. We call this class (s, c, d, S)‐policies, and also develop an algorithm to compute good policies in this class, for large multi‐product problems. Finally using an exhaustive set of computational examples we show that policies in this class very closely approximate the optimal policy and can outperform policies analyzed in prior literature which assume independent demand. We have also included examples that illustrate performance under the average cost objective.     

A Model for Resource Constrained Production and Inventory Management

We present a general model for multi-item production and inventory management problems that include a resource restriction. The decision variables in the model can take on a variety of interpretations, but will typically represent cycle times, production batch sizes, number of production runs, or order quantities for each item. We consider environments where item demand rates are approximately constant and performing an activity such as producing a batch of a product or placing an order results in the consumption of a scarceresource that is shared among the items. Some examples of shared resources include limited machine capacity, a restriction on the amount of money that can be tied up in stock, orlimited storage capacity. We focus on the case where the decision variables must be integer valued or selected from a discrete set of choices, such as when an integer number of production runs is desired for each item, or in order quantity problems where the items come in pack sizes containing more than one unit and, therefore, the order quantities must be an integer multiple of the pack sizes. We develop a heuristic and a branch and bound algorithm for solving the problem. The branch and bound algorithm includes reoptimization procedures and the heuristic to improve its performance. Computational testing indicates that the algorithms are effective for solving the general model.     

A simple integrated production policy of an imperfect item for vendor and buyer

This article develops a simple approach for determining an optimal integrated vendor–buyer inventory policy for an item with imperfect quality. The objective is to minimize the total joint annual costs incurred by the vendor and the buyer. This model is assumed to produce a certain number of defective items during the production process. Items of poor quality detected in the screening process of a lot are sold at a discounted price. The expected annual integrated total cost function is derived and a solution procedure is proposed to determine the optimal policy. Finally, a numerical example is also given to illustrate the solution procedure presented in this article.     

Optimal Acquisition and Sorting Policies for Remanufacturing

The condition of the used items acquired by remanufacturers is often highly variable, and sorting is an important aspect of remanufacturing operations. Sorting policies—the rules specifying which used products should be remanufactured and which should be scrapped—have received limited attention in the literature. In this paper, we examine the case of a remanufacturer who acquires unsorted used products as needed from third party brokers. As more used items are acquired for a given demand, the remanufacturer can be more selective when sorting. Thus, two related decisions are made: how many used items to acquire, and how selective to be during the sorting process. We derive optimal acquisition and sorting policies in the presence of used product condition variability for a remanufacturer facing both deterministic and uncertain demand. We show the existence of a single optimal acquisition and sorting policy with a simple structure and show that this policy is independent of production amount when acquisition costs are linear.     

Machine learning for multi-criteria inventory classification applied to intermittent demand

Multi-criteria inventory classification groups inventory items into classes, each of which is managed by a specific re-order policy according to its priority. However, the tasks of inventory classification and control are not carried out jointly if the classification criteria and the classification approach are not robustly established from an inventory-cost perspective. Exhaustive simulations at the single item level of the inventory system would directly solve this issue by searching for the best re-order policy per item, thus achieving the subsequent optimal classification without resorting to any multi-criteria classification method. However, this would be very time-consuming in real settings, where a large number of items need to be managed simultaneously.

In this article, a reduction in simulation effort is achieved by extracting from the population of items a sample on which to perform an exhaustive search of best re-order policies per item; the lowest cost classification of in-sample items is, therefore, achieved. Then, in line with the increasing need for ICT tools in the production management of Industry 4.0 systems, supervised classifiers from the machine learning research field (i.e. support vector machines with a Gaussian kernel and deep neural networks) are trained on these in-sample items to learn to classify the out-of-sample items solely based on the values they show on the features (i.e. classification criteria). The inventory system adopted here is suitable for intermittent demands, but it may also suit non-intermittent demands, thus providing great flexibility. The experimental analysis of two large datasets showed an excellent accuracy, which suggests that machine learning classifiers could be implemented in advanced inventory classification systems.     

Sensitivity of the Optimum to Perturbations of the Profit or Weight of an Item in the Binary Knapsack Problem

In the binary single constraint Knapsack Problem, denoted KP, we are given a knapsack of fixed capacity c and a set of n items. Each item j, j = 1,...,n, has an associated size or weight w_j and a profit p_j. The goal is to determine whether or not item j, j = 1,...,n, should be included in the knapsack. The objective is to maximize the total profit without exceeding the capacity c of the knapsack. In this paper, we study the sensitivity of the optimum of the KP to perturbations of either the profit or the weight of an item. We give approximate and exact interval limits for both cases (profit and weight) and propose several polynomial time algorithms able to reach these interval limits. The performance of the proposed algorithms are evaluated on a large number of problem instances.     

Approximation of knapsack problems with conflict and forcing graphs

We study the classical 0–1 knapsack problem with additional restrictions on pairs of items. A conflict constraint states that from a certain pair of items at most one item can be contained in a feasible solution. Reversing this condition, we obtain a forcing constraint stating that at least one of the two items must be included in the knapsack. A natural way for representing these constraints is the use of conflict (resp. forcing) graphs. By modifying a recent result of Lokstanov et al. (Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA, pp 570–581, 2014) we derive a fairly complicated FPTAS for the knapsack problem on weakly chordal conflict graphs. Next, we show that the techniques of modular decompositions and clique separators, widely used in the literature for solving the independent set problem on special graph classes, can be applied to the knapsack problem with conflict graphs. In particular, we can show that every positive approximation result for the atoms of prime graphs arising from such a decomposition carries over to the original graph. We point out a number of structural results from the literature which can be used to show the existence of an FPTAS for several graph classes characterized by the exclusion of certain induced subgraphs. Finally, a PTAS for the knapsack problem with H-minor free conflict graph is derived. This includes planar graphs and, more general, graphs of bounded genus. The PTAS is obtained by expanding a general result of Demaine et al. (Proceedings of 46th annual IEEE symposium on foundations of computer science, FOCS 2005, pp 637–646, 2005). The knapsack problem with forcing graphs can be transformed into a minimization knapsack problem with conflict graphs. It follows immediately that all our FPTAS results of the current and a previous paper carry over from conflict graphs to forcing graphs. In contrast, the forcing graph variant is already inapproximable on planar graphs.     

An inventory control policy for liquefied natural gas as a transportation fuel

In this paper, we study a novel stochastic inventory management problem that arises in storage and refueling facilities for Liquefied Natural Gas (LNG) as a transportation fuel. In this inventory problem, the physio-chemical properties of LNG play a key role in the design of inventory policies. These properties are: (1) LNG suffers from both quantity decay and quality deterioration and (2) the quality of on-hand LNG can be upgraded by mixing it with higher-quality LNG. Given that LNG quality can be upgraded, an inventory control policy for this problem needs to consider the removal of LNG as a decision variable. We model and solve the problem by means of a Markov Decision Process (MDP) and study the structural characteristics of the optimal policy. The insights obtained in the analysis of the optimal policy are translated into a simple, though effective, inventory control policy in which actions (i.e., replenishment and/or removal) are driven by both the quality and the quantity of the inventories. We assess the performance of our policy by means of a numerical study and show that it performs close to optimal in many numerical instances. The main conclusion of our study is that it is important to take quality into consideration when design inventory control policies for LNG, and that the most effective way to cope with quality issues in an LNG inventory system involves both the removal and the replenishment of inventories.     

A reinforcement-learning approach for admission control in distributed network service systems

In the distributed network service systems such as streaming-media systems and resource-sharing systems with multiple service nodes, admission control (AC) technology is an essential way to enhance performance. Model-based optimization approaches are good ways to be applied to analyze and solve the optimal AC policy. However, due to “the curse of dimensionality”, computing such policy for practical systems is a rather difficult task. In this paper, we consider a general model of the distributed network service systems, and address the problem of designing an optimal AC policy. An analytical model is presented for the system with fixed parameters based on semi-Markov decision process (SMDP). We design an event-driven AC policy, and the stationary randomized policy is taken as the policy structure. To solve the SMDP, both the state aggregation approach and the reinforcement-learning (RL) method with online policy optimization algorithm are applied. Then, we extend the problem by considering the system with time-varying parameters, where the arrival rates of requests at each service node may change over time. In view of this situation, an AC policy switching mechanism is presented. This mechanism allows the system to decide whether to adjust its AC policy according to the policy switching rule. And in order to maximize the gain of system, that is, to obtain the optimal AC policy switching rule, another RL-based algorithm is applied. To assess the effectiveness of SMDP-based AC policy and policy switching mechanism for the system, numerical experiments are presented. We compare the performance of optimal policies obtained by the solutions of proposed methods with other classical AC policies. The simulation results illustrate that higher performance and computational efficiency could be achieved by using the SMDP model and RL-based algorithms proposed in this paper.     

A classification approach based on the outranking model for multiple criteria ABC analysis

The multiple criteria ABC analysis is widely used in inventory management, and it can help organizations to assign inventory items into different classes with respect to several evaluation criteria. Many approaches have been proposed in the literature for addressing such a problem. However, most of these approaches are fully compensatory in multiple criteria aggregation. This means that an item scoring badly on one or more key criteria could be placed in good classes because these bad performances could be compensated by other criteria. Thus, it is necessary to consider the non-compensation in the multiple criteria ABC analysis. To the best of our knowledge, the ABC classification problem with non-compensation among criteria has not been studied sufficiently. We thus propose a new classification approach based on the outranking model to cope with such a problem in this paper. However, the relational nature of the outranking model makes the search for the optimal classification solution a complex combinatorial optimization problem. It is very time-consuming to solve such a problem using mathematical programming techniques when the inventory size is large. Therefore, we combine the clustering analysis and the simulated annealing algorithm to search for the optimal classification. The clustering analysis groups similar inventory items together and builds up the hierarchy of clusters of items. The simulated annealing algorithm searches for the optimal classification on different levels of the hierarchy. The proposed approach is illustrated by a practical example from a Chinese manufacturer. Furthermore, we validate the performance of the approach through experimental investigation on a large set of artificially generated data at the end of the paper.     

A nested-compliance table policy for emergency medical service systems under relocation

The goal of Emergency Medical Service (EMS) systems is to provide rapid response to emergency calls in order to save lives. This paper proposes a relocation strategy to improve the performance of EMS systems. In practice, EMS systems often use a compliance table to relocate ambulances. A compliance table specifies ambulance base stations as a function of the state of the system. We consider a nested-compliance table, which restricts the number of relocations that can occur simultaneously. We formulate the nested-compliance table model as an integer programming model in order to maximize expected coverage. We determine an optimal nested-compliance table policy using steady state probabilities of a Markov chain model with relocation as input parameters. These parameter approximations are independent of the exact compliance table used. We assume that there is a single type of medical unit, single call priority, and no patient queue. We validate the model by applying the nested-compliance table policies in a simulated system using real-world data. The numerical results show the benefit of our model over a static policy based on the adjusted maximum expected covering location problem (AMEXCLP).     

Application of the knapsack model for budgeting

The budget problem of selecting projects (or activities) with known values (or payoffs) and associated costs, subject to a prescribed maximum budget, is akin to the knapsack problem, which is well documented in the literature. The optimal solution to maximise the total value of selected projects for a given budget constraint can readily be obtained. In practice, budgets are often somewhat flexible, or subject to possible changes, so that an optimal solution for a given budget value may not remain optimal when the budget is modified. It is, therefore, sensible in many situations to consider a budget range, instead of a single budget value. In addition to their original objective of maximising the total value of selected projects, decision makers are often concerned to get ‘value for money’, indicated by the ratio of payoff to cost. This paper examines how these questions can be tackled through the introduction of a stability index, to guide project selection within a defined budget range, and the use of a portfolio diagram, to help in the ranking of projects with respect to the stated twin objectives.