An aggregate production planning for a heavy manufacturing industry

This paper proposes a linear programming formulation of the aggregate production planning problem in the context of a heavy manufacturing industry. A basic model is first developed under the special requirements of the industry, to minimize the total cost of production which is assumed to be piecewise linear. The basic model is then transformed into a linear programming model to seek an optimal solution for a series of planning periods within the planning horizon. The results of the application to a real world situation are also included.     

Modular Decision Analysis—A Production-Scheduling Illustration

A simple production-scheduling problem is used to illustrate one aspect of the modular decision-analysis approach. Superficially the approach illustrated resembles dynamic programming, but it provides considerably more flexibility and insight into the problem situation than conventional dynamic programming. The approach involves a forward iteration process, which exploits separability characteristics of the problem. A production schedule is built up by considering successive production periods up to the planning horizon. A central feature of the approach is the use of a series of two-dimensional state-action diagrams which portray feasible production strategies. Explicit representation of alternative strategies in this way greatly facilitates the determination of good strategies in terms of direct use of a criterion function and constraints, sensitivity and robustness analysis. The approach can be extended to handle more realistic problem situations, as indicated briefly.     

An MIP-based interval heuristic for the capacitated multi-level lot-sizing problem with setup times

This paper considers the capacitated multi-level lot-sizing problem with setup times, a class of difficult problems often faced in practical production planning settings. In the literature, relax-and-fix is a technique commonly applied to solve this problem due to the fact that setup decisions in later periods of the planning horizon are sensitive to setup decisions in the early periods but not vice versa. However, the weakness of this method is that setup decisions are optimized only on a small subset of periods in each iteration, and setup decisions fixed in early iterations might adversely affect setup decisions in later periods. In order to avoid these weaknesses, this paper proposes an extended relax-and-fix based heuristic that systematically uses domain knowledge derived from several strategies of relax-and-fix and a linear programming relaxation technique. Computational results show that the proposed heuristic is superior to other well-known approaches on solution qualities, in particular on hard test instances.     

A lexicographic approach to bi-objective scheduling of single-period orders in make-to-order manufacturing

This paper presents a lexicographic approach and integer programming formulations for a dual-objective, long-term production scheduling in make-to-order manufacturing environment. The problem objective is to assign single-period customer orders for various product types to planning periods to complete all the orders with minimum number of tardy orders as a primary criterion and to level the aggregate production or the total capacity utilization over a planning horizon as a secondary criterion. Each order must be completed during one planning period. The basic integer programming formulation has been strengthened by the addition of some cutting constraints derived by relating the demand on required capacity to available capacity for each subset of orders with the same due date. The approach has been applied to optimize production schedules in a flexible flowshop made up of several processing stages in series, with identical, parallel machines, and an output buffer of limited capacity for holding completed products before delivery to the customers. Numerical examples modeled after a real-world make-to-order flexible assembly line in the electronics industry are provided and some computational results are reported.     

Integrating two-dimensional cutting stock and lot-sizing problems

The two-dimensional cutting stock problem (2DCSP) consists in the minimization of the number of plates used to cut a set of items. In industry, typically, an instance of this problem is considered at the beginning of each planning time period, what may result in solutions of poor quality, that is, excessive waste, when a set of planning periods is considered. To deal with this issue, we consider an integrated problem, in which the 2DCSP is extended from the solution in only a single production planning period to a solution in a set of production planning periods. The main difference of the approach in this work and the ones in the literature is to allow sufficiently large residual plates (leftovers) to be stored and cut in a subsequent period of the planning horizon, which may further help in the minimization of the waste. We propose two integrated integer programming models to optimize the combined two-dimensional cutting stock and lot-sizing problems, minimizing the total cost, which includes material, waste and storage costs. Two heuristics based on the industrial practice to solve the problem were also presented. Computational results for the proposed models and for the heuristics are presented and discussed.     

The economic lot scheduling problem under extended basic period and power-of-two policy

The economic lot scheduling problem schedules the production of several different products on a single machine over an infinite planning horizon. In this paper, a nonlinear integer programming model is used to determine the optimal solution under the extended basic period and power-of-two policy. A small-step search algorithm is presented to find a solution which approaches optimal when the step size approaches zero, where a divide-and-conquer procedure is introduced to speed up the search. Further a faster heuristic algorithm is proposed which finds the same solutions in almost all the randomly generated sample cases.     

Polyhedral analysis for the two-item uncapacitated lot-sizing problem with one-way substitution

We consider a production planning problem for two items where the high quality item can substitute the demand for the low quality item. Given the number of periods, the demands, the production, inventory holding, setup and substitution costs, the problem is to find a minimum cost production and substitution plan. This problem generalizes the well-known uncapacitated lot-sizing problem. We study the projection of the feasible set onto the space of production and setup variables and derive a family of facet defining inequalities for the associated convex hull. We prove that these inequalities together with the trivial facet defining inequalities describe the convex hull of the projection if the number of periods is two. We present the results of a computational study and discuss the quality of the bounds given by the linear programming relaxation of the model strengthened with these facet defining inequalities for larger number of periods.     

A note on makespan minimization in two-stage flexible flow shops with uniform machines

We consider the two-stage flexible flow shop makespan minimization problem with uniform parallel machines. Soewandi and Elmaghraby [Soewandi, H., Elmaghraby, S., 2003. Sequencing on two-stage hybrid flowshops with uniform machines to minimize makespan. IIE Transaction 35, 467–477] developed a heuristic (S–E) and derived a machine speed-dependent worst-case ratio bound for it. We point out that this bound works well when the uniform machines have approximately equal speeds but is not indicative of the performance of the S–E heuristic when the machine speeds are in a wide range. Motivated by this observation, we propose an alternative tight machine-speed dependent worst-case bound for the S–E heuristic that works well when the machine speeds vary significantly. We then combine the two speed-dependent ratio bounds into a speed-independent bound. Our findings facilitate the narrowing of the gap between experimental performance and worst-case bound for the S–E heuristic.     

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.     

DEA based dimensionality reduction for classification problems satisfying strict non-satiety assumption

This study shows how data envelopment analysis (DEA) can be used to reduce vertical dimensionality of certain data mining databases. The study illustrates basic concepts using a real-world graduate admissions decision task. It is well known that cost sensitive mixed integer programming (MIP) problems are NP-complete. This study shows that heuristic solutions for cost sensitive classification problems can be obtained by solving a simple goal programming problem by that reduces the vertical dimension of the original learning dataset. Using simulated datasets and a misclassification cost performance metric, the performance of proposed goal programming heuristic is compared with the extended DEA-discriminant analysis MIP approach. The holdout sample results of our experiments shows that the proposed heuristic approach outperforms the extended DEA-discriminant analysis MIP approach.     

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.     

Robust optimal dynamic production/pricing policies in a closed-loop system

Hybrid manufacturing/remanufacturing systems play a key role in implementing closed-loop production systems which have been considered due to increasingly environmental concerns and latent profit of used products. Manufacturing and remanufacturing rates, selling price of new products, and acquisition price of used products are the most critical variables to optimize in such hybrid systems. In this paper, we develop a dynamic production/pricing problem, in which decisions should be made in each period confronting with uncertain demand and return. The manufacturer is able to control the demand and return by adjusting selling price and acquisition price respectively, also she can stock inventories of used and new products to deal with uncertainties. Modeling a nominal profit maximization problem, we go through robust optimization approach to reformulate it for the uncertain case. Final robust optimization model is obtained as a quadratic programming model over discrete periods which can be solved by optimization packages of QP. A numerical example is defined and sensitivity analysis is performed on both basic parameters and parameters associated with uncertainty to create managerial views.     

Multi-item lot-sizing with joint set-up costs

We consider a multi-item lot-sizing problem with joint set-up costs and constant capacities. Apart from the usual per unit production and storage costs for each item, a set-up cost is incurred for each batch of production, where a batch consists of up to C units of any mix of the items. In addition, an upper bound on the number of batches may be imposed. Under widely applicable conditions on the storage costs, namely that the production and storage costs are nonspeculative, and for any two items the one that has a higher storage cost in one period has a higher storage cost in every period, we show that there is a tight linear program with O(mT ²) constraints and variables that solves the joint set-up multi-item lot-sizing problem, where m is the number of items and T is the number of time periods. This establishes that under the above storage cost conditions this problem is polynomially solvable. For the problem with backlogging, a similar linear programming result is described for the uncapacitated case under very restrictive conditions on the storage and backlogging costs. Computational results are presented to test the effectiveness of using these tight linear programs in strengthening the basic mixed integer programming formulations of the joint set-up problem both when the storage cost conditions are satisfied, and also when they are violated.     

The optimal control of just-in-time-based production and distribution systems and performance comparisons with optimized pull systems

In just-in-time (JIT) production systems, there is both input stock in the form of parts and output stock in the form of product at each stage. These activities are controlled by production-ordering and withdrawal kanbans. This paper discusses a discrete-time optimal control problem in a multistage JIT-based production and distribution system with stochastic demand and capacity, developed to minimize the expected total cost per unit of time. The problem can be formulated as an undiscounted Markov decision process (UMDP); however, the curse of dimensionality makes it very difficult to find an exact solution. The author proposes a new neuro-dynamic programming (NDP) algorithm, the simulation-based modified policy iteration method (SBMPIM), to solve the optimal control problem. The existing NDP algorithms and SBMPIM are numerically compared with a traditional UMDP algorithm for a single-stage JIT production system. It is shown that all NDP algorithms except the SBMPIM fail to converge to an optimal control.Additionally, a new algorithm for finding the optimal parameters of pull systems is proposed. Numerical comparisons between near-optimal controls computed using the SBMPIM and optimized pull systems are conducted for three-stage JIT-based production and distribution systems. UMDPs with 42 million states are solved using the SBMPIM. The pull systems discussed are the kanban, base stock, CONWIP, hybrid and extended kanban.     

Two-stage stochastic lot-sizing problem under cost uncertainty

For production planning problems, cost parameters can be uncertain due to marketing activities and interest rate fluctuation. In this paper, we consider a single-item two-stage stochastic lot-sizing problem under cost parameter uncertainty. Assuming cost parameters will increase or decrease after time period p each with certain probability, we minimize the total expected cost for a finite horizon problem. We develop an extended linear programming formulation in a higher dimensional space that can provide integral solutions by showing that its constraint matrix is totally unimodular. We also project this extended formulation to a lower dimensional space and obtain a corresponding extended formulation in the lower dimensional space. Final computational experiments demonstrate that the extended formulation is more efficient and performs more stable than the two-stage stochastic mixed-integer programming formulation.     

基于可信性理论的生产计划期望值模型

基于可信性理论,提出一类新的模糊生产计划期望值模型.然后,讨论这个模糊生产计划模型的基本性质.最后,利用这个模糊模型的基本性质我们可以把模糊生产计划期望值模型转化为一个线性规划模型并且设计相应的算法求解模糊生产计划问题的一个数值例子.     

One way to solve the parametric quadratic programming problem

A method is presented for the solution of the parametric quadratic programming problem by the use of conjugate directions. It is based on the method for quadratic programming proposed by the author in [1].While engaged in this research the author had a part-time post with the Manpower Services Commission.     

Marginal values in mixed integer linear programming

For a given optimization problem, P, considered as a function of the data, its marginal values are defined as the directional partial derivatives of the value of P with respect to perturbations in that data. For linear programs, formulas for the marginal values were given by Mills, [10], and further developed by the current author [16]. In this paper, the marginal value formulas are extended to the case of mixed integer linear programming (MIP). As in ordinary linear programming, discontinuities in the value can occur, and the analysis here identifies them. This latter aspect extends previous work on continuity by the current author, [18], Geoffrion and Nauss, [5], Nauss, [11], and Radke, [12], and work on the value function of Blair and Jeroslow, [2]. Application is made to model formulation and to post-optimal analysis.Supported in part by the Air Force Office of Scientific Research, Grant # AFSOR-0271 to Rutgers University.     

A decomposition algorithm for solving certain classes of production-transportation problems with concave production cost

This paper addresses a method for solving two classes of production-transportation problems with concave production cost. By exploiting a special network structure both problems are reduced to a kind of resource allocation problem. It is shown that the resultant problem can be solved by using dynamic programming in time polynomial in the number of supply and demand points and the total demand.The author was partially supported by Grand-in-Aid for Scientific Research of the Ministry of Education, Science and Culture, Grant No. (C)05650061.     

More on subgradient duality

A duality theorem of P. Wolfe for nonlinear differential programming has been extended by the author to the non-differentiable case by replacing gradients by subgradients. In this paper this extended result is improved by allowing additional types of constraints. Also a converse duality theorem is proved.