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

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