石化企业能力批量问题的模型与算法研究
文献类型:学位论文
作者 | 刘晓 |
学位类别 | 博士 |
答辩日期 | 2004-12-20 |
授予单位 | 中国科学院沈阳自动化研究所 |
授予地点 | 中国科学院沈阳自动化研究所 |
导师 | 王成恩 ; 储诚斌 |
关键词 | 生产/采购计划 批量 单产品 库存 动态规划算法 |
其他题名 | Research on Models and Algorithms for Capacitated Lot Sizing Problems in Petrochemical Industries |
学位专业 | 机械电子工程 |
中文摘要 | 面对日趋激烈的竞争和全球化的市场需求,制造企业必须考虑各种资源在时间和空间上的优化分配以降低成本,提高自身的竞争能力。带能力约束的批量计划问题是理论上研究的难点,也是在生产活动中产生重大经济效益的主要问题之一。尽管经典的库存理论以及带能力约束的批量问题的研究已经有几十年的历史,但随着新的生产模式的出现,如外包、不完全满足需求等生产形式的出现,使得按时满足需求的计划模式不再适用。企业必须改变经营理念,合理决策以确保其竞争优势。近年来,随着国内外学者对各类批量计划问题研究的不断深入以及相关学科的发展,涌现出了一些新的生产计划理论和方法。由于带能力约束的批量计划问题广泛存在于工业生产的各个领域,如石化企业,玻璃,钢材,造纸,食品等制造行业。因此,对带能力约束的批量问题的理论研究,探索有效和实用的算法,一直是运筹学、管理科学和工业工程等领域所关注的研究热点。本文以石化企业为背景,研究了带能力约束的批量计划问题,主要内容包括以下几个方面:本文通过对历史文献的详尽综述,将带能力约束的批量计划问题归纳为四类模型:即不允许拖期模型,允许拖期模型,清仓模型和持有模型。给出它们的准确定义和模型特点。在总结了上述模型的求解技术的基础上,对目前存在的问题进行以下几方面的扩展研究。首先,扩展了一般情况下的单产品带能力约束的批量问题的概念。由于模型中需求被全部满足的假设对企业来讲并非是最优的,在生产实际中常常存在不完全满足情况。例如,当某时段的市场需求大于企业的能力时,企业首先要决定哪些需求要失去或外包;另一种情况是即使企业有能力全部满足,但按时满足需求可能导致过多的库存成本或调整成本。为了最小化总成本,允许在某时段拖期满足或失去需求的情况在实际生产中经常发生。因此,我们将带能力约束的批量计划问题的概念扩展到更一般的情况,即模型中允许拖期满足和失去需求的情况。与传统模型不同的是:扩展后的模型对成本函数没有任何假定,即需求、能力和成本函数在每个时段可能是线性的、凹函数、凸函数的或者是任意的。模型中不仅考虑了生产能力,而且考虑库存能力和最大拖期数量等方面的限制。对于这样一个复杂的NP-hard问题,由于各种约束的存在可能使得问题不一定存在可行解。为了便于求解该问题,我们首先将问题归结为有向网络流问题。给出判断可行解存在的充分必要条件,并用Bellman/Ford算法给出可行解的上界和下界,以缩小最优解的搜索空间。如果可行解存在,设计了求解该问题的有效算法,并在理论上分析了算法的计算复杂度和空间复杂度。采用这样的方法和思路,提出了允许/不允许拖期满足模型,清仓模型和持有模型下的求解问题的动态规划方法的伪多项式时间算法。在分析炼油企业主要生产特点的基础上,建立了带库存能力约束的一类特殊情况下的单产品生产批量批量模型。其目标是最小化调整费用、生产费用、库存持有费用和失去需求惩罚费用总和。研究了不完全满足情况下的清仓和持有两类模型,找到并证明了最优解的零库存定单特性存在于两类模型中。通过将问题归结为网络流问题,证明最优解的特性,来缩小最优解的搜索空间。分别设计了求解问题的两种动态规划算法,使其在多项式时间内可解。并从理论上分析了算法的计算复杂度,给出数值实验结果表明了算法的有效性。随后,我们将带库存能力约束的单产品生产批量计划问题模型扩展到更一般的情况:即成本函数为凹函数情况。研究了一类特殊成本函数结构下的清仓模型,找到了最优解的一些新特性。根据这些特性,设计了求解问题的多项式时间可解的算法。从理论上分析了算法的计算复杂度,并给出的算法实例。对多产品、多供应商、多炼油厂的分布式供应链下的原油采购计划问题,建立了以最小化提前/拖期惩罚费用,生产成本和运输成本的总和为目标,同时最小化供应链的循环时间的多目标优化数学模型。通过对模型的数学推导将其转换为线性规划问题,并利用AHP法求解多目标规划模型。所提出的模型和方法不仅能编制有效的采购计划,使采购成本和供应链的循环时间最小化,而且能够合理选择供应商,优化资源配置,满足客户对产品质量和交货期的要求。数值实验表明所提出的方法的有效性和可行性。 |
索取号 | F27/L75/2005 |
英文摘要 | This thesis develops and investigates exact approaches to classical and practical capacitated lot sizing problems in petrochemical industries. The refinery provides a host of very challenging problems in production/procurement planning. Two typical production/procurement planning problems are investigated, which are single item capacitated lot sizing problems oriented refineries, and multi-item procurement planning problems in distributed supply chain with multi-suppliers, multi-refineries and multi-customs. Due to the characters in petrochemical products, the total demands are always more than production capacities. On the other side, even the total demands are less than production capacities, since the rule of meeting demands may lead to excessive inventory holding costs in some periods, it is cheaper to permit lost sales in order to get maximum profit. Furthermore, by analyzing the practical production/procurement planning on special cases in a refinery, the production capacity is high enough, but the reorder quantities are restricted by inventory capacity instead of production capacity. A single item dynamic lot size model with inventory capacity and lost sales is formulated. Subsequently, we extend a single item inventory capacity economic lot sizing model with lost sales to more general cost functions, which are concave functions. Stockout and conservation models are considered as well. Zero Inventory Order property cannot be used anymore here. Two strongly polynomial algorithms are developed based on some new properties, respectively. Some theoretical analyses for algorithms are performed. The computational results show that proposed approaches could get a satisfactory solution and has potential to practical production applications. Finally, by analyzing the crude oil procurement planning for distributed supply chain with multi-suppliers and multi-refineries, a purchasing problem originating from the purchase center as buyer’s point of view is described. The refineries outsource their crude oil procurement to purchase center for scale economies. A multi-objective procurement planning model is established, which not only minimizes supply chain cycle time, the total costs of earliness and tardiness penalties, production costs and transportation costs, but also considers quality and delivery on time. Through model transformation, the objective function can be solved by the general mathematical programming methods. The numerical computations demonstrates that the approach proposed is efficient and applicable, which can not only make effective procurement planning, minimize the cycle time of the supply chain,but also can choose the suppliers reasonably and optimize the configuration of resources. |
语种 | 中文 |
公开日期 | 2012-08-29 |
产权排序 | 1 |
分类号 | F27 |
源URL | [http://ir.sia.ac.cn/handle/173321/9571] ![]() |
专题 | 沈阳自动化研究所_工业信息学研究室_先进制造技术研究室 |
推荐引用方式 GB/T 7714 | 刘晓. 石化企业能力批量问题的模型与算法研究[D]. 中国科学院沈阳自动化研究所. 中国科学院沈阳自动化研究所. 2004. |
入库方式: OAI收割
来源:沈阳自动化研究所
浏览0
下载0
收藏0
其他版本
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。