可延迟供货的冷轧生产库存问题之建模与优化

本文针对可延迟供货的冷轧生产系统,建立了以最小化库存成本、拖期惩罚和启动成本为目标的多阶段生产库存模型,模型中充分考虑了工序不允许停机的情况以及计划与调度之间的一致性问题.同时开发了基于变量分离的有效拉格朗日松弛求解算法,并使用120个基于实际生产数据的算例进行了仿真实验,计算结果显示该算法能够在合理的时间内得到高质量的解.     

Hierarchical stochastic production planning for flexible automation workshops

This paper presents the hierarchical stochastic production planning (HSPP) problem for flexible automation workshops (FAWs) in agile manufacturing environments, which is a multiple-period multiple-product problem with random material supply, demands, capacities, processing times, rework and waste products. To solve the HSPP problem, a mathematical model is built up first. Then, an algorithm for HSPP is deduced in detail by using a stochastic interaction/prediction approach. The corresponding software package named as stochastic interaction/prediction algorithm (SIPA) has been developed and is presented in this paper, through which examples of HSPP have been studied, and which show that the algorithm can optimally decompose medium-term random product demand plans of an FAW into short-term stochastic production plans to be executed by FMSs in the FAW. Finally, the application of the algorithm is presented in detail through one of those examples.     

求解动态停泊计划问题的拉格朗日松弛算法

研究钢铁企业原料码头动态停泊计划问题,其动态特征主要体现在原料船动态到达并有两个或两个以上连续泊位且在停泊计划开始执行时每一泊位上仅有部分泊位长度可利用。针对这个问题,建立了一个数学模型并设计了改进拉格朗日算法在很短的时间内求得了近优解。在改进算法中使用了所提出的四个性质来分别加速求解子问题、乘子更新和获得可行解的过程。通过包含50个实际规模问题的算法性能实验表明改进的拉格朗日松弛算法相比未改进算法减少了80%的运行时间。     

基于拉格朗日松弛的供应链合作生产计划模型研究

为解决供应链生产计划协调问题,通过市场价格和中间库存因素使供应链上下游企业结合成一个整体,建立一种供应链上下游一体化计划模型,从整体考虑供应链合作计划问题．为获取问题的可行解,采用拉格朗日松弛技术进行优化,为供应链上下游企业在信息共享条件下实现“多赢”目标,提供了理论依据．仿真结果验证了模型和算法的有效性．     

Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports

The problem of transporting patients or elderly people has been widely studied in literature and is usually modeled as a dial-a-ride problem (DARP). In this paper we analyze the corresponding problem arising in the daily operation of the Austrian Red Cross. This nongovernmental organization is the largest organization performing patient transportation in Austria. The aim is to design vehicle routes to serve partially dynamic transportation requests using a fixed vehicle fleet. Each request requires transportation from a patient's home location to a hospital (outbound request) or back home from the hospital (inbound request). Some of these requests are known in advance. Some requests are dynamic in the sense that they appear during the day without any prior information. Finally, some inbound requests are stochastic. More precisely, with a certain probability each outbound request causes a corresponding inbound request on the same day. Some stochastic information about these return transports is available from historical data. The purpose of this study is to investigate, whether using this information in designing the routes has a significant positive effect on the solution quality. The problem is modeled as a dynamic stochastic dial-a-ride problem with expected return transports. We propose four different modifications of metaheuristic solution approaches for this problem. In detail, we test dynamic versions of variable neighborhood search (VNS) and stochastic VNS (S-VNS) as well as modified versions of the multiple plan approach (MPA) and the multiple scenario approach (MSA). Tests are performed using 12 sets of test instances based on a real road network. Various demand scenarios are generated based on the available real data. Results show that using the stochastic information on return transports leads to average improvements of around 15%. Moreover, improvements of up to 41% can be achieved for some test instances.     

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.     

柔性宽度浇次计划编制的一种混合改进算法

根据连铸工艺特点,炉次的宽度是柔性值,充分利用炉次宽度的柔性可以有效提高中间包的利用率,但同时会增加浇次计划的编制难度。根据柔性宽度浇次计划问题特征,建立其广义车辆路径问题模型,并构建一种混合改进算法进行求解。该算法基于局部-全局方法,将柔性宽度浇次计划问题分解为确定炉次顺序和选取炉次宽度两个子问题,并利用改进的交叉熵法和可达算法分别进行求解。最后通过实例表明了所提出模型和算法的有效性。     

Cross-facility management of production and transportation planning problem

This paper studies an integrated production and transportation planning problem in a two-stage supply chain. This supply chain consists of a number of facilities, each capable of producing the final product, and a number of retailers. We assume that retailers’ demands are known deterministically and there are no production or transportation capacity constraints. We formulate the problem as a network flow problem with fixed charge costs. This is an NP  -hard problem. To solve the problem we propose a primal-dual based heuristic that generates upper and lower bounds and runs in O(FRT²)$O({\mathit{FRT}}^2)$. The quality of the upper and lower bounds is tested on a large set of randomly generated problems. The maximum error reported for these problems is 4.36% and the maximum running time is 7.65 cpu seconds.     

汽车同步装配线生产计划与调度集成优化汽车同步装配线生产计划与调度集成优化

为克服传统的"自顶向下"方式下生产计划与调度不协调的缺陷,针对汽车同步装配线,构造了生产计划与调度集成优化混合整数规划模型,并采用拉格朗日松弛法将其分解为批量计划及调度等子问题.将调度子问题转化为与时间相关的旅行商问题,并采用dynasearch算法求解.对于拉格朗日对偶问题,采用均衡方向策略法求解.仿真实验结果验证了模型及算法的有效性.     

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.     

模糊需求和模糊能力约束的集约生产计划

通过对模糊需求量和模糊等式及模糊需求环境下生产-库存平衡方程两种等价的描述方法的基础上,建立了具有模糊需求量和模糊能力约束集约生产计划问题的最佳平衡模型(BAPP)、交互式集约计划模型(IAPP)和交互式求解方法.     

A maritime inventory routing problem with stochastic sailing and port times

This paper describes a stochastic short sea shipping problem where a company is responsible for both the distribution of oil products between islands and the inventory management of those products at consumption storage tanks located at ports. In general, ship routing and scheduling is associated with uncertainty in weather conditions and unpredictable waiting times at ports. In this work, both sailing times and port times are considered to be stochastic parameters. A two-stage stochastic programming model with recourse is presented where the first stage consists of routing, loading and unloading decisions, and the second stage consists of scheduling and inventory decisions. The model is solved using a decomposition approach similar to an L-shaped algorithm where optimality cuts are added dynamically, and this solution process is embedded within the sample average approximation method. A computational study based on real-world instances is presented.     

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.     

A two-stage approach to the orienteering problem with stochastic weights

The Orienteering Problem (OP) is a routing problem which has many interesting applications in logistics, tourism and defense. The aim of the OP is to find a maximum profit path or tour, which is feasible with respect to a capacity constraint on the total weight of the selected arcs. In this paper we consider the Orienteering Problem with Stochastic Weights (OPSWs) to reflect uncertainty in real-life applications. We approach this problem by formulating a two-stage stochastic model with recourse for the OPSW where the capacity constraint is hard. The model takes into account the effect that stochastic weights have on the expected total profit value to be obtained, already in the modeling stage. Since the expected profit is in general non-linear, we introduce a linearization that models the total profit that can be obtained for a given tour and a given scenario of weight realizations. This linearization allows for the application of Sample Average Approximation (SAA). The SAA solution asymptotically converges to the optimal solution of the two-stage model, but is computationally expensive. Therefore, to solve large instances, we developed a heuristic that exploits the problem structure of the OPSW and explicitly takes the associated uncertainty into account. In our computational experiments, we evaluate the benefits of our approach to the OPSW, compared to both a standard deterministic approach, and a deterministic approach that is extended with utilization of real-time information.     

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.     

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 Simultaneous Inventory Control and Facility Location Model with Stochastic Capacity Constraints

Traditionally, logistics analysts divide decisions levels into strategic, tactical and operational. Often these levels are considered separately for modeling purposes. The latter may conduce to make non-optimal decisions, since in reality there is interaction between the different levels. In this research, a cross-level model is derived to analyze decisions about inventory control and facility location, specially suited to urban settings, where the storage space is scarce and the vehicles’ capacity is usually restricted. Both conditions, on the one hand make the problem difficult to solve optimally but on the other hand make it more realistic and useful in practice. This paper presents a simultaneous nonlinear-mixed-integer model of inventory control and facility location decisions, which considers two novel capacity constraints. The first constraint states a maximum lot size for the incoming orders to each warehouse, and the second constraint is a stochastic bound to inventory capacity. This model is NP-Hard and presents nonlinear terms in the objective function and a nonlinear constraint. A heuristic solution approach is introduced, based on Lagrangian relaxation and the subgradient method. Numerical experiments were designed and applied. The solution procedure presented good performance in terms of the objective function. One of the key conclusions of the proposed modeling approach is the fact that a reduction of the inventory capacity does not necessarily imply an increase in the number of installed warehouses. In fact, reducing the order size allows the optimal allocation of customers (those with higher variances) into different warehouses, reducing the total system’s cost.     

再制造成本随机分布的生产优化问题研究

研究单一厂商制造/再制造集成系统的两期生产优化问题.首先,在回收率一定的条件下,建立回收产品的再制造成本与再制造率之间的函数关系;然后,建立以追求利润最大化为目标的模型,验证了该模型为凸规划,给出了K-T条件表达式,并分析了伽马分布条件下解的特征及其临界条件;最后,通过算例对该模型的性质和规律作进一步分析.     

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.