机器调度问题和二维向量装箱问题的精确算法研究

发布时间：2020-04-10 03:55

【摘要】：随着经济全球化的发展,企业之间的竞争越发激烈。在能源储备不足日益凸显的今天,高效分配和使用稀缺资源的技术优势无疑是企业的核心竞争力之一。生产调度问题是制造企业在日常运作中面临的主要问题,单一机器是制造产业的基本生产单元,在机械科技水平的限制和购入机器投入资金的限制下,如何通过排序和统筹调度方面的技术去提高机器产能是企业首要解决的问题。打包装箱方法是影响物流运输的一个关键技术,跟物流运输的自动化水平、装载效率和业务流程的规范都有着重要的关系。因此,本文针对生产调度和打包装箱问题展开研究,基于列生成的思想为问题设计有效的精确算法。首先,基于制造企业实际的生产场景,我们提出了一个考虑柔性周期维护和恶化效应的单机调度问题,并设计了有效的分支定价精确算法。通过推导问题最优解中所使用批次数目的上界,我们提出了该问题的混合整数规划模型,并将此模型通过Dantzig-Wolfe分解得到集合划分问题的整数规划模型。由于集合划分问题所对应的定价问题是带有资源约束的最短路问题,我们设计了高效的标签设定算法来求解此问题。在标签设定算法中,为了加速标签的搜索过程,我们针对定价问题的特性和结构设计了标签支配规则。同时,考虑到最优解的特性,我们还提出了一个能够有效减少集合划分模型中变量数目的批次支配规则。限制性主问题的线性松弛求得的最优解有可能不是整数。为了得到问题的最优整数解,我们为精确算法设计了两种分支策略:对批次的数目进行分支和对最短路中的前向弧进行分支。在分支定界树中,全局上界的更新是通过构造式的启发式算法来实现的。在计算实验中,我们结合相关文献随机生成了 1440个算例,用来验证算法的求解性能。通过对分支定价算法的多个子模块进行对比实验和分析,实验结果表明我们所设计的分支定价算法是高效的。我们还给出了该问题在线版本下的一个最优策略。其次,我们以一个物流运输行业实际的打包装箱收费问题为背景,提出了一个与体积重量相关的一般价格函数的二维向量装箱问题。我们在论文中介绍了知名物流企业对包裹的标准收费流程,据我们所知,这是第一篇考虑体积重量的装箱问题的论文。由于价格函数的原因,我们所考虑的问题要比经典的二维向量装箱问题复杂很多。为了求解这一问题,我们在分支定价算法的基础上往限制性主问题里面加入两种有效不等式,因此我们所设计的算法是一个分支定价切割精确算法。用于加速全局下界的提升速度和减少结点的求解个数的两种有效不等式分别为:取整不等式和Subset-row不等式。因为Subset-row不等式会改变定价问题的结构使得定价问题的复杂性增加,我们仅在根结点添加Subset-row不等式。为了求解定价问题,我们设计了标签设定算法,同时推导出了考虑Subset-row不等式下的标签支配规则。为了求得问题的最优整数解,我们采用了两种分支策略:对使用的箱子的数目进行分支和对成对的物品进行分支。我们基于一种最短路解码算法来更新分支定界树中每个结点的上界。我们随机生成了 360个算例来测试我们所设计算法的性能。我们将原问题的混合整数规划模型带入CPLEX求解器求解,所得到的结果与分支定价切割算法的实验结果进行了比较,结果显示我们的算法远比CPLEX求解高效。另外,我们还对算法的几个关键子模块做了测评实验和分析。最后,我们为一个抗癌静脉注射针剂的运输存储问题设计了一个分支定价切割精确算法。此问题实际上是一个不确定尺寸的二维向量装箱问题,我们将存储抗癌静脉注射针剂的容器看成是具有体积维度和加工时长维度的箱子,那么在体积维度上箱子的体积是确定的,但是在加工时长这一维度上箱子的大小是不确定的。在加工时长维度上,我们只需考虑的问题是针剂的延迟时长不超过给定的时间限制即可。为了减少求解分支定界树中结点的数目,我们在限制性主问题里面添加了取整不等式。为了求解定价问题,我们设计了标签设定算法和标签支配规则。另外,我们还设计了对定价问题中的前向弧进行分支的分支策略。通过随机生成420个算例来测试我们算法的性能。我们用CPLEX求解器来求解原问题的0,1整数规划模型,将得到的结果与分支定价切割算法的实验结果进行比较,结果显示我们的算法远比CPLEX求解高效。另外,我们还对加入取整不等式的BPC算法与不加取整不等式的BP算法做了比较实验,实验结果显示取整不等式能够极大地提升我们算法的性能。
【图文】：

技术路线图,生产调度问题,装箱问题,物流运输

别对这三个问题建立了混合整数规划或整数规划模型，，然后基于列生成方法设计逡逑了不同的精确算法，最后通过大量的数值实验对所设计的算法的性能进行评估和逡逑问题本身的性质进行分析探讨。本文具体的技术路线图在图１－２中给出。逡逑１６逡逑

实例图,可行调度,实例,博士学位论文

南京大学博士学位论文逦逡逑可以表示成ｌ｜ｐｙ邋＝邋ｐ＿／邋＋邋ｏｃ／Ｓｙ；邋ｄ邋－邋／ｐｍ｜Ｃｍａｘ，这里的ｄ邋－邋／ｐｍ表示恶化效应逡逑（Ｄｅｔｅｒｉｏｒａｔｉｏｎ邋Ｅｆｆｅｃｔ）和／ｐｍ表示柔性周其月维护活动（Ｆｌｅｘｉｂｌｅ邋Ｐｅｒｉｏｄｉｃ邋Ａｃｔｉｖｉｔｙ邋）。目逡逑标函数Ｃｍａｘ指的是最后一个工件的完工时刻。逡逑
【学位授予单位】：南京大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：F274

【相似文献】