【作者】 靳鹏；

【导师】 杨善林；

【作者基本信息】 合肥工业大学 ， 管理科学与工程， 2013， 博士

【摘要】 传统下料问题研究给定母材情况下,确定下料模式及下料模式切割次数以满足子材需求。多数研究下料问题的文献,其研究目标主要为成本最小化,成本最小化主要有废料最小化、生产成本最小化、最小化下料模式数、母材总长度最小化以及最小化剩余产品等。也有一些文献的研究目标为盈利最大化。下料问题不仅在工业生产过程有着广泛地应用,而且也是运筹学、工业工程等学科研究的热点问题之一。实际下料过程中,下料活动只是企业经营过程的环节之一,企业不仅要考虑母材与子材逻辑结构关系,还要考虑生产过程其它方面的约束,如下料设备刀具约束、子材存放料箱约束、子材到期时间等。企业的生产经营优化要从全局角度出发,不仅注重企业内部生产过程的优化,同时也要分析外部环境对企业影响与制约。特别是供应链环境下,及时提供客户满意的产品与服务,对提高企业的核心竞争力更为重要。本文较为详细地研究能力受限多周期标准一维下料问题。基于多周期标准一维下料问题,研究供应链环境下母材采购与下料协调优化问题,下料与子材运输协调优化问题。对于下料与调度协调优化问题,重点研究料箱数受限的下料与调度协调优化问题,有公共交货期的下料与调度协调优化问题。本文主要的研究内容和创新点如下：(1)在多周期标准一维下料优化模型研究方面：加工子材的品种和数量越多,母材利用率就越高,降低母材使用成本,但下料模式的作业准备费用和时间消耗以及子材的库存费用却也随之增加。为此,本文考虑下料能力有限制、母材下料时间及下料模式作业准备时间等因素,研究母材下料、下料作业准备、子材库存三者之间协调优化问题。建立多目标非线性整数规划模型,目标是母材使用费用、下料作业准备费用和子材库存费用综合指标最小。采用拉格朗日松弛技术将模型转化为无能力约束的多周期标准一维下料模型：然后综合使用动态规划和列生成法求解无能力约束的多周期一维下料问题;基于次梯度方法求解能力受限的离散多周期一维下料问题；最后利用启发式算法处理与下料能力约束有冲突的解。(2)在采购与下料协调优化模型研究方面：首先,研究考虑母材订购成本的单周期母材采购与下料协调优化问题,多规格母材组合下料,增加母材平均长度与子材平均长度的比率,提高母材的利用率降低废料。考虑有许多供应商供应不同规格的母材,每家供应商的采购价格和母材购买价格不同。建立多产品多供应商采购与多母材一维下料协调优化模型,目标函数最小化母材使用费用、母材采购费用及作业准备费用总和。模型不仅研究基于母材分类的下料问题,而且研究多产品多供应商选择问题,模型弥补母材分类问题的研究缺陷。用拉格朗日松弛技术对模型进行分解,基于分支定界和列生成法构造启发式算法用于求解问题,给出具体求解步骤。数值实验表明多规格母材下料优于单规格母材下料。其次,研究多周期母材采购与下料联合优化模型研究,建立多目标非线性整数规划模型,模型同时考虑母材使用费用、子材库存费用、母材运输费用、母材订购费用及母材库存费用。用拉格朗日松弛技术将原问题分解为多周期多母材一维下料及多周期采购与供应商选择两个子问题。对于多周期多母材一维下料问题,限制母材最大规格数,考虑更换母材产生的作业准备费用,忽略同一规格母材下料模式作业准备费用,每个生产周期下料能力没有限制。对于多周期多产品采购与供应商选择问题,目标最小化母材订购费用、运输费用和库存费用。基于动态规划和分支定界设计启发式算法求解该问题。最后,用次梯度算法计算出原问题最优解,给出具体求解步骤。(3)在下料与调度协调优化模型研究方面：首先,研究给定料箱数的标准一维下料与下料模式排序联合优化问题。基于下料模式中子材品种数受限,任一下料模式中的子材品种数不大于料箱数,研究下料模式的生成问题。建立新型下料与模式排序协调优化模型,目标函数最小化母材使用费用及子材下料流程。其次,研究子材有公共交货期的一维下料与调度联合优化问题,基于子材延期交货惩罚权重,构造下料模式,建立非线性混合整数规划模型,目标函数最小化母材使用费用、子材拖后惩罚费用和。不同于传统下料模式生成方式,上述二个问题强调下料模式中的不同子材组合有着特殊的要求,应结合具体问题构造下料模式,采用两阶段算法求解模型,给出计算步骤。(4)在下料与运输协调优化模型研究方面：首先,研究单周期标准一维下料与运输联合优化问题。在标准一维下料问题基础上,依据下料模式数动态将子材运输分为多个阶段,研究了母材下料、子材库存与运输联合优化问题。不仅考虑母材使用费用及下料模式排序问题,而且考虑子材库存与运输问题。建立多目标非线性整数规划模型,最小化母材使用费用、子材库存费用和运输费用总和。其次,研究多周期多母材一维下料与运输联合优化问题。建立多目标非线性整数规划模型,目标函数由6部分组成,即母材使用费用、作业准备费用、子材库存费用、车辆运输费用、固定运输费用、客户端产品库存费用,优化目标是最小化各项费用总和。采用拉格朗日松弛技术将原问题分解为多周期多母材一维下料及库存与运输两个子问题。对于多周期多母材一维下料问题,考虑了R个不同规格母材下料产生的作业准备费用,忽略同一规格母材,不同下料模式产生的作业准备费用,将多周期多母材一维下料问题分解为R个多周期标准一维下料问题。基于动态规划和列生成法构建启发式算法求解问题。更多还原

【Abstract】 Traditionally, Cutting stock problems (CSP) consist of determining the best way of cutting a set of available large stock objects to smaller ordered items. In many articles, CSPs haave been studied with different goals such as minimal trim-loss, minimal production costs, minimal number of patterns, minimal total length and overproduction, etc. However, in some papers, they have also been used to describe value-maximization problems. CSPs occur in a wide range of industries and an extensive body of literature exists on solving these problems. Then, CSPs have been studied in many research disciplines such as management sciences, engineering sciences, information and computer sciences, mathematics, operations research and other. In many real world applications, Cutting stock is one of the production procedures in an enterprise. So, an enterprise not only considers the logical relationships between stocks and items, but also studies the other resource constraints on CSPs, for example cutting tools, the number of open stacks, and items with due date and other. According to the entire set of business optimization, a company not only pays attention to inside production and business procedures, but focus on the outside environment and resources constraints as well. In the environment of upstream and downstream supply chain operations, providing products or services timely and increasing customer satisfaction is one of the more important in enhancing the enterprise core competitive capacity.Firstly, this dissertation studies multi-period capacitated one-dimensional cutting stock problem (1D-CSP) in more detail. Secondly, based on above problem, it researches on integrated optimization problem of stock procurement and CSP and integrated optimization problem of CSP and item transportation based on supply chain. Finally, it studies integrated optimization problem of CSP and scheduling. The last problem includes integrated optimization problem of CSP and scheduling with considering the number of stack constraints and the coordination optimization problem of CSP and common due date scheduling.The major research and innovations are as follows:(1) For optimization model of multi-period1D-CSP, with increasing number of different item lengths and number of items the stock utilization generally improves, and hence the total stock cost decreases. On the other hand, a larger number of different cutting-patterns results in more frequent changes and setup consuming time and increases the inventory costs of items. Considering capacity of cutting process and cutting-pattern setup consuming time, the dissertation presents a multi-objective nonlinear integer programming model which studies balance among stock, cutting-pattem setup and inventory. The model’s objective is to minimize the costs of stock, cutting-pattern setup and inventory. Lagrangian relaxation of the capacity constraints allows this model to be decomposed into a set of multi-period uncapacitated1D-CSP Then, an approach integrated based on dynamic programming and column generation is presented for solving multi-period uncapacitated1D-CSP. Sub-gradient approach is employed for updating the Lagrangean multipliers and obtaining a feasible solution. Finally, a heuristic algorithm improving a solution conflicting with cutting process capacity is presented. Computational experiments are carried out to solve multi-period and one-by-one period1D-CSP. Such experiments showed that the multi-period model could obtain effective gains when compared with the one-by-one period solution. Further the cost of stock of multi-period cutting stock is lower than the total costs of stock of cutting stock in one-by-one period. (2) For coordination model of stock procurement and1D-CSP, firstly, this dissertation studies an integrated stock procurement with ordering cost and CSP with multiple length in a single period. A coordination optimization model of procurement and cutting stock with multi-products and multi-suppliers is formulated. This model’s objective function is to minimize stock, ordering and cutting-pattern setup costs. This dissertation studies not only1D-CSP with stock assortment problem, but also multiple product procurement with multiple supplier selection. This model makes up for a lack of stock assortment problem. Many different types of stock lengths which increase the ratio of the average stock to average order length can increase stock utilization rate and decrease trim loss. Lagrangian relaxation is employed to decompose the model. Heuristic algorithm based on the methods of column generation, branch-and-bound and subgradient, is developed for solving the problem. A distinctive solution steps is given. The calculation results demonstrate that1D-CSP with many different types of stock lengths greatly excelled single stock-size1D-CSP. Secondly, this disseitation presents an integrated stock procurement and cutting stock with multiple lengths in multiple periods. A multi-objective nonlinear integer programming model is formulated, and this model’s objective function is to minimize stock, item inventory, stock transportation, stock procurement and stock inventory costs. This model is decomposed into multi-period cutting stock problem with multi-length stock and multi-period multi-product procurement with supplier selection by means of Lagrangian relaxation technique. Multi-period1D-CSP model limits the number of types of stock and ignores cutting-pattern setup. This dissertation presents a hybrid heuristic which is composed of branch-and-bound and column generation and dynamic programming. For multi-period procurement with supplier selection problem, this dissertation develops a heuristic approach for this model which is based on dynamic programming and branch-and-bound. The sub-gradient algorithm is employed to calculate the optimal solution of the original problem.(3) For integrated1D-CSP and scheduling optimization model, firstly, this dissertation studies an integrated problem of1D-CSP and cutting-pattern sequencing with given the number of stacks. Considering constraint on the number of different types of items in a cutting pattern, it presents new model on coordination and optimization problem of1D-CSP and cutting-pattern sequencing, whose objective function is to minimize stock cost and span of items. Two-phase algorithm is proposed for solving the problem. The steps are given briefly. Secondly, it studies a coordination and optimization problem of1D-CSP and scheduling with a common due date. A non-linear mixed integer programming model is formulated. The objective function minimizes stock costs and item total weighted tardiness. Finally, the dissertation presents two two-stage heuristic optimization algorithms for each model.(4) For the coordination optimization problems of CSP and item transportation, firstly, an integrated optimization problem of1D-CSP and transportation is studied in a single-period. Depended on the1D-CSP, item transportation batches is divided into multiple stages according to the number of cutting patterns. A multi-objective nonlinear integer programming model is formulated, the model’s objective function is to minimize the total costs of stock, item inventory and transportation. Lagrangian relaxation is employed and then the model is decomposed into1D-CSP and transportation problem. Two heuristic algorithms are proposed for solving1D-CSP and transportation problem respectively. The subgradient algorithm is employed for solving the original model. Secondly, this dissertation studies integrating optimization problem of1D-CSP with multiple stock lengths and item transportation in multiple periods. It establishes a multi-objective non-linear integer programming model, whose objective function is to minimize stock costs, cutting-pattern setup costs, item inventory costs, vehicle costs, fixed transportation costs and product inventory costs. Then, the model is decomposed into multi-period CSP and multi-period transportation problem by means of Lagrangian relaxation. Multi-period CSP objective function includes setup costs of changing stock of different length and ignores cutting-pattern setup costs. Further, considering R types of different stock identical stock setup and ignoring identical stock setup, this dissertation decomposes multi-period CSP into R types of multi-period CSP. A heuristic algorithm, based on dynamic programming and column generation, is developed for solving R types of multi-period CSP. The inventory and transportation problem is a problem which one supplier serves a customer and supplier management client inventory. Based on dynamic programming, a heuristic algorithm is proposed for solving the inventory and transportation problem. A subgradient algorithm is employed for the original model.更多还原