在线A形装箱问题: 模型及算法研究

A形装箱问题是由生产实际引发的一个新的数学模型,它是经典一维装箱问题的一种变形--每样物品有高度和半径两个参数.把装箱问题的经典算法推广到在线A形装箱问题,并分别从最坏情形分析与数值模拟两方面对算法进行了比较,得到了不同而且有趣的结果. 证明了 First Fit算法的渐近竞争比为2, 而其它在线启发式算法如Next Fit, Worst Fit, Best Fit(BF), Almost Worst Fit, Harmonic的渐近竞争比皆为无界; 通过数值模拟,在平均意义下BF的性质最好.     

Stears收敛模型的一个几何解释

在 n 人合作对策中,Stearns 给出并证明了:从转归集中的任何一点出发,总可以用 K—Transfer 的收敛模型收敛到核(kernel)中的一点。本文从几何上给出这个模型的一个几何解释。     

一种求解N人合作对策核仁的方法

本文采用Maschler, Peleg和Shaply,[4]所给核仁的等价定义。用与此定义相同的递归顺序,先通过解一线性规划问题求出(ε~i,Σ_i)中的ε~i和达到这一最优值的最优极点解。再以这一点为起点,以Kohlberg定理([8] Theorem2)为基础,建立一个线性规划问题,求它的最优极点解,反复迭代计算,最后求出Σ_(io)这样,就求出了(ε~i,Σ_i)(i=1,2,…,τ)和达到这一结果的相应点列。这个点列收敛到核仁,点列中地多有(2~n-2)~2/2个点。     

在线A形装箱问题

研究了一类有实际背景的新的装箱问题—— A形装箱问题 (ASBP)的在线情形 .在 ASBP中物品均为圆柱形 ,并且在每个箱子中物品均摆放成 A字形 ,即后到达的物品放在先到达的物品之上且上层物品的截面半径不超过下层物品的截面半径 ,优化目标是最小化装下所有物品所用的箱子数 .当所有物品半径都相同时 ASBP退化成经典一维装箱问题 (BP) ,故 BP为 ASBP的特殊情形 .BP的大多数启发式算法可以推广到 ASBP中 ,我们从最坏情形分析的角度讨论了两类 ASBP启发式算法 .证明了直接推广的启发式算法性能较差 ,其中一些算法的渐近最坏比甚至可以任意大 ;如果半径的种类有限 ,按半径分类的启发式算法的性能较好 ,并且一些算法的渐近最坏比和它们所基于的 BP启发式算法的渐近最坏比相等.     

Parallel Machine Scheduling with Special Jobs

Introduction Parallel machine scheduling problems arise in many fields, including service and manufacturing systems. A parallel machine scheduling problem has a sequence of n jobs with processing times { p1 , p 2 , ... , p n } to be processed on m paralle…