Hierarchical stochastic production planning for the highest business benefit

This paper addresses the hierarchical stochastic production planning (HSPP) problem of flexible automated workshops (FAWs), each with a number of flexible manufacturing systems (FMSs) the part-transfer between which is a delay of a time period. The problem not only includes uncertainties in the demand, capacities, material supply, processing times, necessity for rework, and scrap, but also considers multiple products and multiple time periods. The objective is to develop a production plan which tells each FMS how many parts to produce and when to produce them so as to obtain the highest business benefit. Herein, the HSPP problem is formulated by a stochastic nonlinear programming model whose constraints are linear but whose objective function is piecewise linear. For the convenience of solving the stochastic nonlinear programming model above, it is approximately transformed into a deterministic nonlinear programming model and further into a linear programming model. Because the scale of the model for a general workshop is too large to be solved by the simplex method on a personal computer within acceptable time, Karmarkar's algorithm and an interaction/prediction algorithm, respectively, are used to solve the model, the former for the medium or small scale problems and the latter for the large scale problems. By the implementation of the above-mentioned algorithms and through many HSPP examples, Karmarkar's algorithm, the interaction/prediction algorithm and the linear programming method in Matlab 5.0 are compared, the result of which shows that the proposed approaches are very effective and suitable for not only “push” production but also “pull” production.     

最优递阶随机生产计划与控制

研究了敏捷制造车间(AMW)中的最优递阶随机生产计划与控制问题.首先根据实际需要建立关联方程有延迟的车间生产的随机非线性规划模型,即一种求解动态优化问题的静态优化模型.为求解方便将其转化成确定非线性规划模型并通过引进约束进一步转化成线性规划模型.然后,提出分别用卡马卡算法和基于卡马卡算法的关联预测法进行求解,并编制了相应软件.算例研究表明所提方法是非常有效的.     

Hierarchical production planning for complex manufacturing systems

A hierarchical approach to production planning for complex manufacturing systems is presented. A single facility comprising a number of work-centers that produce multiple part types is considered. The planning horizon includes a sequence of time periods, and the demand for all part types is assumed known. The production planning problem consists of minimizing the holding costs for all part types, as well as the work-in-process and the backlogging costs for the end items. We present a two-level hierarchy that is based on aggregating parts to part families, work-centers to manufacturing cells and time periods to aggregate time periods. The solution at the aggregate level is imposed as a constraint to the detailed level problems which are formulated for each manufacturing cell separately. This architecture uses a rolling horizon strategy to perform the production management function. We have employed perturbation analysis techniques to adjust certain parameters of the optimization problems at the detailed level to reach a near-optimal detailed production plan. Numerical results for several realistic example problems are presented and the solutions obtained from the hierarchical and monolithic approaches are compared. The results indicate that the hierarchical approach offers major advantages in computational efficiency, while the loss of optimality is acceptable.     

A stochastic production planning problem with nonlinear cost

Most production planning models are deterministic and often assume a linear relation between production volume and production cost. In this paper, we investigate a production planning problem in a steel production process considering the energy consumption cost which is a nonlinear function of the production quantity. Due to the uncertain environment, the production demands are stochastic. Taking a scenario-based approach to express the stochastic demands according to the knowledge of planners on the demand distributions, we formulate the stochastic production planning problem as a mixed integer nonlinear programming (MINLP) model.Approximated with the piecewise linear functions, the MINLP model is transformed into a mixed integer linear programming model. The approximation error can be improved by adjusting the linearization ranges repeatedly. Based on the piecewise linearization, a stepwise Lagrangian relaxation (SLR) heuristic for the problem is proposed where variable splitting is introduced during Lagrangian relaxation (LR). After decomposition, one subproblem is solved by linear programming and the other is solved by an effective polynomial time algorithm. The SLR heuristic is tested on a large set of problem instances and the results show that the algorithm generates solutions very close to optimums in an acceptable time. The impact of demand uncertainty on the solution is studied by a computational discussion on scenario generation.     

A robust hierarchical production planning for a capacitated two-stage production system

In this paper, we propose a robust hierarchical production planning approach for a two-stage real world capacitated production system operating in an uncertain environment. The first stage of the system produces a set of semi-finished products having relatively stable annual demands, and the second finishing stage produces finished products having highly variable weekly demands. The fixed production setup costs incurred at the first stage are considerably high. Fixed production setup costs incurred at the second stage are fairly small compared to those of the first stage. We propose an integrated hierarchical planning model, where semi-finished products from the first stage (i.e. the aggregate level) are disaggregated into finished products to be produced in the second stage (i.e. the operational level). As a result of the relatively stable demands and the high setup costs experienced at the first stage, a cyclical aggregate planning model is proposed for production planning at the upper level of the hierarchical plan. Based on this aggregate plan, a modified periodic review policy is then proposed for production planning at the lower level. Finally, a coupling plan, linking the two planning levels, is proposed to ensure the feasibility of the disaggregation process at every period.     

柔性自动化车间生产计划的最优分解

研究了柔性自动化车间生产计划的最优分解问题,首先根据实际需要建立车间生产计划的非线性规划模型,然后为求解方便将其转化成线性规划模型,由于这种模型对于一般车间来讲其规模已经很大,很难在微机上用单纯形法求争,为此,提出分别用卡马卡算法和一种新的基于卡马卡算法的关联预测法来求解车间生产计划的最优分解问题,并编制了相应软件,最后通过算例研究,比较了卡马卡算法、基于卡马卡算法的关联预测法和Matlab中的线性规划法,结果表明所提方法是非常有效的。     

Multi-objective supply planning for two-level assembly systems with stochastic lead times

This paper considers two-level assembly systems whose lead times of components are stochastic with known discrete random distributions. In such a system, supply planning requires determination of release dates of components at level 2 in order to minimize expected holding cost and to maximize customer service. Hnaien et al. [Hnaien F, Delorme X, Dolgui A. Multi-objective optimization for inventory control in two-level assembly systems under uncertainty of lead times. Computers and Operations Research 2010; 37:1835-43] have recently examined this problem, trying to solve it through multi-objective genetic algorithms. However, some reconsideration in their paper is unavoidable. The main problem with Hnaien et al. proposal is their wrong mathematical model. In addition, the proposed algorithms do not work properly in large-scale instances. In the current paper, this model is corrected and solved via a new approach based on NSGA-II that is called Guided NSGA-II. This approach tries to guide search toward preferable regions in the solution space. According to the statistical analyses, the guided NSGA-II has the higher performance in comparison with the basic NSGA-II used by Hnaien et al. Moreover, the wrongly reported characteristics of the Pareto front shape provided by Hnaien et al. are modified.     

A hierarchic approach to production planning and scheduling of a flexible manufacturing system

The paper deals with the problem of improving the machine utilization of a flexible manufacturing cell. Limited tool magazine space of the machines turns out to be a relevant bottleneck. A hierarchic approach for this problem is proposed. At the upper level, sets of parts that can be concurrently processed (batches) are determined. At the lower levels, batches are sequenced, linked, and scheduled. Methods taken from the literature are used for the solution of the latter subproblems, and an original mixed integer programming model is formulated to determine batches. The proposed methods are discussed on the basis of computational experience carried out on real instances.     

On stochastic dynamic programming for solving large-scale planning problems under uncertainty

The stochastic dynamic programming approach outlined here, makes use of the scenario tree in a back-to-front scheme. The multi-period stochastic problems, related to the subtrees whose root nodes are the starting nodes (i.e., scenario groups), are solved at each given stage along the time horizon. Each subproblem considers the effect of the stochasticity of the uncertain parameters from the periods of the given stage, by using curves that estimate the expected future value (EFV) of the objective function. Each subproblem is solved for a set of reference levels of the variables that also have nonzero elements in any of the previous stages besides the given stage. An appropriate sensitivity analysis of the objective function for each reference level of the linking variables allows us to estimate the EFV curves applicable to the scenario groups from the previous stages, until the curves for the first stage have been computed. An application of the scheme to the problem of production planning with logical constraints is presented. The aim of the problem consists of obtaining the planning of tactical production over the scenarios along the time horizon. The expected total cost is minimized to satisfy the product demand. Some computational experience is reported. The proposed approach compares favorably with a state-of-the-art optimization engine in instances on a very large scale.     

A stochastic algorithm for makespan minimized multi-agent path planning in discrete space

Makespan minimized multi-agent path planning (MAPP) requires the minimization of the time taken by the slowest agents to reach its destination. The resulting minimax objective function is non-smooth and the search for an optimal solution in MAPP can be intractable. In this work, a maximum entropy function is adopted to approximate the minimax objective function. An iterative algorithm named probabilistic iterative makespan minimization (PIMM) is then proposed to approximate a makespan minimized MAPP solution by solving a sequence of computationally hard MAPP minimization problems with a linear objective function. At each iteration, a novel local search algorithm called probabilistic iterative path coordination (PIPC) is used to find a sufficiently good solution for each MAPP minimization problem. Experimental results from comparative studies with existing MAPP algorithms show that the proposed algorithm strikes a good tradeoff between the quality of the makespan minimized solution and the computational cost incurred.     

基于关联预测法的递阶生产计划与控制*

本文在研究实现有多种递阶生产计划和控制模型的基础上,提出用关联预测法来解决柔性自动化车间（ＦＡＷ）的最优递阶生产计划与控制问题。文中首先建立ＦＡＷ生产控制的数学模型,然后推导ＦＡＷ递阶生产计划的关联预测算法,编写了基于该算法的ＩＰＡ软件包并进行了算例研究,同现有的计划分解方法相比,这里的方法更适于将ＣＩＭＳ／ＭＲＰⅡ下达给ＦＡＷ的中期计划最优分解成由ＦＡＷ中各ＦＭＳ执行的短期计划。     

Analytical study on multi-product production planning with outsourcing

This paper studies a problem on multi-product capacitated production planning with outsourcing. The context of the problem is about an enterprise that manufactures multiple products in multiple periods for stochastic demands. Manufacturers usually have two alternative modes for the production: one is to outsource parts from outside suppliers and then assemble them; the other is to in-house manufacture parts and then assemble them. Each mode has its relative merits. In addition, the capacity constraint by in-house manufacturing is also taken into account. This paper investigates how to balance the trade-off between the two modes. An analytical approach is proposed to study the optimal decision on the above two modes for all products during each planning period. Some findings are drawn out from this analytical study. Numerical experiments show the significant cost reduction can be obtained using the proposed decision model.     

A robust dynamic planning strategy for lot-sizing problems with stochastic demands

We consider the question of generating robust plans for production planning problems under uncertainty. In particular, we present an alternative approach to generate robust solutions for lot-sizing problems with stochastic demand. The proposed approach is dynamic and includes a decision rule that guides the planner. The decision rule parameters are determined so that the number of expected planning adaptations and their magnitudes are under control. The robust approach and its related models are presented together with some computational results to show how it performs compared to other approaches.     

Integration of process planning and production scheduling based on genetic algorithm

Lacking of flexibility in the traditional workshop production, a genetic algorithm is proposed to implement the integration of process planning and production scheduling. In this paper, the processing routes and processing machine are selected through chromosome crossover and mutation, in order to implement the optimal scheduling of the flexible workshop production. Meanwhile, a performance test about the integration of process planning and production scheduling is implemented, and the results shows that the genetic algorithm is efficient to obtain optimal or near optimal process routes which can meet the requirements of production scheduling.     

Analytical results for the performance and the control of stochastic flow systems

Design and control problems of failure-prone production lines are explored by means of simple mathematical models. The fluctuations of the performances are introduced via random environments which are modelled by non-Markovian alternating renewal processes. The production output can either be discrete or continuous processes. For these modelling frameworks, we calculate explicitly the average and the variance of the following quantities: (1) the cumulate production output, (2) the random time needed to complete a given production batch and (3) the output of a buffered production dipole. Finally, the optimal control of a single failure prone machine which delivers a single part type is considered. The demand rate is taken to be constant. Deviations of the production output from the demand are penalized by a convex cost function. The operating states of the machine are again modelled by a non-Markovian alternating process. Under the assumption that a hedging point policy is optimal, we calculate explicitly the position of this hedging stock as a function of the coefficient of variation of the time to failure.     

A stochastic programming model for strategic capacity planning in thin film transistor-liquid crystal display (TFT-LCD) industry

This paper studies strategic capacity planning problems under demand uncertainties in thin film transistor-liquid crystal display (TFT-LCD) industry. Due to the following trends, capacity planning has become a critical strategic issue in TFT-LCD industry: (1) complex product hierarchy and product types caused by a wide range of product applications; (2) coexistence of multiple generation of manufacturing technologies in a multi-site production system; and (3) rapid growing and changing market demand derived by the needs for replacing traditional cathode ray tube (CRT) display. Furthermore, demand forecasts are usually inaccurate and vary rapidly over time.     

A two-stage stochastic programming approach for project planning with uncertain activity durations

This paper investigates the problem of setting target finish times (due dates) for project activities with random durations. Using two-stage integer linear stochastic programming, target times are determined in the first stage followed by the development of a detailed project schedule in the second stage. The objective is to balance (1) the cost of project completion as a function of activity target times with (2) the expected penalty incurred by deviating from the specified values. It is shown that the results may be significantly different when deviations are considered, compared to when activities are scheduled as early as possible in the traditional way. For example, the optimal target completion time for a project may be greater than the makespan of the early-start schedules under any scenario. To find solutions, an exact algorithm is developed for the case without a budget constraint and is used as a part of a heuristic when crashing is permitted. All computational procedures are demonstrated on a set of 150 benchmark problems consisting of 90 activities each.     

基于多代理的供应链协同生产计划模型

供应链是由分布在全球的供应商、制造商、仓库、分销中心和零售商组成的复杂网络。其生产计划具有分布性,自治性,同步性和开放性等特点,使得传统的生产计划方法已经不能适应供应链的计划需求。在分析了多代理技术和供应链系统生产计划特点的基础上,采用智能代理封供应链系统的功能实体和物理实体进行封装,提出了一个基于多代理的供应链系统网络模型,并构建了基于多智能代理的生产计划运行模式。该生产计划模型分为三层：全局生产计划,企业内部子生产计划和各个任务的详细生产计划。它突破了传统生产计划的局限性,从全局规划的角度来整合供应链上的所有资源,消除了不同企业子生产计划所产生的冲突和差异。很好的体现了供应链系统信息共享和资源共享的原则。     

A Petri net model for integrated process and job shop production planning

In this paper a new Petri net class (Chameleon systems) for modeling and analyzing joined process planning and job shop production planning is proposed based on the multi-level Petri net model introduced by Valk (1995). Chameleon system is a High-level Petri net extended with time that consists of a High-level Petri net modeling the workshop which is called system net and ordinary Petri net modeling the jobs and setups which act as tokens of the system net and therefore are called token nets. Process plans of the jobs are partial orders of operation groups and alternatives. The uncertainty of operation duration is captured by a new time model. The advantages of this new modeling approach are the following: (i) a modular construction of the joined process and job shop planning is allowed, (ii) classical known Petri net analysis methods can be applied and (iii) the analysis can be done at different levels of abstraction.     

A mathematical model on EPQ for stochastic demand in an imperfect production system

In the paper, we develop an EPQ (economic production quantity) inventory model to determine the optimal buffer inventory for stochastic demand in the market during preventive maintenance or repair of a manufacturing facility with an EPQ (economic production quantity) model in an imperfect production system. Preventive maintenance, an essential element of the just-in-time structure, may cause shortage which is reduced by buffer inventory. The products are sold with the free minimal repair warranty (FRW) policy. The production system may undergo “out-of-control” state from “in-control” state, after a certain time that follows a probability density function. The defective (non-conforming) items in “in-control” or “out-of-control” state are reworked at a cost just after the regular production time. Finally, an expected cost function regarding the inventory cost, unit production cost, preventive maintenance cost and shortage cost is minimized analytically. We develop another case where the buffer inventory as well as the production rate are decision variables and the expected unit cost considering the above cost functions is optimized also. The numerical examples are provided to illustrate the behaviour and application of the model. Sensitivity analysis of the model with respect to key parameters of the system is carried out.