面向入厂物流空箱约束具有可重复利用资源的调度模型与优化算法研究

入厂物流是企业实现准时制生产的重要环节；空箱约束是影响入厂物流效率的关键因素。通过深入分析入厂物流空箱约束的实际运作流程,本项目提出研究一类新的具有可重复利用资源的调度问题，特点在于服务能力的动态性与次序依赖性。在对该调度系统进行系统描述基础上，研究调度及数学规划模型的建模方法。进一步，基于物流与供应链、调度、组合优化与计算复杂性理论，从建立集成调度模型与设计高效优化算法的角度出发，通过分析问题的最优解特征,提炼其数学特征量.分析问题的计算难解性,并设计精确及启发式算法,从理论及数值上研究模型及算法性能。通过合作企业进行实证研究，提出高效鲁棒的系统解决方案。研究内容属于物流与供应链管理的应用基础研究，研究方法具有可行性和探索性，研究成果有较强的理论价值。项目完成对促进管理科学、工业工程及物流工程发展有一定科学意义。项目源于生产实践，研究成果对指导物流实践，促进物流应用技术发展有现实意义。

本项目以第三方入厂零部件物流配送系统为研究背景，面向入厂物流空箱资源这一核心约束，在国际上首次提出了具有可重复资源的动态服务调度问题类，就系统建模、问题描述及计算复杂性，数学建模与优化算法等方面展开研究。. 在系统研究上，通过对物流企业实际运作系统的调研分析，给出标准入厂物流空箱运作系统流程，并对系统决策目标要素、环境要素、约束要素以及运输环境等方面展开分析，为提出真正科学而合理的理论问题奠定应用基础。研究指出两类主要目标，一类是最小化最晚完工时间，以实现运输车辆工作负荷均衡以及减少工作时间负荷；另一类是最小化全部完工时间，以实现在途库存的减少提高物流服务的准时性。研究还表明空箱总量固定的约束是导致动态服务能力重要诱因。研究还对入厂物流的直运与循环取料运输模式进行系统的论述。. 本项目提出了两大类科学问题。其一是直运环境下的可重复资源动态服务调度类，其二是循环取料下的可重复资源动态服务调度问题类。这两类调度问题是调度理论研究的重要补充，对指导诸如服务资源固定的资源管理优化，如医院管的手术室管理，具有较强普适性（可推广）价值。研究明确指出问题类的两大特征，即时间空闲特征及装箱特征。这两大特征部分突破传统的调度思维，对形成新的调度理论思想具有较强的思想意义。基于计算复杂性理论，对问题类的子问题分别展开复杂性研究，证明相关问题的计算难解性（NP-难）以及多项式可解性，最终绘制了两大问题类的计算复杂性谱系。建立描述该问题类的混合整数线性规划模型，并采用Ilog Cplex等优化工具验证所建立模型的有效性及高效性。. 在算法研究部分，提出基本装箱特征的装箱类调度规则与基于时间空闲特征的纵横规则。将调度决策分为解为订单排序与订单指派过程。受到经典SPT规则以及背包问题规则的启发，提出了单位资源占用时间最短（RSPT）准则。数值实验表明所提出算法的高效性，最好的启发式算法的误差为6%。项目还进一步对求解大规模问题的线性规划松弛算法与分支定界等精确算法展开研究，并对閥值等参数进行分析。. 项目的研究结论属于物流与供应链管理的应用基础研究成果，研究方法具有可行性和探索性，项目的完成对促进管理科学、工业工程及物流工程发展有一定科学意义。项目源于生产实践，研究成果对指导物流实践，促进物流应用技术发展有较强的实践意义。