A hybrid adaptive large neighborhood search heuristic for lot-sizing with setup times

This paper presents a hybrid of a general heuristic framework and a general purpose mixed-integer programming (MIP) solver. The framework is based on local search and an adaptive procedure which chooses between a set of large neighborhoods to be searched. A mixed integer programming solver and its built-in feasibility heuristics is used to search a neighborhood for improving solutions. The general reoptimization approach used for repairing solutions is specifically suited for combinatorial problems where it may be hard to otherwise design suitable repair neighborhoods. The hybrid heuristic framework is applied to the multi-item capacitated lot sizing problem with setup times, where experiments have been conducted on a series of instances from the literature and a newly generated extension of these. On average the presented heuristic outperforms the best heuristics from the literature, and the upper bounds found by the commercial MIP solver ILOG CPLEX using state-of-the-art MIP formulations. Furthermore, we improve the best known solutions on 60 out of 100 and improve the lower bound on all 100 instances from the literature.     

Optimal methods for batch processing problem with makespan and maximum lateness objectives

In this paper we consider the problem of scheduling n jobs on a single batch processing machine in which jobs are ordered by two customers. Jobs belonging to different customers are processed based on their individual criteria. The considered criteria are minimizing makespan and maximum lateness. A batching machine is able to process up to b jobs simultaneously. The processing time of each batch is equal to the longest processing time of jobs in the batch. This kind of batch processing is called parallel batch processing. Optimal methods for three cases are developed: unbounded batch capacity, b > n, with compatible job groups and bounded batch capacity, b  n, with compatible and non compatible job groups. Each job group represents a different class of customers and the concept of being compatible means that jobs which are ordered by different customers are allowed to be processed in a same batch. We propose an optimal method for the problem with incompatible groups and unbounded batches. About the case when groups are incompatible and bounded batches, our proposed method is considered as optimal when the group with maximum lateness objective has identical processing times. We regard this method, however, as a heuristic when these processing times are different. When groups are compatible and batches are bounded we consider another problem by assuming the same processing times for the group which has the maximum lateness objective and propose an optimal method for this problem.     

Planning for demand failure: A dynamic lot size model for clinical trial supply chains

This paper examines the optimal production lot size decisions for clinical trial supply chains. One unique aspect of clinical trial supply chains is the risk of failure, meaning that the investigational drug is proven unsafe or ineffective during human testing and the trial is halted. Upon failure, any unused inventory is essentially wasted and needs to be destroyed. To avoid waste, manufacturers could produce small lot sizes. However, high production setup costs lead manufacturers to opt for large lot sizes and few setups. To optimally balance this tradeoff of waste and destruction versus production inefficiency, this paper generalizes the Wagner-Whitin model (W-W model) to incorporate the risk of failure. We show that this stochastic model, referred to as the failure-risk model, is equivalent to the deterministic W-W model if one adjusts the cost parameters properly to reflect failure and destruction costs. We find that increasing failure rates lead to reduced lot sizes and that properly incorporating the risk of failure into clinical trial drug production can lead to substantial cost savings as compared to the W-W model without the properly adjusted parameters.     

在寿命周期内具有抛物型需求的物品的最优补充模型

本文建立了在寿命周期内具有二次抛物需求的物品的一个确定型最优批量模型,提供了产生最优补充策略的一个简单的动态规划方法,用数字例子说明了该模型的求解过程,并出示了模型参数的灵敏度分析．     

A dynamic programming approach for batch sizing in a multi-stage production process with random yields

This paper proposes a dynamic programming approach to modeling and determining batch sizes in a single period, multi-stage production process with random yields for each stage. To improve the computational performance of the proposed approach, a statistical bound is developed. A key decision incorporated into the model is whether to continue onto the next stage of processing or to scrap the entire current batch of product. This decision is based on the expected total profit from the remaining items for processing following the removal of all defectives. The decisions involving the locations of test stations after stages are also incorporated into the modeling approach.     

Optimal batch sizing in a multi-stage production system with rework consideration

In a production system, rework process plays an important role in eliminating waste and effectively controlling the cost of manufacturing. Determining the optimal batch size in a system that allows for rework is, therefore, a worthwhile objective to minimize the inventory cost of work-in-processes and the finished goods. In this paper, models for the optimum batch quantity in a multi-stage system with rework process have been developed for two different operational policies. Policy 1 deals with the rework within the same cycle with no shortage and policy 2 deals with the rework done after N cycles, incurring shortages in each cycle. The major components that play a role in minimizing this cost of the system are manufacturing setups, work-in-processes, storage of finished goods, rework processing, waiting-time, and penalty costs to discourage the generation of defectives. The mathematical structure of this rework processing model falls under a nonlinear convex programming problems for which a closed-form solution has been proposed and results are demonstrated through numerical examples, followed by sensitivity analyses of different important parameters. It is concluded that the total cost in policy 2 tends to be smaller than that in policy 1 at lower proportion of defectives if the in-process carrying cost is low. Policy 2 may be preferred when the work-in-process carrying cost is low and the penalty cost is negligible.     

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.     

Optimal production and shipment models for a single-vendor–single-buyer integrated system

This paper develops a more general production-inventory model for a single-vendor–single-buyer integrated system. Unlike the hitherto existing production-inventory models for the vendor–buyer system, the present model neither requires the buyer’s unit holding cost greater than the vendor’s nor assumes the structure of shipment policy. Secondly, the model is extended to the situation with shortages permitted, based on shortages being allowed to occur only for the buyer. Thirdly, the paper also presents a corresponding production-inventory model for a deteriorating item for the integrated system. The solution procedures are provided for finding the optimal production and shipment policies and illustrated with numerical examples. Three significant insights are shown: (1) no matter whether the buyer’s unit holding cost is greater than the vendor’s or not, the present model always performs best in reducing the average total cost as compared to the hitherto existing models; (2) if the buyer’s unit holding cost is less than the vendor’s, the optimal shipment policy for the integrated system will only comprise shipments with successive shipment sizes increasing by a fixed factor. It is different from that obtained by Hill [Hill, R.M., 1999. The optimal production and shipment policy for the single-vendor single-buyer integrated production-inventory problem. International Journal of Production Research 37, 2463–2475] for the opposite case; (3) when designing a single-vendor–single-buyer integrated system, making the buyer’s unit holding cost lower than the vendor’s is more beneficial to the system if shortages are not permitted to occur; otherwise it just reverses.     

Structural results on a batch acceptance problem for capacitated queues

The purpose of this paper is to investigate the structural properties of the optimal batch acceptance policy in a Markovian queueing system where different classes of customers arrive in batches and the buffer capacity is finite. We prove that the optimal policy can possess certain monotonicity properties under the assumptions of a single-server and constant batch sizes. Even though our proof cannot be extended to cases where either one of the assumptions is relaxed, we numerically observe that the optimal policy can still possess the same properties when only the single-server assumption is relaxed. Finally, we present counterexamples that show the non-monotone structure of the optimal policy when the batch sizes are not constant.     

Optimal production and rationing policies of a make-to-stock production system with batch demand and backordering

In this paper, we consider the stock rationing problem of a single-item make-to-stock production/inventory system with multiple demand classes. Demand arrives as a Poisson process with a randomly distributed batch size. It is assumed that the batch demand can be partially satisfied. The facility can produce a batch up to a certain capacity at the same time. Production time follows an exponential distribution. We show that the optimal policy is characterized by multiple rationing levels.     

Optimal dynamic pricing and inventory control with stock deterioration and partial backordering

This paper studies the optimal dynamic pricing and inventory control policies in a periodic-review inventory system with fixed ordering cost and additive demand. The inventory may deteriorate over time and the unmet demand may be partially backlogged. We identify two sufficient conditions under which (s,S,p) policies are optimal.     

Optimal ordering policies for periodic-review systems with a refined intra-cycle time scale

Chiang [C. Chiang, Optimal ordering policies for periodic-review systems with replenishment cycles, European Journal of Operational Research 170 (2006) 44–56] recently proposed a dynamic programming model for periodic-review systems in which a replenishment cycle consists of a number of small periods (each of identical but arbitrary length) and holding and shortage costs are charged based on the ending inventory of small periods. The current paper presents an alternative (and concise) dynamic programming model. Moreover, we allow the possibility of a positive fixed cost of ordering. The optimal policy is of the familiar (s, S) type because of the convexity of the one-cycle cost function. As in the periodic-review inventory literature, we extend this result to the lost-sales periodic problem with zero lead-time. Computation shows that the long-run average cost is rather insensitive to the choice of the period length. In addition, we show how the proposed model is modified to handle the backorder problem where shortage is charged on a per-unit basis irrespective of its duration. Finally, we also investigate the lost-sales problem with positive lead-time, and provide some computational results.     

A worst case analysis of a dynamic programming-based heuristic algorithm for 2D unconstrained guillotine cutting

In this paper, a dynamic programming-based recursive method is proposed for solving an unconstrained 2D rectangular cutting problem. The algorithm is an incomplete method, in which some intricate cutting patterns may not be obtained. The worst case performance of the algorithm is evaluated and some theoretical analyses for the algorithm are performed. Compared to traditional dynamic programming, this algorithm gives a high percentage of optimal solutions (94.84%, 86.67% and 77.83% for small, medium and large sized unweighted instances, 99.67%, 99.50% and 97.00% for small, medium and large sized weighted instances) but features a far lower computational complexity. Computational results are also presented for some known benchmarks.     

Production planning with load dependent lead times: an update of research

Lead times impact the performance of the supply chain significantly. Although there is a large body of literature concerning queuing models for the analysis of the relationship between capacity utilization and lead times, and another body of work on control and order release policies that take lead times into consideration, there have been relatively few aggregate planning models that recognize the (nonlinear) relationship between the planned utilization of capacity and lead times. In this paper we provide an in-depth discussion of the state-of-the art in this area, with particular attention to those models that are appropriate at the aggregate planning level. An earlier version of this paper appeared in 4OR 3, 257–302, 2005.     

An O(T) algorithm for the capacitated lot sizing problem with minimum order quantities

This paper explores a single-item capacitated lot sizing problem with minimum order quantity, which plays the role of minor set-up cost. We work out the necessary and sufficient solvability conditions and apply the general dynamic programming technique to develop an O(T³) exact algorithm that is based on the concept of minimal sub-problems. An investigation of the properties of the optimal solution structure allows us to construct explicit solutions to the obtained sub-problems and prove their optimality. In this way, we reduce the complexity of the algorithm considerably and confirm its efficiency in an extensive computational study.     

The secretary problem with multiple job vacancies and batch candidate arrivals

We extend the secretary problem with multiple vacancies to allow batch arrival of candidates. We establish structural properties of the optimal policies. We show that the optimal reward is convex and submodular in the values of candidates, which means that there is benefit for having a candidate pool with more variable or less interdependent values. Similar properties continue to hold when there are multiple classes of vacancies. Our model is applicable to recruitment, dynamic auctions and sequential investment.     

Outbound shipment mode considerations for integrated inventory and delivery lot-sizing decisions

We present a two-echelon dynamic lot-sizing model with two outbound delivery modes where one mode has a fixed set-up cost structure while the other has a container-based cost structure. Studying the optimality properties of the problem, we provide a polynomial solution algorithm based on a dynamic programming approach.     

Optimal maintenance of a production-inventory system with idle periods

In this paper we consider a production-inventory system in which an input generating installation supplies a buffer with a raw material and a production unit pulls the raw material from the buffer with constant rate. The installation deteriorates in time and the problem of its optimal preventive maintenance is considered. It is assumed that the installation after the completion of its maintenance remains idle until the buffer is evacuated. Under a suitable cost structure it is shown that the average-cost optimal policy for fixed buffer content is of control-limit type, i.e. it prescribes a preventive maintenance of the installation if and only if its degree of deterioration is greater than or equal to a critical level. Using the usual regenerative argument, the average cost of a control-limit policy is computed exactly and then, the optimal control-limit policy is determined. Furthermore, the stationary probabilities of the system under the optimal policy are computed.     

An index heuristic for transshipment decisions in multi-location inventory systems based on a pairwise decomposition

In multi-location inventory systems, transshipments are often used to improve customer service and reduce cost. Determining optimal transshipment policies for such systems involves a complex optimisation problem that is only tractable for systems with few locations. Consequently simple heuristic transshipment policies are often applied in practice. This paper develops an approximate solution method which applies decomposition to reduce a Markov decision process model of a multi-location inventory system into a number of models involving only two locations. The value functions from the subproblems are used to estimate the fair charge for the inventory provided in a transshipment. This estimate of the fair charge is used as the decision criterion in a heuristic transshipment policy for the multi-location system. A numerical study shows that the proposed heuristic can deliver considerable cost savings compared to the simple heuristics often used in practice.     

Optimal seat allocation for two-flight problems with a flexible demand segment

In this paper, we study a two-flight model where there are two flights between two cities in a day (e.g., one departs at 9:00 am and another at 11:00 am) and booking requests in each fare class arrive according to a random process. There are three types of booking requests: the first and second types are respectively for the first and the second flight only; whereas the third type is flexible and willing to take either flight. Upon receiving a booking request, the airline has to decide whether to accept it, and in case a third type is accepted, which flight to accommodate it. This paper uncovers the structure of optimal booking policies through four monotone switching curves. We also present an extension of the basic model to multiple-flight case. Finally, a numerical example is used to illustrate the derivation and the dynamics of the optimal booking policies.