序列依赖的可重用资源约束调度的列生成算法的研究

《序列依赖的可重用资源约束调度的列生成算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、上海交通大学硕士学位论文序列依赖的可重用资源约束调度的列生成算法研究摘要汽车制造业零部件入厂物流使用专门料箱进行运输。料箱是可重复利用的瓶颈资源，其安排调度不合理，会造成装载率下降与运输时间长等问题。因此，如何有效地利用数量有限的空箱资源，制定高效的运输调度方案，是汽车入厂物流运作与管理的重要问题。本文研究序列依赖的可重用资源调度问题。首先对该问题进行数学描述，建立混合整数线性规划模型。鉴于问题的NP难解性，本文研究求解该问题的列生成方法，提出虚工件等技巧，建立适合序列依赖的可重用资源约束调度的列生成主问题模型以及基于检验数求解的子问题模型，并研究求解子问题的动态规划

2、算法。进一步采用分支定界技巧，最终提出适合本问题求解的列生成算法。数值实验表明方法的有效性与高效性。本文提出的算法思想，对列生成算法自身的发展具有一定的理论意义，也将为汽车零部件入厂物流空箱约束优化的实践提供借鉴。关键词：资源约束，可重用资源，列生成，动态规划，分支定界I万方数据上海交通大学硕士学位论文ColumnGenerationMethodforSchedulingProblemwithRenewableResourcesABSTRACTAutomotiveinboundlogisticsusespecialcontainersfortransportation

3、.Containersarelimitedrenewableresources,andtheinsufficiencyofthemwouldleadtolowloadingrateandextendstransportationtime.Therefore,howtoutilizethesekeyresourceseffectivelyisofgreatimportanceforthemanagementandoperationofautomotiveinboundlogistics.Thispaperstudiescolumngenerationmethodfors

4、chedulingproblemwithrenewableresources.Firstweshowhowamixedintegerlinearprogrammingmodelcanbeusedtodescribetheproblem.AstheproblemisNPhard,weproposecolumngenerationmethodtosolvetheproblem.Duringtheprocess,conceptsofvirtualpartsareintroduced.Setpartitioningmodelissetupforthemasterproblem

5、andthemodelforthesubproblemisbuiltbasedontestnumbersolving.Moreover,weproposetousedynamicmethodtosolvethesubproblemandstudyBranchandBoundtechnique.Finally,weproposethewholecolumngenerationmethodthatsuitforsolvingthisproblemandverifytheeffectivenessofproposedalgorithmbythenumericalexperi

6、ments.Thealgorithmofthispaperhasstrongtheoreticalvalueforcolumngenerationmethod,anditcontributestothethird-partylogisticscompaniesinimprovingoperationalefficiencyofinboundpartsdistributionsystem.KEYWORDS:Resourceconstrained,Renewableresource,Columngeneration,Dynamicprogramming,Branchand

7、BoundII万方数据上海交通大学硕士学位论文目录第一章绪论............................................................11.1研究背景...............................................................................................................11.2研究意义.............................................................