供应链调度理论、模型与算法研究

华中科技大学硕士学位论文供应链调度理论、模型与算法研究姓名：周峰申请学位级别：硕士专业：工业工程指导教师：高亮20080531华中科技大学硕士学位论文I摘要近五年来，供应链调度已经成为供应链管理的研究热点之一。供应链调度研究供应链成员（包括供应商、生产商、分销商和第三方物流公司等）之间的联合（或协同）调度问题。通过供应链中各成员之间的信息共享与协作，建立联合的调度方案，可以缩短产品交货期，提高客户服务水平，同时也可以降低整条供应链的运作成本。首先，系统阐述了供应链调度的基础理论，包括供应链协同理论和生产调度理论，分析并总结了各理论之间的关系。其次，研究了基于单机调度的供应链调度问题，分别建立了单目标和多目标的优化模型，并运用动态规划和调度规则设计了多项式时间的精确算法，通过计算实例验证了算法的有效性。接着，研究了基于平行机调度的供应链调度问题，建立了多目标的优化模型，并运用动态规划和调度规则设计了多项式时间的启发式算法，通过计算实例验证了算法的有效性。昀后，研究了基于两台机器流水车间调度的供应链调度问题，建立了多目标的优化模型，并运用动态规划和调度规则设计了多项式时间的精确算法，通过计算实例验证了算法的有效性。关键词：供应链调度供应链协同生产调度精确算法启发式算法华中科技大学硕士学位论文IIAbstractDuringtherecentfiveyears,SupplyChainScheduling(SCS)hasbecomeoneofthehotproblemsinSupplyChainManagement(SCM).SCSstudiesjointlyorcoordinatedschedulingproblemsthroughsupplychainthatincludessuppliers,manufacturer,distributorsandthirdpartylogistics.Byinformationsharingandcooperationamongmembersinsupplychain,jointschedulingmodelsofthewholesystemaredeveloped,whichnotonlyshortentheleadtime,improvecustomerservicelevel,butalsolowertheoperationscostoftheentiresupplychain.First,fundamentaltheoriesaboutSCSarecompletelypresented,whichincludesupplychaincoordinationandproductionscheduling.Therelationshipbetweenthesetheoriesarealsoanalyzedandsummarized.Second,singlemachineschedulingbasedSCSmodelsarestudied.Single-objectiveandmulti-objectiveoptimizationmodelsaredevelopedrespectively.Polynomialtimeexactalgorithmsaredesignedbydynamicprogramminganddispatchingrulesandthenaretestedbycasestudy.Third,parallelmachineschedulingbasedSCSmodelsarestudied.Multi-objectiveoptimizationmodelsaredeveloped.Polynomialtimeheuristicalgorithmsaredesignedbydynamicprogramminganddispatchingrulesandthenaretestedbycasestudy.Last,two-machineflowshopschedulingbasedSCSmodelsarestudied.Multi-objectiveoptimizationmodelsaredeveloped.Polynomialtimeexactalgorithmsaredesignedbydynamicprogramminganddispatchingrulesandthenaretestedbycasestudy.Keywords:SupplyChainScheduling,SupplyChainCoordination,ProductionScheduling,ExactAlgorithms,HeuristicAlgorithms独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其它个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本论文属于（请在以上方框内打“√”）学位论文作者签名：指导教师签名：日期：年月日日期：年月日保密□，在年解密后适用本授权书。不保密□。华中科技大学硕士学位论文11绪论本章首先介绍了课题的来源、背景、目的与意义。然后，概括了供应链调度国内外的研究现状。昀后，阐述了本文所做的主要工作，并给出了本文的结构。1.1课题概述1.1.1课题来源（1）863项目“基于复杂性科学的车间动态调度理论与方法研究”，项目编号：2006AA04Z131。（2）863/CIMS项目“复杂制造系统中与工艺规划集成的车间调度”，项目编号：2007AA04Z107。1.1.2课题背景供应链调度是在制造业和服务业步入二十一世纪后，订单加工（MaketoOrder,MTO）、零库存、第三方物流（ThirdPartyLogistics,TPL）和电子商务（ElectronicBusiness）的盛行的大背景下产生的。在传统的大规模生产方式中，企业根据市场预测安排生产，采用的生产战略为备货生产型（MaketoStock,MTS），生产不由客户驱动，其作业计划易于实施。而在大规模定制生产中，企业根据订单安排生产，其生产战略为MTO，面临的昀大挑战是成本和交货期。如何对客户的定制需要制定出合适的作业调度计划，及时对客户需求做出反应、提供较低成本定制化的产品是大规模定制企业必须解决的关键问题。在大规模定制生产的企业中，戴尔电脑可谓遥遥领先，以至于它的生产、经营方式被称为“戴尔模式”。从戴尔订货，客户无论是通过网络还是电话发出指令，不到一分钟，信息就会出现在控制中心的电脑里。控制中心再通过网络迅速通知供应商供货，同时也把用户要求的配置信息输入装配程序。配件的运输、需求的数量、规格、型号和装配全都按照控制系统的安排精确运行，前一道工序与后一道工序严丝合缝。戴尔模式的精髓就是“效率第一”。华中科技大学硕士学位论文21.1.3课题目的与意义在当今经济全球化的浪潮下，国内企业面临着日益激烈的市场竞争。竞争的舞台从国内延伸至国外。这种竞争不仅是企业与企业之间的竞争，也是供应链与供应链之间的竞争。高效率、低成本运作是企业及其供应链赢得这场竞争的有力保证。生产和分销是供应链中昀重要的两个环节。企业及其供应链的高效率、低成本运作与这两个环节密切相关。生产和分销环节的优化，存在两种方法：连续（顺序）的优化和集成（联合）的优化。连续（顺序）的优化是指先优化生产环节，再优化分销环节。前面生产环节优化的结果作为后面分销环节优化的初始条件。这种连续（顺序）的优化方法被当今国内企业普遍使用。集成（联合）的优化是指通过建立统一的生产——分销模型，同时的优化生产和分销两个环节。显而易见的是，采用连续（顺序）的优化方法尽管可以使生产和分销达到各自的昀优，但往往不是整体（供应链）的昀优。供应链调度(SupplyChainScheduling，SCS)是在供应链的运作层次上研究企业生产和分销集成的重要问题。它通过建立统一的联合的生产——分销调度模型来寻找可以使整条供应链效益昀优的调度方案。供应链调度可以给供应链及其成员企业带来可观的经济效益，这主要表现在显著的降低运作成本和提高客户服务水平两个方面。尤其是采用MTO和直销模式的企业，因其生产和分销之间没有库存而使两者的联系更为紧密，给实施供应链调度创造了昀理想的条件。1.2供应链调度研究概况1.2.1供应链调度的定义已有的供应链调度文献没有对供应链调度这个概念进行正式的定义。供应链调度作为一个专业名词，在昀近五年的供应链管理的文献中频频出现，有必要对它进行一个科学的定义。个人认为，供应链调度是供应链的成员们，包括供应商、生产商、分销商和第三方物流等，在信息共享的基础上，为了达到缩短产品交货期，降低整条供应链运作成本的目标，实行联合（或协同）的调度。供应链调度与传统生产调度的区别在于：供应链调度研究的是供应链成员之间联合（或协同）的调度，包括了原材料的采购、产品的加工生产以及完工产品的运输和分销过程。而生产调度只关注产品的加工生产这一环节。华中科技大学硕士学位论文31.2.2国外研究现状概述国外供应链调度的研究始于2003年Hall和Potts在OperationsResearch上发表的“Supplychainscheduling:batchinganddelivery”一文。他们在文章中指出[1]，尽管在过去的十年间对应供应链管理的研究已经非常多，但对于供应链运作层次的调度模型的研究却非常少，特别是忽视了供应链成员企业之间的协同调度所带来的效益。这篇供应链调度领域的开创性文献，打破了以往供应链管理研究中只注重战略层次的协同，而忽视运作层次（尤其是调度层次）的协同的现象，对供应链协同管理影响巨大。供应链调度研究的基础，是建立在过去对供应链生产、分销系统研究的基础上的。关于供应链生产、分销系统的研究成果，可参见Vidal和Goetschalckx[2]，Sarmiento和Nagi[3]的文章。2000年以后的研究进展可查阅Jayaraman和Pirkul[4]，Dasci和Verter[5]，Shen等人[6]的论文。正如Chen指出[7]，绝大部分研究供应链生产、分销系统的文献都是从战略或战术的层次考虑决策问题，几乎没有从具体运作层次或是调度层次来考虑。Cohen和Lee[8]提出了一个通用的模型框架将供应链中生产、分销系统的表现和决策联系起来。这个模型建立的目的是为了分析所有可行的生产和服务战略。Chandra和Fisher[9]研究了协同的生产、分销计划的价值。通过计算实验，他们指出，通过生产和分销的协同计划，供应链运作总成本可降低3%-20%。这一研究成果为企业实施机构重组和供应链企业协同提供了必要的实验基础。Fumero和Vercellis[10]提出了一个生产、分销计划的集成优化模型，目的是为了解决物流协同的决策问题，诸如产能管理（CapacityManagement）、库存分配（InventoryAllocation）和车辆路径（VehicleRouting）。Lei等人[11]研究了一个协同的生产、库存和分销运作问题，在满足客户需求的前提下要求总成本昀小。为了解决这一问题，他们提出了一个两阶段的方法。在上面的模型中，库存成本在供应链运作的总成本中占很大一部分。而且生产和分销过程由于库存的间隔，联系并不是很紧密。下面简要回顾下研究供应链生产、分销系统中联合的调度问题的相关文献，这跟本文研究的供应链调度有着密切的联系。Potts[12]，Hall和S