Lower bound on size of branch-and-bound trees for solving lot-sizing problem

We show that there exists a family of instances of the lot-sizing problem, such that any branch-and-bound tree that solves them requires an exponential number of nodes, even in the case when the branchings are performed on general split disjunctions. This result is of interest since there exists dynamic programming algorithm that solves lot-sizing in polynomial-time. To the best of our knowledge, this is the first study that shows that dynamic programming can be exponentially faster than branch-and-bound.     

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.     

The combined cutting stock and lot-sizing problem in industrial processes

Despite its great applicability in several industries, the combined cutting stock and lot-sizing problem has not been sufficiently studied because of its great complexity. This paper analyses the trade-off that arises when we solve the cutting stock problem by taking into account the production planning for various periods. An optimal solution for the combined problem probably contains non-optimal solutions for the cutting stock and lot-sizing problems considered separately. The goal here is to minimize the trim loss, the storage and setup costs. With a view to this, we formulate a mathematical model of the combined cutting stock and lot-sizing problem and propose a solution method based on an analogy with the network shortest path problem. Some computational results comparing the combined problem solutions with those obtained by the method generally used in industry—first solve the lot-sizing problem and then solve the cutting stock problem—are presented. These results demonstrate that by combining the problems it is possible to obtain benefits of up to 28% profit. Finally, for small instances we analyze the quality of the solutions obtained by the network shortest path approach compared to the optimal solutions obtained by the commercial package AMPL.     

The value function of an infinite-horizon single-item lot-sizing problem

We characterize the value function of a discounted infinite-horizon version of the single-item lot-sizing problem. As corollaries, we show that this value function inherits several properties of finite, mixed-integer program value functions; namely, it is subadditive, lower semicontinuous, and piecewise linear.     

Profit maximization in simultaneous lot-sizing and scheduling problem

This paper extends the simultaneous lot-sizing and scheduling problem, to include demand choice flexibility. The basic assumption in most research about lot-sizing and scheduling problems is that all the demands should be satisfied. However, in a business with a goal of maximizing profit, meeting all demands may not be an optimum decision. In the profit maximization simultaneous lot-sizing and scheduling problem with demand choice flexibility, the accepted demand in each period, lot-sizing and scheduling are three problems which are considered simultaneously. In other words the decisions pertaining to mid-term planning and short-term planning are considered as one problem and not hierarchically. According to this assumption, the objective function of traditional models changes from minimizing costs to maximizing profits.     

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.     

On formulations of the stochastic uncapacitated lot-sizing problem

We consider two formulations of a stochastic uncapacitated lot-sizing problem. We show that by adding (?,S) inequalities to the one with the smaller number of variables, both formulations give the same LP bound. Then we show that for two-period problems, adding another class of inequalities gives the convex hull of integral solutions.     

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.     

Analysis of relaxations for the multi-item capacitated lot-sizing problem

The multi-item capacitated lot-sizing problem consists of determining the magnitude and the timing of some operations of durable results for several items in a finite number of processing periods so as to satisfy a known demand in each period. We show that the problem is strongly NP-hard. To explain why one of the most popular among exact and approximate solution methods uses a Lagrangian relaxation of the capacity constraints, we compare this approach with every alternate relaxation of the classical formulation of the problem, to show that it is the most precise in a rigorous sense. The linear relaxation of a shortest path formulation of the same problem has the same value, and one of its Lagrangian relaxations is even more accurate. It is comforting to note that well-known relaxation algorithms based on the traditional formulation can be directly used to solve the shortest path formulation efficiently, and can be further enhanced by new algorithms for the uncapacitated lot-sizing problem. An extensive computational comparison between linear programming, column generation and subgradient optimization exhibits this efficiency, with a surprisingly good performance of column generation. We pinpoint the importance of the data characteristics for an empirical classification of problem difficulty and show that most real-world problems are easier to solve than their randomly generated counterparts because of the presence of initial inventories and their large number of items.Supported by NSF Grant ECS-8518970 and NSERC Grant OGP 0042197.     

Solving the capacitated lot-sizing problem with backorder consideration

In this research, we formulate and solve a type of the capacitated lot-sizing problem. We present a general model for the lot-sizing problem with backorder options, that can take into consideration various types of production capacities such as regular time, overtime and subcontracting. The objective is to determine lot sizes that will minimize the sum of setup costs, holding cost, backorder cost, regular time production costs, and overtime production costs, subject to resource constraints. Most existing formulations for the problem consider the special case of the problem where a single source of production capacity is considered. However, allowing for the use of alternate capacities such as overtime is quite common in many manufacturing settings. Hence, we provide a formulation that includes consideration of multiple sources of production capacity. We develop a heuristic based on the special structure of fixed charge transportation problem. The performance of our algorithm is evaluated by comparing the heuristic solution value to lower bound value. Extensive computational results are presented.     

Hybrid simulated annealing and MIP-based heuristics for stochastic lot-sizing and scheduling problem in capacitated multi-stage production system

This paper addresses lot sizing and scheduling problem of a flow shop system with capacity constraints, sequence-dependent setups, uncertain processing times and uncertain multi-product and multi-period demand. The evolution of the uncertain parameters is modeled by means of probability distributions and chance-constrained programming (CCP) theory. A new mixed-integer programming (MIP) model with big bucket time approach is proposed to formulate the problem. Due to the complexity of problem, two MIP-based heuristics with rolling horizon framework named non-permutation heuristic (NPH) and permutation heuristic (PH) have been performed to solve this model. Also, a hybrid meta-heuristic based on a combination of simulated annealing, firefly algorithm and proposed heuristic for scheduling is developed to solve the problem. Additionally, Taguchi method is conducted to calibrate the parameters of the meta-heuristic and select the optimal levels of the algorithm’s performance influential factors. Computational results on a set of randomly generated instances show the efficiency of the hybrid meta-heuristic against exact solution algorithm and heuristics.     

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.     

Learning and forgetting effects on a group scheduling problem

This paper proposes to investigate learning and forgetting effects on the problem of scheduling families of jobs on a single machine to minimize total completion time of jobs. A setup time is incurred whenever the single machine transfers job processing from a family to another family. To analyze the impact of learning and forgetting on this group scheduling problem, we structure three basic models and make some comparisons through computational experiments. The three models, including no forgetting, total forgetting and partial forgetting, assume that the processing time of a job is dependent on its position in a schedule. Some scheduling rules and a lower bound are derived in order to constitute our branch-and-bound algorithm for searching an optimal sequence. In addition, an efficient and simply-structured heuristic is also built to find a near-optimal schedule.     

Stochastic lot-sizing problem with deterministic demands and Wagner-Whitin costs

In this paper, we consider a two-stage stochastic uncapacitated lot-sizing problem with deterministic demands and Wagner-Whitin costs. We develop an extended formulation in the higher dimensional space that provides integral solutions by showing that its constraint matrix is totally unimodular. We also provide the integral polyhedron of the problem in the original space by projecting the extended formulation to the original space.     

Dynamic programming approximation algorithms for the capacitated lot-sizing problem

This paper provides a new idea for approximating the inventory cost function to be used in a truncated dynamic program for solving the capacitated lot-sizing problem. The proposed method combines dynamic programming with regression, data fitting, and approximation techniques to estimate the inventory cost function at each stage of the dynamic program. The effectiveness of the proposed method is analyzed on various types of the capacitated lot-sizing problem instances with different cost and capacity characteristics. Computational results show that approximation approaches could significantly decrease the computational time required by the dynamic program and the integer program for solving different types of the capacitated lot-sizing problem instances. Furthermore, in most cases, the proposed approximate dynamic programming approaches can accurately capture the optimal solution of the problem with consistent computational performance over different instances.     

A branch-and-cut algorithm for the stochastic uncapacitated lot-sizing problem

This paper addresses a multi-stage stochastic integer programming formulation of the uncapacitated lot-sizing problem under uncertainty. We show that the classical (ℓ,S) inequalities for the deterministic lot-sizing polytope are also valid for the stochastic lot-sizing polytope. We then extend the (ℓ,S) inequalities to a general class of valid inequalities, called the inequalities, and we establish necessary and sufficient conditions which guarantee that the inequalities are facet-defining. A separation heuristic for inequalities is developed and incorporated into a branch-and-cut algorithm. A computational study verifies the usefulness of the inequalities as cuts. This research has been supported in part by the National Science Foundation under Award number DMII-0121495.