受启动空间约束的装箱问题

提出了一种带有启动空间的约束装箱问题(start-up bin packing problem,简称SBPP),即不同类型的物品放入同一箱子中需要一个启动空间.该问题在工作分配、任务调度和日常生活中的包装等问题中有着广泛的应用背景.给出了一个求解SBPP的线性脱线算法C-NF,其最坏情况渐近性能比为2,与启动空间的大小无关.对该算法的平均性能进行了实验分析.另外,还分析了SBPP的在线特性,指出大量的经典在线装箱算法应用于SBPP都不存在确定的最坏情况渐近性能比,也给出了一种具有确定的最坏情况渐近性能比的在线算法.     

调和装箱算法的平均性能分析

经典一维装箱问题在多处理器调度、资源分配和日常生活中的计划、包装、调度等优化问题中有着极为重要的应用 .该文系统地分析了在待处理的物品大小相互独立的情况下 ,L ee & L ee提出的调和近似装箱算法的平均性能 ;具体给出了在均匀分布下 ,调和算法平均性能比的值 ,并用实验验证了这些结果 .     

局内装箱算法综述

系统地介绍了局内装箱算法,归纳了其发展过程中的各种改进如数据分配模型、箱的划分等。阐述了该算法在工作分配、任务调度以及日常生活中的计划、包装、调度等计算机工程领域的应用。最后,对局内装箱算法提出了进一步的研究方向。     

互联网信息管理中的带拒绝装箱覆盖问题

作为对装箱覆盖问题的推广,提出了带拒绝的装箱覆盖问题:设有许多等长的一维箱子,给定一个物品集,每个物品有两个参数:长度和费用.物品可以放入箱子也可被拒绝放入箱子.每个物品只准放入一只箱子中,每只箱子中的物品容量总和至少为箱子容量,一旦箱子中的物品长度达到要求则需启用新箱.如果物品被放入箱中,则产生费用.该问题是一个新的组合优化问题,在内部互联网信息管理等问题中有着广泛的应用背景.给出了一个求解该问题的局外近似算法C-FF,分析其最坏情况渐进性能比为1/2,并给出了相应的实验结果.     

有色装箱问题的在线近似算法

有色装箱问题是经典装箱问题的推广,它在多处理器实时计算机系统的任务调度等实际问题中有着很强的应用背景,提出了求解有色装箱问题的KC－A算法,它首先对输入物品进行分类预处理,然后在同一类内部使用经典装箱问题的近似策略A,给出了KC－A算法最坏情况渐近性能比的下界,分析了当选用的算法A是著名装相算法NF,FF,BF,WF时KC－A算法的最坏情况渐近性能比和平均性能比,给出了实验结果,并指出KC－FF表现出相对更好的实验效果。     

受位置约束的有色装箱问题

作为对有色装箱问题的推广,提出了一种受位置约束的有色装箱问题（longest item at the bottom coloring bin packing problem,LIBCBPP）,即在有色物品的装箱过程中,要求重（长）的物品置于轻（短）的物品下方.该问题在任务调度和日常生活中的运输等问题中有着广泛的应用背景.给出了一个求解该问题的近似KC-LIBFF算法,分析其最坏情况渐进性能比为2,并给出了相应的实验结果.     

带约束的一维装箱问题近似算法的研究

作为经典装箱问题的扩展,有色装箱问题在多处理器实时调度的过程中有很强的应用背景。论文提出了有色装箱问题的新算法-SCPF算法,按颜色分类,将相同颜色的物品分成一类。放置时按照相同颜色的物品首先放置的原则,将物品进行装箱。实验证明,该算法与文献犤3犦中的KC-A算法相比具有更好的装箱效果,使用的箱子数更少。并从理论上论证了该算法的性能比KC-A算法更好。     

A型变尺寸装箱问题之模型及算法研究

作为对经典一维装箱问题的推广,提出一种A型变尺寸装箱问题（A-shaped Variable-sized BinPacking Problem,简称A SVBP）,即在物品的装箱过程中,每样物品有高度和横截面积两个参数,并且箱子的大小不一。该问题在文件系统管理和日常生活中的运输等问题中有着广泛的应用背景。把装箱问题的经典算法以及遗传算法推广到A型变尺寸装箱问题,实验结果表明：按照本文提出的求解模式,离线情况下求解A型变尺寸装箱问题最终结果的质量取决于预先求解其退化为经典装箱问题时的算法,求解物品装箱序列时用首次适应混合遗传算法比用Next Fit算法、First Fit算法、Best Fit算法最终得到的结果要好。     

基于LIB的有色箱覆盖问题

提出了如下定义的受位置约束的有色箱覆盖问题,即在有色物品的箱覆盖过程中,要求重(长)的物品置于轻(短)的物品下方.该问题是一个新的组合优化问题,来源于多处理器任务调度.给出一个求解该问题的局内近似算法KC-LIBFF算法,分析其最坏情况渐进性能比为0,并给出了相应的实验结果;进一步对求解该问题的局内算法性能比的下界进行了讨论.     

半在线入库堆垛问题的动态求解算法

堆场垛位优化问题一直是仓储管理的难点和焦点之一,垛位优化可以保证物料装卸和出入库的高效率,同时对保证合同交货期也起着至关重要的作用。针对仓储和生产一体化下的入库堆垛问题,本文通过分析将其归结为一类半在线的A型装箱问题,并依据问题的特点,建立了最小化总倒垛次数的优化模型。根据货场天车在相邻入库过程中存在空闲作业量的特点,设计了一种前序货物允许移动的动态堆垛策略,结合堆垛约束后嵌入到经典装箱启发式算法中,最后通过仿真算例验证了该策略的有效性。     

带拒绝箱覆盖问题的局内算法

作为对装箱覆盖问题的推广,提出带拒绝的装箱覆盖问题.设有许多等长的一维箱子,给定一个物品集,每个物品有两个参数:长度和费用.物品可以放入箱子也可被拒绝放入箱子,每个物品只准放入一只箱子中,每只箱子中的物品容量总和至少为箱子容量,一旦箱子中的物品长度达到要求则需启用新箱.如果物品被放入箱中,则产生费用.该问题是一个新的组合优化问题,在内部互联网信息管理等问题中有着广泛的应用背景.给出一个求解该问题的局内近似算法C-FF,分析其最坏情况渐近性能比为1/2,并给出了相应的实验结果.     

多箱型三维装箱问题及其优化研究

对多箱型三维装箱问题进行了描述,提出了求解该问题的禁忌算法。算法基于自然数编码,设计了货物的摆放规则和序列生成方式,采用三种邻域,利用邻域操作控制集装箱数量限制,采用惩罚函数处理集装箱重量约束和重心约束。介绍了算法的原理,给出了具有代表性算例实验结果并且进行了分析。实验结果表明了提出的禁忌算法对优化多箱型三维装箱问题的有效性。     

A Hard Dial-a-Ride Problem that is Easy on Average

In the dial-a-ride-problem (Darp) objects have to be moved between given sources and destinations in a transportation network by means of a server. The goal is to find the shortest transportation for the server. We study the Darp when the underlying transportation network forms a caterpillar. This special case is strongly NP-hard in the worst case. We prove that in a probabilistic setting there exists a polynomial time algorithm that finds an optimal solution with high probability. Moreover, with high probability the optimality of the solution found can be certified efficiently. In addition, we examine the complexity of the Darp in a semirandom setting and in the unweighted case.Research supported by the German Science Foundation (DFG, grant FOR 413/1-1)Research supported by the German Science Foundation (DFG, grant Gr 883/10)Research supported by the German Science Foundation (DFG, grant PR 296/6-3)     

求解入库堆垛问题的改进约束满足算法

入库堆垛问题普遍存在于堆场作业管理中,是在货物数目和出库顺序已知的前提下,要求较长（重）的货物置于较短（轻）的货物下方,目标是实现占用垛位数最少。通过问题分析,将其归结为一类带顺序约束的A形装箱问题,并建立了约束满足模型,设计了嵌入经典装箱启发式的约束满足求解算法。实验表明,该算法对于求解复杂约束下的大规模堆场问题较现有的装箱启发式有一定程度的改善。     

求解online packing problem的F-B绝对近似算法

FF算法由于其在线特性在处理在线装箱问题得到广泛使用,但它无法预测后面达到物品造成装箱率低,提出一种预留一定比例的各类未装满箱体的装箱算法。首先对未装满箱体分类并给出相应的数据结构,接着设计一种绑定配对策略来预留各类未装满箱体数目,并引入间隔函数控制新箱体的启用,最后基于FF算法结合预留策略对物品进行装箱来保证装箱的绝对近似比。提出了一种预留绑定配对策略为后续输入物品提供预测空间,特别的是F-B算法能得到5/3的绝对近似比。     

一种独立任务的同型机调度快速算法

如何将n个独立任务调度到m台同型机上加工,使总完成时间最短,是一个复杂问题.通过分析Bound Fit预备算法的性质,结合MULTIFIT和Bound Fit提出QUICKFIT算法;对相同机器数和任务数,QUICKFIT能用比MULTIFIT和Bound Fit都少的迭代次数得到相同的总完成时间.实验结果表明,任务机器比越大,QUICKFIT算法的性能就越优于MULTIFIT和Bound Fit.绝大多数情况下,总完成时间等于MULTIFIT和Bound Fit中的最小者.该算法适用于大规模同型机调度.     

一类两阶段杂交流水作业的近似算法

讨论了一类两台机流水作业要求最后完工工件完工时间最早的排序问题.问题中每个工件包含两个加工任务:第1个任务可以在任何一台机器上加工,第2个任务只能在第1个任务完成后在第2台机器上加工.如果要求在加工同一个工件的两个任务时,两个任务之间不能有停顿,则称其为不可等待的模型,记作NSHFS.如果第2个任务可以在第1个任务完成后的任意时间加工,则称其为允许等待的模型,记作SHFS.对于SHFS模型,在魏麒和何勇工作的基础上给出了一种改进的最坏情况界为8/5的多项式时间近似算法.对于NSHFS模型,首先证明它是NP-难的,并且给出了一种最坏情况界为5/3的多项式时间近似算法.