组合优化在供应链管理中的应用

曲阜师范大学硕士学位论文组合优化在供应链管理中的应用姓名：高伟申请学位级别：硕士专业：数学、运筹学与控制论指导教师：张玉忠20090401组合优化在供应链管理中的应用作者：高伟学位授予单位：曲阜师范大学相似文献(10条)1.学位论文方秀丽供应链管理中的若干排序问题研究2008本文主要研究供应链管理中的若干排序问题,即工件可以进行外包加工的一种新的排序模型和带批处理的流水作业问题。全文共分为三章。第一章是绪论部分,介绍了组合优化和排序问题,算法的时间复杂性与近似算法等基本概念。第二章主要研究基于机器排序的工件外包问题,证明了这个问题等价于一个子集和问题,从而证明该问题也可以在O(nP)时间复杂性内加以解决,还提出了针对该问题的算法Aε和近似算法A1,并且证明了算法Aε是FPTAS。第三章主要研究带批处理的流水作业问题F2→D｜B,v=1,k=1｜Cmax,给出了F2→D｜B,v=1,k=1｜Cmax问题的混合整数规划模型,通过3-划分问题(3-PP),证明了F2→D｜B,v=1,k=1｜Cmax是强NP难的。在工件加工顺序给定的情况下,我们给出了该问题的启发式算法,证明了该算法最坏情况界是2,而且是紧界。2.学位论文方立华汽车行业配送组合优化与分布式库存管理的研究与实现2003销售配送和分布式库存管理是供应链中重要的一环.通过销售配送,企业将生产出的品转移到下属的分销网络.分布式库存管理主要研究在多仓库条件下,如何设置恰当的进货量和进货期、如何制订各库存点的出库数目和规划运输数量和运输路线,才能在满足各需求点需求的条件下,使得系统的物流成本降至最低.该文通过利用销售组织结构,对不适合充分利用运输车辆运能的配送计划进行了组合优化,并在分解组合过程中参考了运输车辆的前期表现等因素.分解组合的结果充分利用了运输车辆的运能,节约了运输成本,并在承运车辆的选择和运输任务的分配上体现了对运输车辆的奖惩.在分布式库存条件下,通过建立移拨模型并求解,确定了各个库存点到各个需求点的移拨数目.该移拨数目方案在考虑单车运费条件下移拨成本最低.通过建立路线优化模型并求解,对运输车辆的运输数目和运输路线进行了规划,降低了最终的运输成本.论文最后详细阐述了系统的设计及实现过程.3.学位论文仲维亚供应链管理中的若干排序问题研究2008排序问题是一类经典的组合优化问题,从上世纪50年代至今受到了许多行业的从业人员与理论研究者的密切关注。本文主要研究排序问题在供应链管理中的应用。众所周知,供应链是由多个环节构成的,因此我们不能孤立地研究排序问题,而要把排序问题与其它过程综合考虑。全文共分四章。第一章主要介绍了供应链与排序问题的一些知识和概念,并且总结了近些年来在综合考虑排序与运输的问题研究方面取得的一些成果。第二章研究工件占用运输工具空间不同的综合考虑运输和排序的问题。在这类问题中,工件在机器上完成加工后,需要由唯一的一辆运输工具运送到相应的顾客处。运输工具的空间是有限的,每个工件占用运输工具的空间各不相同。目标函数是极小化最后一个到达顾客的工件的到达时间。当机器环境是单台机,所有工件的顾客相同时,我们设计了最坏情况界为3/2+∈(∈是任意正常数)的渐近最优算法。当机器环境是两台平行机,所有工件的顾客相同时,我们给出了了最坏情况界为5/3的近似算法。第三章讨论了允许在两个加工工厂之间运送原材料或成品的排序问题。每个工厂可以加工所有属于本身的工件,也可以把一些工件运送到另一个工厂去加工。这样的运送需要一定的时间。若某个工厂需要另一家工厂加工一些工件,根据工厂和工件的不同要求,有以下三种情形：(1)在工件加工之前,原材料不需要运送,工件完成加工后,需要被运送回有需求的工厂；(2)在工件加工之前,需要先运送原材料,工件完成加工后不需要被送回有需求的工厂；(3)在工件加工之前,需要先运送原材料,工件完成加工后,需要被运送回有需求的工厂。问题的目标函数都是极小化最后一个完工工件的完工时间。对这三个问题,我们分别设计了最坏情况界为4/3,4/3和3/2的线性时间近似算法,并且给出了动态规划算法。第四章研究了带承诺到货时间的排序问题。在该问题中,企业根据顾客的订单来加工产品,并把完成的订单交由第三方物流公司运送给顾客。每个订单包含不同的产品数量,而且必须在顾客要求的时间之前送达。订单产生的运输费用与其中的产品数量以及运输需要的时间有关。我们的目标是安排一个加工订单的排序并为每个订单选择运输时间,使得所有订单都能在承诺的最迟到货时间之前到达其顾客处,并且产生的总运输费用尽量地少。我们给出了此问题的最坏情况界为2的近似算法,并且证明了这个界是紧的。4.学位论文王守震供应链管理模式下钻井企业采购管理研究2009新经济时代，企业之间的竞争由企业之间的竞争转变为各企业供应链之间的竞争，从计划经济走过来的钻井企业大多还没有完全认识到供应链管理思想对企业生存和发展的重要性，面对这种变化，没有及时采取行动，以适应新的挑战。石油钻井企业作为石油行业的上游企业，其成本直接影响着整个石油的价格。如何在供应链管理思想的指导下，对钻井企业的采购管理进行优化，并使这种管理思想深入到钻井企业生产、经营的各个环节，降低成本、提高市场响应速度，成为提高整个供应链竞争能力的关键所在。本文以供应链中的采购管理环节为研究对象，以供应链管理、采购管理及供应链管理环境下的采购管理理论为基础，分析和研究了石油钻井企业物资采购的现状、特点及其存在的问题，提出了在供应链管理模式下石油钻井企业物资采购的改进方案，重点运用由FAHP和模糊多指标群决策方法组成的组合优化多维决策模型来对钻井企业的相关供应商进行量化排序，为战略合作伙伴型供应商的选择提供了指标全面、科学合理、易于操作的评价方法，也为其它同类型企业在采购管理方面的运作提供了较好的借鉴和利用价值。本文内容主要由六章组成：第一章是前言，指出课题研究的意义、国内外研究现状及论文的技术路线；第二章对供应链、供应链管理及采购管理理论进行了概述，介绍了采购管理的发展趋势，进而探讨了供应链管理模式下的采购管理；第三章阐述了石油钻井的基本知识，介绍了钻井企业物资采购的现状，分析了我国钻井企业采购管理中存在的问题；第四章在供应链管理思想指导下，提出了我国石油钻井企业物资采购的改进策略；第五章则运用由FAHP和模糊多指标群决策方法组成的组合优化多维决策模型来对钻井企业的相关供应商进行量化排序，为战略合作伙伴型供应商的选择提供依据；第六章是结论，对整个论文进行了总结。5.学位论文王磊可控分批排序及供应链排序问题研究2008排序问题是一类重要的组合优化问题，有着深刻的实际背景和广阔的应用前景，它广泛应用于管理科学、计算机科学、工农业生产、交通运输等许多领域，已经取得了许多有意义的成果.分批排序和可控排序是两类很重要的现代排序模型，本文中把这两类排序模型相结合，讨论加工时间离散可控的单机分批排序问题.另外，对于近年来出现的将供应链管理和排序理论相结合的供应链排序问题，对于其中一个模型，考虑了平行机分批配送问题.论文共分三章：第一章首先介绍了排序问题的应用背景及问题描述，然后给出了必要的预备知识，最后概述了本文研究的主要问题及研究结果.第二章主要讨论加工时间离散可控的单机分批排序问题：分别考虑机器容量有限及无限两种情况下，分别使最大完工时间和总完工时间加上加工时间可控所需费用的总和为最小作为优化的目标，讨论了这四个问题的最优解的性质，并在此基础上提出了相应的多项式时间最优算法.第三章主要讨论平行机分批配送问题中的一个模型，首先指出该问题是强NP-hard的.如果工件满足一致性假设，本文给出了一个伪多项式时间的动态规划算法.最后，对于两种特殊情形给出了多项式时间最优算法.6.学位论文石磊基于大规模邻域搜索的车辆调度快速算法研究2007现代，企业为了提高竞争力，对供应链管理提出了更高的要求，如何高效率地完成从原材料采购，产品生产到产品配送，已成为各公司研究的重点。现代物流系统作为供应链的重要环节，主要包括运输、存储、包装、装卸和搬运等若干相互依赖、相互制约的子系统，其中物流配送是一个与消费者相连的重要环节。本文主要研究了一类车辆优化调度问题――PDPTW问题（PickupandDeliveryProblemwithTimeWindows，带时间窗口的装卸货问题）及其扩展问题的优化调度算法。有时间窗口的装卸货问题（PDPTW）是一个典型的NP-hard问题，因此成为运筹学与组合优化领域的研究的难点与热点。本文主要在两方面对PDPTW问题开展研究，首先，针对静态的PDPTW问题，相关文献中介绍的一些优化算法在计算时间和解的质量方面缺乏良好的平衡，如文献[15]提到的自适应方法，虽然能得到很好的解，但计算时间过长，难以满足实时性要求。本文通过合理平衡计算时间和解质量，提出了一种快速LNS（LargeNeighborhoodSearch,大规模邻域搜索）算法，这种方法具有求解速度快、求解质量好、对初始解的依赖性小的特点。在保持快速求解的前提下，利用模拟退火在全局寻优中的优势，进一步提出了类模拟的快速LNS算法，改进了单一采用LNS算法的不足。其次，本文结合实际应用时车辆在行驶过程中可能损坏的情况研究了动态PDPTW问题，给出了求解策略。本文的研究工作和成果如下：1．分析了PDPTW问题的标准算例，对已有的相关算法进行了测试，理解其优缺点，为寻求和改进算法打下基础。2．提出了改进的LNS算法，在保持解质量的情况下，缩短了求解过程。求解过程主要以减少车辆为目标，通过优先选出短路径中的客户和与之有较大相关性的客户，来调整邻域搜索方向，使之能快速收敛到一个较优的解上，然后加入随机扰动，充分利用LNS算法本身邻域空间较大的优势，寻找在其它空间内更优的解。3．对比了采用上述改进LNS算法所得到的解与其他相关文献所得到的解的质量，分析了影响解质量的因素，提出了类模拟退火的LNS算法，该算法在保持了改进LNS算法快速性的前提下，利用模拟退火在全局寻优能力上的优点，进一步改进原有解的质量，对不同算例的仿真结果表明，该算法对提高随机分布算例的解的质量，具有极大的优势，并且减小了对于初始解的依赖性。4．参考当前车辆调度领域文献中对动态车辆调度问题的研究，对动态PDPTW问题进行讨论，结合实际执行调度过程中车辆可能损坏的情况，给出解决此类问题的策略，在尽量不新增车辆（即使新增车辆，可能到达事故点取货后，仍然会延期交货）的前提下，依靠剩下的车辆来完成所有客户需求，问题的目标定义为最小化客户不满意度，其中客户不满意度包括延迟客户的总数目和所有客户的延迟时间和。5．通过大量仿真测试，给出了静态PDPTW的问题算法解质量的分析，对比不同算法，不同初始解对问题求解的影响，并通过加入动态PDPTW的概念，分析各个算法的解结构对抗突发事件的鲁棒性。本文的研究工作得到了上海市科技发展基金的支持。7.期刊论文陈雷雷.冯定忠.山城光雄.CHENLei-lei.FENGDing-zhong.MITSOUYamashiro基于分层模糊综合评价的供应商组合优化选择-浙江工业大学学报2005,33(6)供应商选择是供应链管理中的一个重要环节.随着信息技术的发展和经济的全球化,对供应商的选择已突破了地域和距离的限制,因而,所要处理的信息变得更多,选择的难度也变得更大.根据供应商选择的特点,首先就供应商的工艺能力和生产能力对相关信息进行有效的过滤,然后,结合模糊数学理论提出了一个分层模糊综合评价模型,进而分析与探讨了供应商与外购零部件间不同组合的优化选择问题,提出了逐步简化的解决办法,最后给出了一个数值例子来例证该方法的实际应用.8.学位论文成飙两种随机优化算法的改进及其化工应用研究2007在过去的30年中,能源价格持续增长,环境控制日益严格,产品竞争趋于全球化,面对这些压力,优化技术是企业降低成本提高效益的一个有效技术.从产品设计到供应链管理,优化技术可以应用于化工过程的每一个层次.然而物质能量转化过程内在的非线性、以及装置操作中的离散性使得化