Dynamic setup reduction in production lot sizing with nonconstant deterministic demand

We examine three production policies under nonconstant, deterministic demand and dynamic setup cost reduction, where a decision to invest in setup reduction is made at the beginning of each period of a planning horizon. The three production policies are the reorder point, order quantity (s, Q) policy; the fixed production cycle, variable order quantity (t, Q_i) policy; and the variable production cycle, variable order quantity (t_i, Q_i). We study the behavior of the total relevant cost and develop a lot sizing and an investment solution procedure. Numerical examples are provided and dynamic setup cost reduction is compared with static setup cost reduction, where the decision to invest in setup reduction is made only at the initial setup.     

On alternative mixed integer programming formulations and LP-based heuristics for lot-sizing with setup times

We address the multi-item, capacitated lot-sizing problem (CLSP) encountered in environments where demand is dynamic and to be met on time. Items compete for a limited capacity resource, which requires a setup for each lot of items to be produced causing unproductive time but no direct costs. The problem belongs to a class of problems that are difficult to solve. Even the feasibility problem becomes combinatorial when setup times are considered. This difficulty in reaching optimality and the practical relevance of CLSP make it important to design and analyse heuristics to find good solutions that can be implemented in practice. We consider certain mixed integer programming formulations of the problem and develop heuristics including a curtailed branch and bound, for rounding the setup variables in the LP solution of the tighter formulations. We report our computational results for a class of instances taken from literature.     

Scale-integration and scale-disintegration in nonlinear homogenization

This work is devoted to scale transformations of stationary nonlinear problems. A class of coarse-scale problems is first derived by integrating a family of two-scale minimization problems (scale-integration), in presence of appropriate orthogonality conditions. The equivalence between the two formulations is established by showing that conversely any solution of the coarse-scale problem can be represented as the fine-scale average of a solution of the two-scale problem (scale-disintegration). This procedure may be applied to the homogenization of several quasilinear problems, and is related to De Giorgi’s notion of Γ-convergence. As an example the homogenization of a simple nonlinear model of magnetostatics is illustrated: a two-scale minimization problem is first derived via Nguetseng’s notion of two-scale convergence, and afterwards the equivalence with a coarse-scale problem is proved.     

Capacitated lot-sizing with extensions: a review

The capacitated lot-sizing problem (CLSP) is a standard formulation for big bucket lot-sizing problems with a discrete period segmentation and deterministic demands. We present a literature review on problems that incorporate one of the following extensions in the CLSP: back-orders, setup carry-over, sequencing, and parallel machines. We illustrate model formulations for each of the extensions and also mention the inclusion of setup times, multi-level product structures and overtime in a study. For practitioners, this overview allows to check the availability of successful solution procedures for a specific problem. For scientists, it identifies areas that are open for future research.      

Integer Programming Formulations for the k-Cardinality Tree Problem

In this paper, we present two Integer Programming formulations for the k-Cardinality Tree Problem. The first is a multiflow formulation while the second uses a lifting of the Miller-Tucker-Zemlin constraints. Based on our computational experience, we suggest a two-phase exact solution approach that combines two different solution techniques, each one exploring one of the proposed formulations.     

On the stochastic uncapacitated dynamic single-item lotsizing problem with service level constraints

In this paper, we consider the uncapacitated single-item dynamic lotsizing problem with stochastic period demands and backordering. We present a model formulation that minimizes the setup and holding costs with respect to a constraint on the probability that the inventory at the end of any period does not become negative (α service level) and, alternatively, to a fill rate constraint (β service level). In contrast to earlier model formulations which consider the cycle α service level (α_c) and which approximate the on hand inventory by the net inventory, we include the exact on hand inventory into the model formulation. Therefore, the models are also applicable in situations with very low service levels.     

Optimal sequencing in the presence of setup times for tow/barge traffic through a river lock

Queues of tow/barges form when a river lock is rendered inoperable due to lock malfunction, a tow/barge accident or adverse lock operating conditions. In this paper, we develop model formulations that allow the queue to be cleared using a number of differing objectives. Of particular interest is the presence of different setup times between successive passages of tow/barges through the lock. Dependent on the objective chosen, we are able to show that certain ordering protocols may be used to markedly reduce the sequencing search space for N tow/barges from the order of N! to 2^N. We present accompanying linear and nonlinear integer programming formulations and carry out computational experiments on a representative set of problems.     

Integer-friendly formulations for the r-separation problem

In this paper, we consider different formulations for the r-separation problem, where the objective is to choose as as many points as possible from a given set of points subject to the constraint that no two selected points can be closer than r units to one another. Our goal is to devise a mathematical programming formulation with an LP-relaxation which yields integer solutions with great frequency. We consider six different formulations of the r-separation problem. We show that the LP-relaxations of the most obvious formulations will yield fractional results in all instances of the problem if an optimal solution contains fewer than half of the given points. To build computationally effective formulations for the r-separation problem, we write dense constraints with unit right-hand-sides. The LP formulation that performs the best in our computational tests almost always finds 0–1 solutions to the problem.     

An Evolutionary Boundary Value Problem

We consider a nonlinear initial boundary value problem in a two-dimensional rectangle. We derive variational formulation of the problem which is in the form of an evolutionary variational inequality in a product Hilbert space. Then, we establish the existence of a unique weak solution to the problem and prove the continuous dependence of the solution with respect to some parameters. Finally, we consider a second variational formulation of the problem, the so-called dual variational formulation, which is in a form of a history-dependent inequality associated with a time-dependent convex set. We study the link between the two variational formulations and establish existence, uniqueness, and equivalence results.

     

Lower bounds for nonlinear assignment problems using many body interactions

This paper concerns lower bounding techniques for the general α-adic assignment problem. The nonlinear objective function is linearized by the introduction of additional variables and constraints, thus yielding a mixed integer linear programming formulation of the problem. The concept of many body interactions is introduced to strengthen this formulation and incorporated in a modified formulation obtained by lifting the original representation to a higher dimensional space. This process involves two steps — (i) addition of new variables and constraints and (ii) incorporation of the new variables in the objective function. If this lifting process is repeated β times on an α-adic assignment problem along with the incorporation of higher order interactions, it results in the mixed-integer formulation of an equivalent (α + β)-adic assignment problem. The incorporation of many body interactions in the higher dimensional formulation improves its degeneracy properties and is also critical to the derivation of decomposition methods for the solution of these large scale mathematical programs in the higher dimensional space. It is shown that a lower bound to the optimal solution of the corresponding linear programming relaxation can be obtained by dualizing a subset of constraints in this formulation and solving O(N^2(α+β−1)) linear assignment problems, whose coefficients depend on the dual values. Moreover, it is proved that the optimal solution to the LP relaxation is obtained if we use the optimal duals for the solution of the linear assignment problems. This concept of many body interactions could be applied in designing algorithms for the solution of formulations obtained by lifting general MILP's. We illustrate all these concepts on the quadratic assignment problems With these decomposition bounds, we have found the provably optimal solutions of two unsolved QAP's of size 32 and have also improved upon existing lower bounds for other QAP's.     

A linear programming embedded genetic algorithm for an integrated cell formation and lot sizing considering product quality

Production lot sizing models are often used to decide the best lot size to minimize operation cost, inventory cost, and setup cost. Cellular manufacturing analyses mainly address how machines should be grouped and parts be produced. In this paper, a mathematical programming model is developed following an integrated approach for cell configuration and lot sizing in a dynamic manufacturing environment. The model development also considers the impact of lot sizes on product quality. Solution of the mathematical model is to minimize both production and quality related costs. The proposed model, with nonlinear terms and integer variables, cannot be solved for real size problems efficiently due to its NP-complexity. To solve the model for practical purposes, a linear programming embedded genetic algorithm was developed. The algorithm searches over the integer variables and for each integer solution visited the corresponding values of the continuous variables are determined by solving a linear programming subproblem using the simplex algorithm. Numerical examples showed that the proposed method is efficient and effective in searching for near optimal solutions.     

A dynamic lot sizing model with exponential machine breakdowns

This paper addresses the dynamic lot sizing model with the assumption that the equipment is subject to stochastic breakdowns. We consider two different situations. First we assume that after a machine breakdown the setup is totally lost and new setup cost is incurred. Second we consider the situation in which the cost of resuming the production run after a failure might be substantially lower than the production setup cost. We show that under the first assumption the cost penalty for ignoring machine failures will be noticeably higher than in the classical lot sizing case with static demand. For the second case, two lot sizes per period are required, an ordinary lot size and a specific second (or resumption) lot size. If during the production of a future period demand the production quantity exceeds the second lot size, the production run will be resumed after a breakdown and terminated if the amount produced is less than this lot size. Considering the results of the static lot sizing case, one would expect a different policy. To find an optimum lot sizing decision for both cases a stochastic dynamic programming model is suggested.     

Simultaneous column-and-row generation for large-scale linear programs with column-dependent-rows

In this paper, we develop a simultaneous column-and-row generation algorithm that could be applied to a general class of large-scale linear programming problems. These problems typically arise in the context of linear programming formulations with exponentially many variables. The defining property for these formulations is a set of linking constraints, which are either too many to be included in the formulation directly, or the full set of linking constraints can only be identified, if all variables are generated explicitly. Due to this dependence between columns and rows, we refer to this class of linear programs as problems with column-dependent-rows. To solve these problems, we need to be able to generate both columns and rows on-the-fly within an efficient solution approach. We emphasize that the generated rows are structural constraints and distinguish our work from the branch-and-cut-and-price framework. We first characterize the underlying assumptions for the proposed column-and-row generation algorithm. These assumptions are general enough and cover all problems with column-dependent-rows studied in the literature up until now to the best of our knowledge. We then introduce in detail a set of pricing subproblems, which are used within the proposed column-and-row generation algorithm. This is followed by a formal discussion on the optimality of the algorithm. To illustrate our approach, the paper is concluded by applying the proposed framework to the multi-stage cutting stock and the quadratic set covering problems.     

Pricing,relaxing and fixing under lot sizing and scheduling

We present a novel mathematical model and a mathematical programming based approach to deliver superior quality solutions for the single machine capacitated lot sizing and scheduling problem with sequence-dependent setup times and costs. The formulation explores the idea of scheduling products based on the selection of known production sequences. The model is the basis of a matheuristic, which embeds pricing principles within construction and improvement MIP-based heuristics. A partial exploration of distinct neighborhood structures avoids local entrapment and is conducted on a rule-based neighbor selection principle. We compare the performance of this approach to other heuristics proposed in the literature. The computational study carried out on different sets of benchmark instances shows the ability of the matheuristic to cope with several model extensions while maintaining a very effective search. Although the techniques described were developed in the context of the problem studied, the method is applicable to other lot sizing problems or even to problems outside this domain.     

The single item uncapacitated lot-sizing problem with time-dependent batch sizes: NP-hard and polynomial cases

This paper considers the uncapacitated lot sizing problem with batch delivery, focusing on the general case of time-dependent batch sizes. We study the complexity of the problem, depending on the other cost parameters, namely the setup cost, the fixed cost per batch, the unit procurement cost and the unit holding cost. We establish that if any one of the cost parameters is allowed to be time-dependent, the problem is NP-hard. On the contrary, if all the cost parameters are stationary, and assuming no unit holding cost, we show that the problem is polynomially solvable in time O(T³), where T denotes the number of periods of the horizon. We also show that, in the case of divisible batch sizes, the problem with time varying setup costs, a stationary fixed cost per batch and no unit procurement nor holding cost can be solved in time O(T³ logT).     

The finite multiple lot sizing problem with interrupted geometric yield and holding costs

We consider the multiple lot sizing problem in production systems with random process yield losses governed by the interrupted geometric (IG) distribution. Our model differs from those of previous researchers which focused on the IG yield in that we consider a finite number of setups and inventory holding costs. This model particularly arises in systems with large demand sizes. The resulting dynamic programming model contains a stage variable (remaining time till due) and a state variable (remaining demand to be filled) and therefore gives considerable difficulty in the derivation of the optimal policy structure and in numerical computation to solve real application problems. We shall investigate the properties of the optimal lot sizes. In particular, we shall show that the optimal lot size is bounded. Furthermore, a dynamic upper bound on the optimal lot size is derived. An O(nD) algorithm for solving the proposed model is provided, where n and D are the two-state variables. Numerical results show that the optimal lot size, as a function of the demand, is not necessarily monotone.     

A MIP-based framework and its application on a lot sizing problem with setup carryover

In this paper we present a framework to tackle mixed integer programming problems based upon a “constrained” black box approach. Given a MIP formulation, a black-box solver, and a set of incumbent solutions, we iteratively build corridors around such solutions by adding exogenous constraints to the original MIP formulation. Such corridors, or neighborhoods, are then explored, possibly to optimality, with a standard MIP solver. An iterative approach in the spirit of a hill climbing scheme is thus used to explore subportions of the solution space. While the exploration of the corridor relies on a standard MIP solver, the way in which such corridors are built around the incumbent solutions is influenced by a set of factors, such as the distance metric adopted, or the type of method used to explore the neighborhood. The proposed framework has been tested on a challenging variation of the lot sizing problem, the multi-level lot sizing problem with setups and carryovers. When tested on 1920 benchmark instances of such problem, the algorithm was able to solve to near optimality every instance of the benchmark library and, on the most challenging instances, was able to find high quality solutions very early in the search process. The algorithm was effective, in terms of solution quality as well as computational time, when compared with a commercial MIP solver and the best algorithm from the literature.     

The two-group heuristic to solve the multi-product,economic lot sizing and scheduling problem in flow shops

This paper presents a new and efficient heuristic to solve the multi-product, economic lot sizing and scheduling problem in flow shops. The problem addressed is that of making sequencing, lot sizing and scheduling decisions for a number of products so as to minimize the sum of setup costs, work-in-process inventory holding costs and final-products inventory holding costs while a given demand is fulfilled without backlogging. The proposed heuristic, called the two-group method (TG), assumes that the cycle time of each product is an integer multiple of a basic period and restricts these multiples to take either the value 1 or K where K is a positive integer. The products to be produced once each K basic period are then partitioned into K sub-groups and each sub-group is assigned to one and only one of the K basic periods of the global cycle. This method first determines a value for K and a feasible partition. Then, a production sequence is determined for each sub-group of products and a non-linear program is solved to determine lot sizes and a feasible schedule. We also show how to adapt our method to the case of batch streaming (transportation of sub-batches from one machine to the next). To evaluate its performance, the TG method was compared to both the common cycle method and a reinforced version of El-Najdawi’s job-splitting heuristic. Numerical results show that the TG method outperforms both of these methods.     

On relaxations of the max k-cut problem formulations

A tight continuous relaxation is a crucial factor in solving mixed integer formulations of many NP-hard combinatorial optimization problems. The (weighted) max k-cut problem is a fundamental combinatorial optimization problem with multiple notorious mixed integer optimization formulations. In this paper, we explore four existing mixed integer optimization formulations of the max k-cut problem. Specifically, we show that the continuous relaxation of a binary quadratic optimization formulation of the problem is: (i) stronger than the continuous relaxation of two mixed integer linear optimization formulations and (ii) at least as strong as the continuous relaxation of a mixed integer semidefinite optimization formulation. We also conduct a set of experiments on multiple sets of instances of the max k-cut problem using state-of-the-art solvers that empirically confirm the theoretical results in item (i). Furthermore, these numerical results illustrate the advances in the efficiency of global non-convex quadratic optimization solvers and more general mixed integer nonlinear optimization solvers. As a result, these solvers provide a promising option to solve combinatorial optimization problems. Our codes and data are available on GitHub.