Reformulation and a Lagrangian heuristic for lot sizing problem on parallel machines

We consider the capacitated lot sizing problem with multiple items, setup time and unrelated parallel machines. The aim of the article is to develop a Lagrangian heuristic to obtain good solutions to this problem and good lower bounds to certify the quality of solutions. Based on a strong reformulation of the problem as a shortest path problem, the Lagrangian relaxation is applied to the demand constraints (flow constraint) and the relaxed problem is decomposed per period and per machine. The subgradient optimization method is used to update the Lagrangian multipliers. A primal heuristic, based on transfers of production, is designed to generate feasible solutions (upper bounds). Computational results using data from the literature are presented and show that our method is efficient, produces lower bounds of good quality and competitive upper bounds, when compared with the bounds produced by another method from the literature and by high-performance MIP software.     

Capacitated Multiple Item Ordering with Incremental Quantity Discounts

This paper presents a heuristic algorithm for determining order quantities for multiple items given incremental quantity discounts and a single resourse constraint. The heuristic is based on Lagrangian relaxation. The performance of the heuristic is compared, for small problems, with a procedure that generates optimal solutions. Results from computational experiments are given that demonstrate the quality and computational efficiency of the heuristic algorithm.     

An alternative framework to Lagrangian relaxation approach for job shop scheduling

A new Lagrangian relaxation (LR) approach is developed for job shop scheduling problems. In the approach, operation precedence constraints rather than machine capacity constraints are relaxed. The relaxed problem is decomposed into single or parallel machine scheduling subproblems. These subproblems, which are NP-complete in general, are approximately solved by using fast heuristic algorithms. The dual problem is solved by using a recently developed “surrogate subgradient method” that allows approximate optimization of the subproblems. Since the algorithms for subproblems do not depend on the time horizon of the scheduling problems and are very fast, our new LR approach is efficient, particularly for large problems with long time horizons. For these problems, the machine decomposition-based LR approach requires much less memory and computation time as compared to a part decomposition-based approach as demonstrated by numerical testing.     

Relaxation heuristics for a generalized assignment problem

We propose relaxation heuristics for the problem of maximum profit assignment of n tasks to m agents (n > m), such that each task is assigned to only one agent subject to capacity constraints on the agents. Using Lagrangian or surrogate relaxation, the heuristics perform a subgradient search obtaining feasible solutions. Relaxation considers a vector of multipliers for the capacity constraints. The resolution of the Lagrangian is then immediate. For the surrogate, the resulting problem is a multiple choice knapsack that is again relaxed for continuous values of the variables, and solved in polynomial time. Relaxation multipliers are used with an improved heuristic of Martello and Toth or a new constructive heuristic to find good feasible solutions. Six heuristics are tested with problems of the literature and random generated problems. Best results are less than 0.5% from the optimal, with reasonable computational times for an AT/386 computer. It seems promising even for problems with correlated coefficients.     

A Lagrangian relaxation approach to large-scale flow interception problems

The paper presents a tight Lagrangian bound and an efficient dual heuristic for the flow interception problem. The proposed Lagrangian relaxation decomposes the problem into two subproblems that are easy to solve. Information from one of the subproblems is used within a dual heuristic to construct feasible solutions and is used to generate valid cuts that strengthen the relaxation. Both the heuristic and the relaxation are integrated into a cutting plane method where the Lagrangian bound is calculated using a subgradient algorithm. In the course of the algorithm, a valid cut is added and integrated efficiently in the second subproblem and is updated whenever the heuristic solution improves. The algorithm is tested on randomly generated test problems with up to 500 vertices, 12,483 paths, and 43 facilities. The algorithm finds a proven optimal solution in more than 75% of the cases, while the feasible solution is on average within 0.06% from the upper bound.     

A Heuristic for a Resource-capacitated Multi-stage Lot-sizing Problem with Lead Times

In this paper we propose a heuristic for the resource-capacitated multi-stage lot-sizing problem with general product structures, set-up costs and resource usage, work-in-process inventory costs and lead times. To facilitate the functioning of the heuristic, we use the formulation of the problem based on Echelon Stock in a rolling horizon scheme. The heuristic first obtains a reasonable solution to the corresponding uncapacitated problem and then tries to attain capacity feasibility by shifting production backwards in time. The concept of echelon stock makes the task of checking the inventory feasibility of proposed shifts easier than would be the case with conventional installation stock. The heuristic is first tested computationally for problems with a five-component product structure over a 12 period planning horizon for which optimal solutions were available and for which optimality precision guarantees were also obtained via Lagrangian Relaxation. The heuristic's performance is also explored with two different 40-component product structures, with high and low set-up costs, and is compared with the Lagrangian precision guarantees.     

The static stochastic knapsack problem with normally distributed item sizes

This paper develops exact and heuristic algorithms for a stochastic knapsack problem where items with random sizes may be assigned to a knapsack. An item’s value is given by the realization of the product of a random unit revenue and the random item size. When the realization of the sum of selected item sizes exceeds the knapsack capacity, a penalty cost is incurred for each unit of overflow, while our model allows for a salvage value for each unit of capacity that remains unused. We seek to maximize the expected net profit resulting from the assignment of items to the knapsack. Although the capacity is fixed in our core model, we show that problems with random capacity, as well as problems in which capacity is a decision variable subject to unit costs, fall within this class of problems as well. We focus on the case where item sizes are independent and normally distributed random variables, and provide an exact solution method for a continuous relaxation of the problem. We show that an optimal solution to this relaxation exists containing no more than two fractionally selected items, and develop a customized branch-and-bound algorithm for obtaining an optimal binary solution. In addition, we present an efficient heuristic solution method based on our algorithm for solving the relaxation and empirically show that it provides high-quality solutions.     

A multi-period order selection problem in flexible manufacturing systems

We consider a multi-period order selection problem in flexible manufacturing systems, which is the problem of selecting orders to be produced in each period during the upcoming planning horizon with the objective of minimising earliness and tardiness costs and subcontracting costs. The earliness and tardiness costs are incurred if an order is not finished on time, while subcontracting cost is incurred if an order is not selected within the planning horizon (and must be subcontracted) due to processing time capacity or tool magazine capacity. This problem is formulated as a 0–1 integer program which can be transformed into a generalised assignment problem. To solve the problem, a heuristic algorithm is developed using a Lagrangian relaxation technique. Effectiveness of the algorithm is tested on randomly generated problems and results are reported.     

A theoretical and empirical investigation on the Lagrangian capacities of the 0-1 multidimensional knapsack problem

We present a novel Lagrangian method to find good feasible solutions in theoretical and empirical aspects. After investigating the concept of Lagrangian capacity, which is the value of the capacity constraint that Lagrangian relaxation can find an optimal solution, we formally reintroduce Lagrangian capacity suitable to the 0-1 multidimensional knapsack problem and present its new geometric equivalent condition including a new associated property. Based on the property, we propose a new Lagrangian heuristic that finds high-quality feasible solutions of the 0-1 multidimensional knapsack problem. We verify the advantage of the proposed heuristic by experiments. We make comparisons with existing Lagrangian approaches on benchmark data and show that the proposed method performs well on large-scale data.     

A Lagrangian Relaxation Heuristic for Capacitated Facility Location with Single-Source Constraints

Facility location models are applicable to problems in many diverse areas, such as distribution systems and communication networks. In capacitated facility location problems, a number of facilities with given capacities must be chosen from among a set of possible facility locations and then customers assigned to them. We describe a Lagrangian relaxation heuristic algorithm for capacitated problems in which each customer is served by a single facility. By relaxing the capacity constraints, the uncapacitated facility location problem is obtained as a subproblem and solved by the well-known dual ascent algorithm. The Lagrangian relaxations are complemented by an add heuristic, which is used to obtain an initial feasible solution. Further, a final adjustment heuristic is used to attempt to improve the best solution generated by the relaxations. Computational results are reported on examples generated from the Kuehn and Hamburger test problems.     

Production planning and warehouse management in supply networks with inter-facility mold transfers

This paper, considers with the problem of production capacity and warehouse management in a supply network in which inter-plant mold transfers are enabled. The supply network has a limited number of very expensive molds which can be transferred from a plant to another making it possible for each plant to produce the entire product gamut. It is assumed that warehouses in this supply network can be activated and deactivated as required, and that material transfers from a warehouse to another are also possible. The objective is to develop a capacity and warehouse management plan that satisfies the expected market demands with the lowest possible cost. A mixed integer programming model for the problem is suggested and its properties are discussed. A linear programming-based heuristic that combines Lagrangian relaxation and linear programming duality to generate lower and upper bounds for the problem is proposed. Finally, based on a designed experiment the performance of the heuristic on a set of generated test problems is reported and discussed.     

工件优先级图为非连接图且含环的单机总加权拖期调度问题

为满足实际生产环境对工件加工顺序和工件到达时间的要求,提出了具有新特征的单机总加权拖期调度问题,其特点体现在:工件有动态到达时间,且由工件优先级关系构成的优先级图为非连接图且存在环的情况,对该问题建立数学规划模型,在扩展Tang和Xuan等的基础上,提出了结合双向动态规划的拉格朗日松弛算法求解该问题。在该算法的设计中,提出双向动态规划算法求解拉格朗日松弛问题,使得它可处理优先级图中一个工件可能有多个紧前或紧后工件的情况,采用次梯度算法更新拉格朗日乘子,基于拉格朗日松弛问题的解设计启发式算法构造可行解。实验测试结果显示,所设计的拉格朗日松弛算法能够在较短的运行时间内得到令人满意的近优解,为更复杂的调度问题的求解提供了思路。     

Dynamic resource allocation in a multi-product make-to-stock production system

We consider optimal policies for a production facility in which several (K) products are made to stock in order to satisfy exogenous demand for each. The single machine version of this problem in which the facility manufactures at most one product at a time to minimise inventory costs has been much studied. We achieve a major generalisation by formulating the production problem as one involving dynamic allocation of a key resource which drives the manufacture of all products under an assumption that each additional unit of resource allocated to a product achieves a diminishing return of increased production rate. A Lagrangian relaxation of the production problem induces a decomposition into K single product problems in which the production rate may be varied but is subject to charge. These reduced problems are of interest in their own right. Under mild conditions of full indexability the Lagrangian relaxation is solved by a production policy with simple index-like structure. This in turn suggests a natural index heuristic for the original production problem which performs strongly in a numerical study. The paper discusses the importance of full indexability and makes proposals for the construction of production policies involving resource idling when it fails.     

Short-Term Capacity Adjustment with Offline Production for a Flexible Manufacturing System under Abnormal Disturbances

Large production variations caused by abnormal disturbances can significantly reduce the production capacity of a flexible manufacturing system (FMS). To prevent production delays, short-term capacity adjustment strategies can be used to augment the capacity of the FMS, such as working overtime, using alternative tools that are suited for faster processing, and producing parts outside of the FMS. We propose a mixed integer programming (MIP) model to obtain an optimal production plan for a multi-machine FMS. Our model evaluates both the FMS loading decision and the effective use of short-term capacity adjustment strategies to minimize the total part production cost. We develop an iterative procedure to solve the model that uses the Lagrangian relaxation method for finding lower bounds and a Lagrangian heuristic for obtaining feasible solutions. The procedure exploits certain special structures found in the Lagrangian multipliers which enable us to obtain good solutions to reasonably large test problems quickly.     

Lagrangian Smoothing Heuristics for Max-Cut

This paper presents a smoothing heuristic for an NP-hard combinatorial problem. Starting with a convex Lagrangian relaxation, a pathfollowing method is applied to obtain good solutions while gradually transforming the relaxed problem into the original problem formulated with an exact penalty function. Starting points are drawn using different sampling techniques that use randomization and eigenvectors. The dual point that defines the convex relaxation is computed via eigenvalue optimization using subgradient techniques. The proposed method turns out to be competitive with the most recent ones. The idea presented here is generic and can be generalized to all box-constrained problems where convex Lagrangian relaxation can be applied. Furthermore, to the best of our knowledge, this is the first time that a Lagrangian heuristic is combined with pathfollowing techniques. The work was supported by the German Research Foundation (DFG) under grant No 421/2-1.     

Multiple machine continuous setup lotsizing with sequence-dependent setups

We address the short-term production planning and scheduling problem coming from the glass container industry. A furnace melts the glass that is distributed to a set of parallel molding machines. Both furnace and machine idleness are not allowed. The resulting multi-machine multi-item continuous setup lotsizing problem with a common resource has sequence-dependent setup times and costs. Production losses are penalized in the objective function since we deal with a capital intensive industry. We present two mixed integer programming formulations for this problem, which are reduced to a network flow type problem. The two formulations are improved by adding valid inequalities that lead to good lower bounds. We rely on a Lagrangian decomposition based heuristic for generating good feasible solutions. We report computational experiments for randomly generated instances and for real-life data on the aforementioned problem, as well as on a discrete lotsizing and scheduling version.     

Real-time vehicle rerouting problems with time windows

This paper introduces and studies real-time vehicle rerouting problems with time windows, applicable to delivery and/or pickup services that undergo service disruptions due to vehicle breakdowns. In such problems, one or more vehicles need to be rerouted, in real-time, to perform uninitiated services, with the objective to minimize a weighted sum of operating, service cancellation and route disruption costs. A Lagrangian relaxation based-heuristic is developed, which includes an insertion based-algorithm to obtain a feasible solution for the primal problem. A dynamic programming based algorithm solves heuristically the shortest path problems with resource constraints that result from the Lagrangian relaxation. Computational experiments show that the developed Lagrangian heuristic performs very well.     

Using Lagrangian dual information to generate degree constrained spanning trees

In this paper, a Lagrangian-based heuristic is proposed for the degree constrained minimum spanning tree problem. The heuristic uses Lagrangian relaxation information to guide the construction of feasible solutions to the problem. The scheme operates, within a Lagrangian relaxation framework, with calls to a greedy construction heuristic, followed by a heuristic improvement procedure. A look ahead infeasibility prevention mechanism, introduced into the greedy heuristic, allowed us to solve instances of the problem where some of the vertices are restricted to having degrees 1 or 2. Furthermore, in order to cut down on CPU time, a restricted version of the original problem is formulated and used to generate feasible solutions. Extensive computational experiments were conducted and indicate that the proposed heuristic is competitive with the best heuristics and metaheuristics in the literature.     

A multi-period network design problem for cellular telecommunication systems

Mathematical Programming models for multi-period network design problems, which arise in cellular telecommunication systems are presented. The underlying network topologies range from a simple star to complex multi-layer Steiner-like networks. Linear programming, Lagrangian relaxation, and branch-and-cut heuristics are proposed and a polynomial-bounded heuristic based on an interior point linear programming implementation is described. Extensive computational results are presented on a number of randomly generated problem sets and the performance of the heuristic(s) are compared with an optimal branch-and-bound algorithm.     

A mathematical programming model and solution for scheduling production orders in Shanghai Baoshan Iron and Steel Complex

In this paper, we investigate the production order scheduling problem derived from the production of steel sheets in Shanghai Baoshan Iron and Steel Complex (Baosteel). A deterministic mixed integer programming (MIP) model for scheduling production orders on some critical and bottleneck operations in Baosteel is presented in which practical technological constraints have been considered. The objective is to determine the starting and ending times of production orders on corresponding operations under capacity constraints for minimizing the sum of weighted completion times of all orders. Due to large numbers of variables and constraints in the model, a decomposition solution methodology based on a synergistic combination of Lagrangian relaxation, linear programming and heuristics is developed. Unlike the commonly used method of relaxing capacity constraints, this methodology alternatively relaxes constraints coupling integer variables with continuous variables which are introduced to the objective function by Lagrangian multipliers. The Lagrangian relaxed problem can be decomposed into two sub-problems by separating continuous variables from integer ones. The sub-problem that relates to continuous variables is a linear programming problem which can be solved using standard software package OSL, while the other sub-problem is an integer programming problem which can be solved optimally by further decomposition. The subgradient optimization method is used to update Lagrangian multipliers. A production order scheduling simulation system for Baosteel is developed by embedding the above Lagrangian heuristics. Computational results for problems with up to 100 orders show that the proposed Lagrangian relaxation method is stable and can find good solutions within a reasonable time.