在线装箱与混合流水调度问题近似算法研究

发布时间：2020-09-10 15:41

　　 装箱和调度作为组合优化问题中比较经典的两大类,已在工业生产、物流管理、交通规划等行业发挥了重要作用。它们的研究见证了近似算法理论的发展历程,为其它离散组合优化问题的研究提供了重要的理论科学依据。近年来,带缓冲区的在线装箱已成为研究热点,当物品尺寸上限不超过1/2、缓冲区大小为2时,目前最好的结果是郑等人给出的1.4444的渐近竞争比。对第一阶段单机第二阶段多台并行机的两阶段混合流水调度问题,孙等人给出了特定条件下近似比为3的近似算法。本文主要针对这些结果分别进行改进和扩展研究。对于装箱问题,主要研究了带常数大小缓冲区和有界空间两类在线模型。带缓冲区在线装箱指物品在线到来后可先放入缓冲区,待缓冲区满后再进行装箱决策。本文基于物品尺寸划分思想先将物品按尺寸区间进行分类,箱子亦按最后所装物品的组合特征进行相应分类。装箱时按类别从缓冲区中选择合适物品装入特定类别箱子中。本文给出了使用大小为2缓冲区、物品被分成4类的在线算法Al。竞争比分析时,采用权重函数思想,根据物品在箱子中的相对占比设计物品的权重值。研究结果表明算法A1的最坏渐近竞争比为1.4375。该结果改进了前人使用相同大小辅助空间时的1.4444竞争比结果;若将缓冲区扩大至3,物品被划分成5类,竞争比可改进至1.4243。通过构建使任何算法都不会表现很好的问题实例,将带缓冲的在线装箱算法下界由1.3333改进至1.4230,缩紧了上下界之间的缝隙。同时研究了有界空间在线装箱模型,在打开5个和7个箱子情况下,给出物品上限为1/2时的最坏渐近竞争比分别为1.4243和1.4236的两个在线算法,改进了经典调和算法中使用同样大小有界空间的竞争比结果。对于混合流水调度问题,主要研究了集流水与平行机两种调度形式的两阶段混合流水调度模型。模型中第一阶段仅有一台机器,第二阶段有m台并行机,任务在第二阶段可由多台机器并行处理。按第一阶段所有任务全部结束再启动第二阶段操作的思路,利用已有条形装箱与平行机调度算法,从理论上设计了若干近似比小于等于3的近似算法,改进了前人给出的特定约束条件下的3近似比结果。对第二阶段机器数目分别为2和3的特定模型,根据任务在第二阶段所需机器数将任务分组,按先整组调度、组内再列表调度的设计思路,给出了线性时间复杂度下近似比分别为2.5和2.67的近似算法。最后通过对原模型任务不可切割条件的松弛,将任务切割至第二阶段的所有机器上,利用经典两阶段流水调度的Johnson算法,给出所研究模型新的下界,改进了前人给出的下界结果。
【学位单位】：大连理工大学
【学位级别】：博士
【学位年份】：2019
【中图分类】：TP301.6;TH247
【部分图文】：

图２．２算法Ａ１可能装载情况示意图逡逑Ｆｉｇ．邋２．２邋Ｐｏｓｓｉｂｌｅ邋ｂｉｎ邋ｃｏｎｆｉｇｕｒａｔｉｏｎｓ邋ｏｆ邋Ａ１逡逑２．３．２竞争比分析逡逑本节将利用权重函数思想，通过权重函数建立算法Ａ１与离线最优算法间关系，据物品在箱子中的占有率来设计权重函数，由此分析最坏情况下算法Ａ１的渐近竞争比首先根据算法装箱策略考查一下各类箱子的最小装载率。逡逑引理２．２：算法Ａ１完成时，除了步骤５中用到的箱子外，其它任意一个／ｆｃ－６ｍ（Ａ；邋＝１，２，邋３）所装物品尺寸之和至少为每一个／４邋－逦所装物品尺寸之和至少为｜。逡逑证明：根据算法Ａ１处理过程知，每个Ａ邋－邋中有２个－邋ｐｉｅｃｅｓ，根据物品分规则，每个Ａ邋－邋ｐｉｅｃｅｓ都大于￥，故每个／丨－６咖至少装｜。同理每个／２邋－邋至少｜，每个Ａ邋—６ｍ至少装ｆ。逡逑算法执行过程中，如果需要打开１个Ｊ４邋－邋６ｉｎ，那么意味着此时此刻Ｓ１＇中至多１个Ａ邋－邋ｐｉｅｃｅｓ、２个／２邋－邋ｐｉｅｃｅｓ，由于缓冲区总的大小为２，贝＿冲区中所有剩余／３邋－邋ｐｉｅｃｅｓ和Ｊ４邋－邋ｐｉｅｃｅｓ类物品总的尺寸大小一定超过２邋－邋｜邋－着＝｜；同时由于此１＇－－—

ＢＥＧＩＮ逡逑（１）将第１个物品ａｉ放入缓冲区中；逡逑（２）如果没有新到来的物品，则转到步骤５；否则重复地将每一个新到来物品放入缓冲区逡逑中，直到放不进去为止；逡逑（３）令Ｖ邋＝邋ｅ邋＊５｝邋Ｕ邋｛叫｝，分以下几种情况装箱；逡逑３．１）若Ｓ＇中至少有Ａ：邋＋邋１个厶—ｐｉｅｃｅｓ＃邋＝邋１，２，邋３），则打开１个－邋６ｍ，任选ｆｃ邋＋邋１逡逑个－邋ｐｉｅｃｅｓ物品放入这个４邋－邋Ｍｎ中，关闭该箱子，转到步骤２；逡逑３．２）若Ｙ中厶－Ｐｉｅｃｅｓ类物品总大小超过｜，则打开１个厶－■，按ＮＦ策略将尽逡逑可能多的Ａ－ｐｉｅｃｅｓ类物品放人该箱子中，结束后关闭该箱子，转到步骤２；逡逑３．３）若以上情况均未出现，则打开］个忍－ｂｉｎ箱子，首先将Ｓ１＇中所有／４－ｐｉｅｃｅｓ逡逑类物品放入该筘子中，然后苒按ＮＦ策略将尽可能多的－邋ｐｅｃｅｓ类物品放入该逡逑箱子中，直到放不进去为止，关闭该箱子，转到步骤２；逡逑（５）将缓冲区中剩余物品按ＮＦ策略装箱。逡逑ＥＮＤ逡逑图２．３展示了算法Ａ２执行后各类箱子可能的装载情况。逡逑

ｍ邋：＝邋ｍ－＼－邋ｍ／ｃ；逡逑ＥＮＤ逡逑若物品尺寸分布相对比较均匀，算法结束后每类箱子的可能装载情况如图３．１所示。逡逑５＋￡逦；逦：逡逑１＋＾逦５＋￡：逦：逦；逡逑４邋逦邋■逡逑卜＇——邋Ｗ逦■逡逑逦逦＼＋￡逦逦邋——逦＾ｍｚ逡逑逦邋ｊ＋ｆ逦逦逡逑３逦－＋￡逦逦邋ｎ邋ｓ逡逑逦邋逦邋Ｊ邋＋邋ｇ邋ｈ＋￡逡逑Ｉｘ邋－邋ｂｉｎ逦Ｌ邋—ｂｌｎ逦ｈ邋－邋ｂｉｎ逦／４邋—邋ｂｉｎ逦ｈ邋－ｂｉｎ逡逑图３．１算法Ａ３可能装载情况示意图逡逑Ｆｉｇ邋３．１邋Ｐｏｓｓｉｂｌｅ邋ｂｉｎ邋ｃｏｎｆｉｇｕｒａｔｉｏｎｓ邋ｏｆ邋Ａ３逡逑－３８－逡逑

【参考文献】

相关期刊论文 前4条

1 孙景昊;邓庆绪;孟亚坤;;GPU上两阶段负载调度问题的建模与近似算法[J];软件学报;2014年02期

2 陈田;陈庆新;毛宁;刘建军;;具有两道工序的柔性同序加工车间任务投放策略[J];工业工程;2010年05期

3 王辉;鲁习文;;工件带到达时间的两阶段柔性流水作业的近似算法[J];运筹学学报;2007年03期

4 张国川;k－Bounded　Space　On－line装箱中AFB_k算法的界[J];应用数学学报;1996年03期

相关博士学位论文 前4条

1 赵晓凡;在线装箱问题相关近似算法研究[D];北京交通大学;2016年

2 丁宁;若干调度问题的算法研究[D];大连理工大学;2016年

3 姚国辉;若干组合优化问题的算法研究[D];山东大学;2009年

4 石永强;若干批处理机排序与装箱问题的算法研究[D];浙江大学;2005年

相关硕士学位论文 前4条

1 孙蕊;多车场多配送中心满载车辆路径问题研究[D];沈阳师范大学;2016年

2 邵飞牛;一维装箱问题启发式算法的设计与分析[D];东北大学;2013年

3 陈幸瑜;两台同类机极大化机器最小负载问题研究[D];浙江大学;2008年

4 郭文静;两阶段模糊柔性流水车间排序模型及算法[D];南京理工大学;2006年

本文编号：2815993