Capacitated dynamic lot-sizing problem with delivery/production time windows

In this paper we generalize the classical dynamic lot-sizing problem by considering production capacity constraints as well as delivery and/or production time windows. Utilizing an untraditional decomposition principle, we develop a polynomial-time algorithm for computing an optimal solution for the problem under the assumption of non-speculative costs. The proposed solution methodology is based on a dynamic programming algorithm that runs in O(nT⁴) time, where n is the number of demands and T is the length of the planning horizon.     

An Efficient Procedure for Dynamic Lot-sizing Model with Demand Time Windows

We consider a dynamic lot-sizing model with demand time windows where n demands need to be scheduled in T production periods. For the case of backlogging allowed, an O(T ³) algorithm exists under the non-speculative cost structure. For the same model with somewhat general cost structure, we propose an efficient algorithm with O(max {T ², nT}) time complexity.     

An FPTAS for a single-item capacitated economic lot-sizing problem with monotone cost structure

We present a fully polynomial time approximation scheme (FPTAS) for a capacitated economic lot-sizing problem with a monotone cost structure. An FPTAS delivers a solution with a given relative error ɛ in time polynomial in the problem size and in 1/ɛ. Such a scheme was developed by van Hoesel and Wagelmans [8] for a capacitated economic lot-sizing problem with monotone concave (convex) production and backlogging cost functions. We omit concavity and convexity restrictions. Furthermore, we take advantage of a straightforward dynamic programming algorithm applied to a rounded problem.     

Dynamic lot-sizing problem with demand time windows and container-based transportation cost

In this paper, we study the dynamic lot-sizing problem with demand time windows and container-based transportation cost. For each particular demand, there are corresponding earliest and latest times, and the duration between such earliest and latest times is the demand time window. If a demand is satisfied by a delivery within demand time window, then there is no holding or backlogging cost incurred. Our purpose is to satisfy demand at a minimum total cost, including setup cost, procurement cost, container cost, and inventory holding cost. This research is supported in part by Hong Kong RGC grant HKUST 6010/02E and NUS ARF grant R-266-000-019-112.     

Dynamic lot-sizing model for major and minor demands

This paper deals with a lot-sizing model for major and minor demands in which major demands are specified by time windows while minor demands are given by periods. For major demands, the agreeable time window structure is assumed where each time window is not strictly nested in any other time windows. To incorporate the economy of scale of large production quantity, especially from major demands, concave cost structure in production must be considered. Investigating the optimality properties, we propose optimal solution procedures based on dynamic program. For a simple case when only major demands exist, we propose an optimal procedure with running time of O(n²T)$\mathrm{O}(n^{2}T)$ where n is the number of demands and T   is the length of the planning horizon. Extending the algorithm to the model with major and minor demands, we propose an algorithm with complexity O(n²T²)$\mathrm{O}(n^2{T}^2)$.     

The single-item lot-sizing problem with two production modes,inventory bounds,and periodic carbon emissions capacity

We consider the single-item lot-sizing problem with inventory bounds under a carbon emissions constraint with two options for producing items: regular or green. We wish to find the optimal production plan so that the total carbon emissions from production cannot exceed the carbon emissions capacity in each period. Extending a problem without fixed carbon emissions and inventory bounds, we show that the extended problem is polynomially solvable by a dynamic programming algorithm.     

The vehicle routing problem with flexible time windows and traveling times

We generalize the standard vehicle routing problem by allowing soft time window and soft traveling time constraints, where both constraints are treated as cost functions. With the proposed generalization, the problem becomes very general. In our algorithm, we use local search to determine the routes of vehicles. After fixing the route of each vehicle, we must determine the optimal start times of services at visited customers. We show that this subproblem is NP-hard when cost functions are general, but can be efficiently solved with dynamic programming when traveling time cost functions are convex even if time window cost functions are non-convex. We deal with the latter situation in the developed iterated local search algorithm. Finally we report computational results on benchmark instances, and confirm the benefits of the proposed generalization.     

Lot-sizing with production and delivery time windows

We study two different lot-sizing problems with time windows that have been proposed recently. For the case of production time windows, in which each client specific order must be produced within a given time interval, we derive tight extended formulations for both the constant capacity and uncapacitated problems with Wagner-Whitin (non-speculative) costs. For the variant with nonspecific orders, known to be equivalent to the problem in which the time windows can be ordered by time, we also show equivalence to the basic lot-sizing problem with upper bounds on the stocks. Here we derive polynomial time dynamic programming algorithms and tight extended formulations for the uncapacitated and constant capacity problems with general costs. For the problem with delivery time windows, we use a similar approach to derive tight extended formulations for both the constant capacity and uncapacitated problems with Wagner-Whitin (non-speculative) costs. We are most grateful for the hospitality of IASI, Rome, where part of this work was carried out. The collaboration with IASI takes place in the framework of ADONET, a European network in Algorithmic Discrete Optimization, contract n MRTN-CT-2003-504438. This text presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister's Office, Science Policy Programming. The scientific responsibility is assumed by the authors.     

A single-item economic lot-sizing problem with a non-uniform resource: Approximation

We study a generalization of the classical single-item capacitated economic lot-sizing problem to the case of a non-uniform resource usage for production. The general problem and several special cases are shown to be non-approximable with any polynomially computable relative error in polynomial time. An optimal dynamic programming algorithm and its approximate modification are presented for the general problem. Fully polynomial time approximation schemes are developed for two NP-hard special cases: (1) cost functions of total production are separable and holding and backlogging cost functions are linear with polynomially related slopes, and (2) all holding costs are equal to zero.     

An algorithm for single-item economic lot-sizing problem with general inventory cost, non-decreasing capacity, and non-increasing setup and production cost

This paper considers an economic lot-sizing model with non-decreasing capacity constraint, non-increasing setup cost and production cost, and a general inventory cost. We prove that when periodic starting inventory is not less than a certain critical value, it is optimal to produce nothing; this critical value can be computed easily which results in a new effective algorithm.     

Optimal inventory policy with supply uncertainty and demand cancellation

We consider a periodic review model where the firm manages its inventory under supply uncertainty and demand cancellation. We show that because of supply uncertainty, the optimal inventory policy has the structure of re-order point type. That is, we order if the initial inventory falls below this re-order point, otherwise we do not order. This is in contrast to the work of Yuan and Cheung (2003) who prove the optimality of an order up to policy in the absence of supply uncertainty. We also investigate the impact of supply uncertainty and demand cancellation on the performance of the supply chain. Using our model, we are able to quantify the importance of reducing the variance of either the distribution of yield or the distribution of demand cancellation. The single, multiple periods and the infinite horizon models are studied.     

Fix-and-optimize heuristics for capacitated lot-sizing with sequence-dependent setups and substitutions

In this paper, we consider a capacitated single-level dynamic lot-sizing problem with sequence-dependent setup costs and times that includes product substitution options. The model is motivated from a real-world production planning problem of a manufacturer of plastic sheets used as an interlayer in car windshields. We develop a mixed-integer programming (MIP) formulation of the problem and devise MIP-based Relax&Fix and Fix&Optimize heuristics. Unlike existing literature, we combine Fix&Optimize with a time decomposition. Also, we develop a specialized substitute decomposition and devise a computation budget allocation scheme for ensuring a uniform, efficient usage of computation time by decompositions and their subproblems. Computational experiments were performed on generated instances whose structure follows that of the considered practical application and which have rather tight production capacities. We found that a Fix&Optimize algorithm with an overlapping time decomposition yielded the best solutions. It outperformed the state-of-the-art approach Relax&Fix and all other tested algorithm variants on the considered class of instances, and returned feasible solutions with neither overtime nor backlogging for all instances. It returned solutions that were on average only 5% worse than those returned by a standard MIP solver after 4 hours and 19% better than those of Relax&Fix.     

An iterated local search algorithm for the time-dependent vehicle routing problem with time windows

We generalize the standard vehicle routing problem with time windows by allowing both traveling times and traveling costs to be time-dependent functions. In our algorithm, we use a local search to determine routes of the vehicles. When we evaluate a neighborhood solution, we must compute an optimal time schedule for each route. We show that this subproblem can be efficiently solved by dynamic programming, which is incorporated in the local search algorithm. The neighborhood of our local search consists of slight modifications of the standard neighborhoods called 2- opt^*, cross exchange and Or-opt. We propose an algorithm that evaluates solutions in these neighborhoods more efficiently than the ones computing the dynamic programming from scratch by utilizing the information from the past dynamic programming recursion used to evaluate the current solution. We further propose a filtering method that restricts the search space in the neighborhoods to avoid many solutions having no prospect of improvement. We then develop an iterated local search algorithm that incorporates all the above ingredients. Finally we report computational results of our iterated local search algorithm compared against existing methods, and confirm the effectiveness of the restriction of the neighborhoods and the benefits of the proposed generalization.     

Solving the discrete lotsizing and scheduling problem with sequence dependent set-up costs and set-up times using the Travelling Salesman Problem with time windows

In this paper we consider the Discrete Lotsizing and Scheduling Problem with sequence dependent set-up costs and set-up times (DLSPSD). DLSPSD contains elements from lotsizing and from job scheduling, and is known to be NP-Hard. An exact solution procedure for DLSPSD is developed, based on a transformation of DLSPSD into a Travelling Salesman Problem with Time Windows (TSPTW). TSPTW is solved by a novel dynamic programming approach due to Dumas et al. (1993). The results of a computational study show that the algorithm is the first one capable of solving DLSPSD problems of moderate size to optimality with a reasonable computational effort.     

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.     

The multi-item capacitated lot-sizing problem with setup times and shortage costs

We address a multi-item capacitated lot-sizing problem with setup times and shortage costs that arises in real-world production planning problems. Demand cannot be backlogged, but can be totally or partially lost. The problem is NP-hard. A mixed integer mathematical formulation is presented. Our approach in this paper is to propose some classes of valid inequalities based on a generalization of Miller et al. [A.J. Miller, G.L. Nemhauser, M.W.P. Savelsbergh, On the polyhedral structure of a multi-item production planning model with setup times, Mathematical Programming 94 (2003) 375–405] and Marchand and Wolsey [H. Marchand, L.A. Wolsey, The 0–1 knapsack problem with a single continuous variable, Mathematical Programming 85 (1999) 15–33] results. We also describe fast combinatorial separation algorithms for these new inequalities. We use them in a branch-and-cut framework to solve the problem. Some experimental results showing the effectiveness of the approach are reported.     

Minimizing total earliness and tardiness on re-entrant batch processing machine with time windows

The time window (TW) generalizes the concept of due date. The semiconductor wafer fabrication system is currently one of the most complex production processes, which has typical re-entrant batch processing machine (RBPM). RBPM is a bottleneck. This paper addresses a scheduling of RBPM with job-dependent TWs. According to a general modelling, an improved and new job-family-oriented modelling of the decomposition method that is based on the slack mixed integer linear programming is proposed. First, the complicated scheduling problem of RBPM is divided into sub-problems, which are executed circularly. Then, each one consists of updating, sequencing and dispatching. The objective is to minimize the total earliness and tardiness for job-dependent TWs. In order to evaluate the proposed modelling, the experiments are implemented on the real-time scheduling simulation platform and optimization toolkit ILOG CPLEX. The results show that the improved modelling obtains better solutions in less computation time.