供应链管理中的若干排序问题研究

浙江大学理学院硕士学位论文供应链管理中的若干排序问题研究姓名：方秀丽申请学位级别：硕士专业：运筹学与控制论指导教师：谈之奕20080601供应链管理中的若干排序问题研究作者：方秀丽学位授予单位：浙江大学理学院相似文献(10条)1.学位论文仲维亚供应链管理中的若干排序问题研究2008排序问题是一类经典的组合优化问题,从上世纪50年代至今受到了许多行业的从业人员与理论研究者的密切关注。本文主要研究排序问题在供应链管理中的应用。众所周知,供应链是由多个环节构成的,因此我们不能孤立地研究排序问题,而要把排序问题与其它过程综合考虑。全文共分四章。第一章主要介绍了供应链与排序问题的一些知识和概念,并且总结了近些年来在综合考虑排序与运输的问题研究方面取得的一些成果。第二章研究工件占用运输工具空间不同的综合考虑运输和排序的问题。在这类问题中,工件在机器上完成加工后,需要由唯一的一辆运输工具运送到相应的顾客处。运输工具的空间是有限的,每个工件占用运输工具的空间各不相同。目标函数是极小化最后一个到达顾客的工件的到达时间。当机器环境是单台机,所有工件的顾客相同时,我们设计了最坏情况界为3/2+∈(∈是任意正常数)的渐近最优算法。当机器环境是两台平行机,所有工件的顾客相同时,我们给出了了最坏情况界为5/3的近似算法。第三章讨论了允许在两个加工工厂之间运送原材料或成品的排序问题。每个工厂可以加工所有属于本身的工件,也可以把一些工件运送到另一个工厂去加工。这样的运送需要一定的时间。若某个工厂需要另一家工厂加工一些工件,根据工厂和工件的不同要求,有以下三种情形：(1)在工件加工之前,原材料不需要运送,工件完成加工后,需要被运送回有需求的工厂；(2)在工件加工之前,需要先运送原材料,工件完成加工后不需要被送回有需求的工厂；(3)在工件加工之前,需要先运送原材料,工件完成加工后,需要被运送回有需求的工厂。问题的目标函数都是极小化最后一个完工工件的完工时间。对这三个问题,我们分别设计了最坏情况界为4/3,4/3和3/2的线性时间近似算法,并且给出了动态规划算法。第四章研究了带承诺到货时间的排序问题。在该问题中,企业根据顾客的订单来加工产品,并把完成的订单交由第三方物流公司运送给顾客。每个订单包含不同的产品数量,而且必须在顾客要求的时间之前送达。订单产生的运输费用与其中的产品数量以及运输需要的时间有关。我们的目标是安排一个加工订单的排序并为每个订单选择运输时间,使得所有订单都能在承诺的最迟到货时间之前到达其顾客处,并且产生的总运输费用尽量地少。我们给出了此问题的最坏情况界为2的近似算法,并且证明了这个界是紧的。2.期刊论文袁晖.YUANHui供应链排序问题模式研究-物流科技2007,30(3)供应链协同是供应链管理中的重要问题,供应链上不同阶段的决策者应当如何安排产品的生产、配送顺序,近年来有研究将经典生产排序理论引入供应链管理中,针对上述协同问题提出供应链排序研究模型,但还没有形成统一的框架和定义,本文将介绍这一领域的研究现状和发展前景.3.期刊论文柏孟卓.陈峰.唐国春.BAIMeng-zhuo.CHENFeng.TANGGuo-chun供应链管理中生产和运输集成的排序问题-工业工程与管理2007,12(5)分析了供应链管理中多制造商、多客户的生产和运输集成起来的排序(调度)问题.建立了集成排序模型,在研究解的最优性条件基础上,用工件的总流程时间作为排序目标,解决使总费用达到最小的问題,给出相应的动态规划算法,并分析算法的复杂性.4.学位论文王磊可控分批排序及供应链排序问题研究2008排序问题是一类重要的组合优化问题，有着深刻的实际背景和广阔的应用前景，它广泛应用于管理科学、计算机科学、工农业生产、交通运输等许多领域，已经取得了许多有意义的成果.分批排序和可控排序是两类很重要的现代排序模型，本文中把这两类排序模型相结合，讨论加工时间离散可控的单机分批排序问题.另外，对于近年来出现的将供应链管理和排序理论相结合的供应链排序问题，对于其中一个模型，考虑了平行机分批配送问题.论文共分三章：第一章首先介绍了排序问题的应用背景及问题描述，然后给出了必要的预备知识，最后概述了本文研究的主要问题及研究结果.第二章主要讨论加工时间离散可控的单机分批排序问题：分别考虑机器容量有限及无限两种情况下，分别使最大完工时间和总完工时间加上加工时间可控所需费用的总和为最小作为优化的目标，讨论了这四个问题的最优解的性质，并在此基础上提出了相应的多项式时间最优算法.第三章主要讨论平行机分批配送问题中的一个模型，首先指出该问题是强NP-hard的.如果工件满足一致性假设，本文给出了一个伪多项式时间的动态规划算法.最后，对于两种特殊情形给出了多项式时间最优算法.5.期刊论文胡一竑.蓝孝全.HUYi-hong.LANXiao-quan在阶跃式定购成本函数和运输能力限制下的运输船只排序问题-中国管理科学2004,12(z1)本文考虑短时期内,满足确定需求,不能缺货,有运输能力限制,且定购成本函数为阶跃型的运输船只排序问题,分析了最优解性质,并据此提出了相应的算法,算法复杂度为O(T3),并给出了算法的应用实例.最后,指出了未来研究的方向.6.学位论文赵珣供应链管理中的分批配送及经济批量问题2008近年来，供应链管理作为一种管理理念在国内外逐渐受到重视.由于运筹学、数理统计等理论与方法的广泛应用，越来越多的学者将运筹学的方法运用到供应链管理中，将实际问题归结为数学问题，通过建立数学模型来解决供应链管理中的问题.本文首先研究了把排序问题与供应链管理中的配送问题相结合的模型，目标是极小化加权配送时间和运输费用的和.然后研究了库存管理中的经济批量问题.论文共分三章来叙述.第一章主要概述了排序的由来、发展和一些相关知识，经济批量问题的定义和研究状况.简单介绍了本文的主要研究成果.第二章讨论的是工件带到达时间的排序及分批配送问题，目标函数为极小化加权配送时间与运输费用的和，这里的配送时间是指工件的完工时间和运输时间的总和.在工件带常数个到达时间的模型中，对两种特殊情况进行了分析，对权重一致的情况给出了动态规划算法，不分批的情况给出最优算法，对其一般情况给出了近似比为B的多项式时间算法，并给出了算法复杂性.第三章研究了两个环节即包含了仓库和分销中心的ELS模型，在从仓库到分销中心的两种出货运输模式都为整车运输的情形下，极小化仓库的进货费、从仓库到分销中心的出货费与仓库和分销中心的库存费的和，对于一个运输工具的容量是另一个容量的整数倍的情形分析了最优解的性质，给出了复杂性为=}(p)的动态规划算法，其中T表示计划展望期的阶段数.7.会议论文胡一竑.蓝孝全在阶跃式定购成本函数和运输能力限制下的运输船只排序问题本文考虑短时期内,满足确定需求,不能缺货,有运输能力限制,且定购成本函数为阶跃型的运输船只排序问题,分析了最优解性质,并据此提出了相应的算法,算法复杂度为O(T3),并给出了算法的应用实例。8.学位论文熊峰供应链协同调度研究2009面对全球化的浪潮和越来越激烈的市场竞争，供应链之间的竞争压力越来越大。如何快速响应不确定性的市场需求，在降低制造和配送成本、缩短产品生产和配送时间的情况下，实现高效的供应链协同制造，成为当前供应链管理者面临的非常具有挑战性的重要课题。通过研究，管理者和研究人员认识到，必须对产品在供应链内的生产制造以及分销领域内的全过程进行协同优化，寻找从供应链整体的角度对供应链内资源进行优化控制的方法，对于提高供应链生产效率，从而提升供应链竞争力，充分发挥供应链制造生产模式的优越性，具有非常重要的意义。因此对供应链协同调度进行研究有着广泛的现实背景和重要的理论意义与学术价值。本文在对国内外供应链优化和供应链协同调度领域罩的研究方法和手段进行了总结和归纳的基础上，运用定量方法研究了供应链协同调度模型和求解方法，阐述了供应链协同调度的建模及优化的思路，并针对几个典型问题进行了建模并给出了具体的算例以及算法。论文的主要创新工作包括：（1）整合了供应链内多阶段调度模式。本文考虑了生产与分销多个环节集成模式下的整体最优安排，将供应链生产的综合成本和时间作为优化的目标，并建立了相应的多目标决策优化调度模型（SCISM模型），在此基础上，考虑缺货成本下的供应链成本增加的情况，建立了一个缺货成本下的二次规划优化调度模型。最后考虑了集成调度下的一个两阶段的生产和配送环节下的集成调度模型（OADSIM模型）。（2）针对线性和非线性的调度优化模型，运用旋转算法进行求解，旋转算法比较适合相对较大规模问题的计算，通过求解多目标线性规划和二次规划调度模型的算例，计算效果非常理想，均在较短时间内找到最优解。（3）把分组嵌套的遗传算法运用到大型供应链集成调度问题的求解中来。在实际中，由于供应链集成环境下，考虑生产厂家和配送过程的集成优化，既是一个指派问题，又具有排序问题的特征，这给模型的求解带来非常大的计算难度，这里给出了一种嵌套的遗传算法，在此基础上找寻集成调度问题的最优调度方案。（4）提出了基于多智能体的WEB集成调度系统框架。考虑供应链集成环境下基于多智能体的制造子系统和供应网络子系统的功能框架，结合实际需求，提出了基于Token的竞标型协商机制。该机制能够实现成员内基于整体资源调度的协商的快速实现。9.会议论文柏孟卓.唐国春平行机加工与分批发送的集成排序问题2006本文研究一个供应商为多个制造商供货的供应链管理中供应商对工件(原料)进行加工,并分批发送给下游制造商的集成排序问题.供应商有m台平行机可以同时进行加工,以工件的总流程时间作为生产排序费用,集成排序问题的目标是使生产排序费用加上分批发送费用的总和为最小.对这个问题建立模型,证明是强-NP难问题,给出建立在动态规划基础上的多项式时间的近似算法,并证明近似算法的界是2-1/m.此外,还考虑生产排序费用与交货期有关的两个集成排序问题的NP-难解性.10.学位论文刘道良基于排序理论的生产和运输集成调度研究2009生产和运输配送是供应链管理的两个重要环节，要使供应链获得好的运作绩效，生产和运输这两个环节必须进行协调运作。在过去的20年里，已经有大量的文献讨论了这种协调、集成性，不过研究的着眼点都是在战略层和战术层上，对于运作层面上的研究还是比较少，而现代管理讲究的是一种精细化管理，运作层面上的这种研究也非常重要。本文将传统的生产调度即排序问题引入到供应链管理中，与运输调度的车辆路径调度结合在一起，在供应链管理运作层面上来研究生产和运输的集成调度问题。该问题就是有一系列的客户订单，订单先在工厂里加工，加工完成后由车辆运送到各自客户，目标是找到一个最优的生产排程和车辆调度解让客户服务水平和运输成本达到最优。客户服务水平是订单到达客户的时间函数，运输成本由固定成本和可变成本组成。本文的主要研究内容有：首先，研究了运输资源无约束下的生产和运输集成调度问题。针对该问题，改进了两个模型，即单机单客户和单机多客户的生产和运输集成调度模型，对这两个模型都给出了基于动态规划的求解方法，并都给出了时间复杂度分析。其次，研究了运输资源有限情形下的生产和运输集成调度问题。针对该问题，改进了两种模型：即单客户单车辆和单客户多车辆的生产和运输集成调度模型，对两个模型本章都给出了基于动态规划的求解方法，并都给出了时间复杂度分析。最后，通过对生产和运输的集成调度与独立调度的比较，来研究生产和运输集成调度的优越性。针对第三章、第四章提到的四个模型用独立调度的方法进行了求解，并将得到的结果与集成调度得到的结果进行比较，通过比较可以验证集成调度的优越性。最后对这种优越性进行了仿真实验，通过大量的数据仿真可以得出随着权重α值、客户数量g、车辆容量c的增大，这种集成调度的优越性更加明显的结论。关键词：生产和运输集成调度动态规划集成调度价值本文链接：：上海海事大学(wflshyxy)，授权号：0