Online bin packing problem with buffer and bounded size revisited

In this paper we study the online bin packing with buffer and bounded size, i.e., there are items with size within \((\alpha ,1/2]\) where \(0 \le \alpha < 1/2 \), and there is a buffer with constant size. Each time when a new item is given, it can be stored in the buffer temporarily or packed into some bin, once it is packed in the bin, we cannot repack it. If the input is ended, the items in the buffer should be packed into bins too. In our setting, any time there is at most one bin open, i.e., that bin can accept new items, and all the other bins are closed. This problem is first studied by Zheng et al. (J Combin Optim 30(2):360–369, 2015), and they proposed a 1.4444-competitive algorithm and a lower bound 1.3333 on the competitive ratio. We improve the lower bound from 1.3333 to 1.4230, and the upper bound from 1.4444 to 1.4243.     

Online algorithms for 1-space bounded multi dimensional bin packing and hypercube packing

In this paper, we study 1-space bounded multi-dimensional bin packing and hypercube packing. A sequence of items arrive over time, each item is a d-dimensional hyperbox (in bin packing) or hypercube (in hypercube packing), and the length of each side is no more than 1. These items must be packed without overlapping into d-dimensional hypercubes with unit length on each side. In d-dimensional space, any two dimensions i and j define a space P _ij . When an item arrives, we must pack it into an active bin immediately without any knowledge of the future items, and 90^°-rotation on any plane P _ij is allowed. The objective is to minimize the total number of bins used for packing all these items in the sequence. In the 1-space bounded variant, there is only one active bin for packing the current item. If the active bin does not have enough space to pack the item, it must be closed and a new active bin is opened. For d-dimensional bin packing, an online algorithm with competitive ratio 4 ^d is given. Moreover, we consider d-dimensional hypercube packing, and give a 2 ^d+1-competitive algorithm. These two results are the first study on 1-space bounded multi dimensional bin packing and hypercube packing.     

Online bin packing of fragile objects with application in cellular networks

We study a specific bin packing problem which arises from the channel assignment problems in cellular networks. In cellular communications, frequency channels are some limited resource which may need to share by various users. However, in order to avoid signal interference among users, a user needs to specify to share the channel with at most how many other users, depending on the user’s application. Under this setting, the problem of minimizing the total channels used to support all users can be modeled as a specific bin packing problem as follows: Given a set of items, each with two attributes, weight and fragility. We need to pack the items into bins such that, for each bin, the sum of weight in the bin must be at most the smallest fragility of all the items packed into the bin. The goal is to minimize the total number of bins (i.e., the channels in the cellular network) used. We consider the on-line version of this problem, where items arrive one by one. The next item arrives only after the current item has been packed, and the decision cannot be changed. We show that the asymptotic competitive ratio is at least 2. We also consider the case where the ratio of maximum fragility and minimum fragility is bounded by a constant. In this case, we present a class of online algorithms with asymptotic competitive ratio at most of 1/4+3r/2, for any r>1. A preliminary version of this paper appeared in Proc. of Workshop on Internet and Network Economics (WINE’05, pp. 564–573). The research of W.-T.C. was supported in part by Hong Kong RGC grant HKU5172/03E. The research of F.Y.-L.C. was supported in part by Hong Kong RGC Grant HKU7142/03E. The research of D.Y. was supported by NSFC (10601048). The research of G.Z. was supported in part by NSFC (60573020).     

On-line bin packing with restricted repacking

Semi-on-line algorithms for the bin-packing problem allow, in contrast to pure on-line algorithms, the use of certain types of additional operations for each step. Examples include repacking, reordering or lookahead before packing the items. Here we define and analyze a semi-on-line algorithm where for each step at most k items can be repacked, for some positive integer k. We prove that the upper bound for the asymptotic competitive ratio of the algorithm is a decreasing function of k, which tends to 3/2 as k goes to infinity. We also establish lower bounds for this ratio and show that the gap between upper and lower bounds is relatively small.     

Constructive procedures to solve 2-dimensional bin packing problems with irregular pieces and guillotine cuts

This paper presents an approach for solving a new real problem in cutting and packing. At its core is an innovative mixed integer programme model that places irregular pieces and defines guillotine cuts. The two-dimensional irregular shape bin packing problem with guillotine constraints arises in the glass cutting industry, for example, the cutting of glass for conservatories. Almost all cutting and packing problems that include guillotine cuts deal with rectangles only, where all cuts are orthogonal to the edges of the stock sheet and a maximum of two angles of rotation are permitted. The literature tackling packing problems with irregular shapes largely focuses on strip packing i.e. minimizing the length of a single fixed width stock sheet, and does not consider guillotine cuts. Hence, this problem combines the challenges of tackling the complexity of packing irregular pieces with free rotation, guaranteeing guillotine cuts that are not always orthogonal to the edges of the stock sheet, and allocating pieces to bins. To our knowledge only one other recent paper tackles this problem. We present a hybrid algorithm that is a constructive heuristic that determines the relative position of pieces in the bin and guillotine constraints via a mixed integer programme model. We investigate two approaches for allocating guillotine cuts at the same time as determining the placement of the piece, and a two phase approach that delays the allocation of cuts to provide flexibility in space usage. Finally we describe an improvement procedure that is applied to each bin before it is closed. This approach improves on the results of the only other publication on this problem, and gives competitive results for the classic rectangle bin packing problem with guillotine constraints.     

缺失数据下ARMA(1, 1)模型的估计方法

近几十年以来,国际上在对"风险的处理和效益的优化"这两个现代金融学的中心议题的分析和处理过程中,金融时间序列的计量学模型及其相应的分析越来越起到非常重要的作用.对于线性时间序列模型如AR(p),MA(q),ARMA(p,q)等,已经为我们所熟知.具体到模型的参数估计在数据没有缺失时,也有很多经典的办法,如最小二乘法、极大似然法等.但是当数据在中间有缺失时,上述方法将无能为力.本文将详细讨论在数据有缺失时的ARMA(1,1)模型,即Zt=αZ_t-1+ε_t-βε_t-1的参数的估计方法.     

基于区间灰数列的GM(1,1) 模型(GMBIGN(1,1))研究

GM(1,1)模型在灰系统的理论与应用研究中占有十分重要的地位,然而目前的GM(1,1)模型只能适用于对白化数表征的数列进行预测,而对于现实中存在的区间灰数表示的数列却无能为力.本文运用有关标准区间灰数的最新研究成果,构建了基于区间灰数表征的GM(1,1)模型GMBIGN(1,1)(GM(1,1)Based on Interval GreyNumber,GMBIGN(1,1)),并给出了其解析解.在此基础之上,本文以某地区某种能源价格区间变动情况这一现实经济问题为背景,建立了该地区某种能源价格区间变动的GMBIGN(1,1)模型,并对其进行了仿真与误差分析,效果良好.     

Notes on L(1,1) and L(2,1) labelings for n-cube

Suppose \(d\) is a positive integer. An \(L(d,1)\) -labeling of a simple graph \(G=(V,E)\) is a function \(f:V\rightarrow \mathbb{N }=\{0,1,2,{\ldots }\}\) such that \(|f(u)-f(v)|\ge d\) if \(d_G(u,v)=1\) ; and \(|f(u)-f(v)|\ge 1\) if \(d_G(u,v)=2\) . The span of an \(L(d,1)\) -labeling \(f\) is the absolute difference between the maximum and minimum labels. The \(L(d,1)\) -labeling number, \(\lambda _d(G)\) , is the minimum of span over all \(L(d,1)\) -labelings of \(G\) . Whittlesey et al. proved that \(\lambda _2(Q_n)\le 2^k+2^{k-q+1}-2,\) where \(n\le 2^k-q\) and \(1\le q\le k+1\) . As a consequence, \(\lambda _2(Q_n)\le 2n\) for \(n\ge 3\) . In particular, \(\lambda _2(Q_{2^k-k-1})\le 2^k-1\) . In this paper, we provide an elementary proof of this bound. Also, we study the \(L(1,1)\) -labeling number of \(Q_n\) . A lower bound on \(\lambda _1(Q_n)\) are provided and \(\lambda _1(Q_{2^k-1})\) are determined.     

无偏GM(1,1)幂模型其及应用

基于GM(1,1)幂模型的模拟误差分析,本文提出了无偏GM(1,1)幂模型及其参数优化方法.从理论上证明了无偏GM(1,1)幂模型对传统GM(1,1)幂模型及其本身的时间响应函数所表达的曲线进行模拟和预测具有重合性,其参数优化方法可以准确识别原始数据所蕴含的参数特性,完全消除了GM(1,1)幂模型自身固有的偏差.其建模过程避免了传统方法由差分方程向微分方程的跳跃导致的误差,应用范围覆盖了无偏GM(1,1)模型和离散灰色模型.数值模拟和实例分析表明,无偏GM(1,1)幂模型使得传统模型的模拟与预测精度得到了显著的改善.     

Multiechelon (R,S) Inventory Model*

Most studies in multiechelon inventory systems have concentrated on understanding the specific aspects of a system's behavior. The problem of optimal policy computation has largely been ignored. In this paper, we investigate a two-echelon inventory system experiencing stochastic demand and a pull system of inventory allocation. Both echelons use an order-up-to-level type control policy. A mathematical model is developed to determine the optimal order level at all echelons and validated through simulation. Two simple algorithms to locate the optimum solution are presented. The use of graphical tools in optimal policy calculation is also discussed.     

GM(1,1)模型时间响应函数的最优化

GM(1,1)是灰色系统理论的核心内容之一。本文利用"最小二乘法"确定GM(1,1)白化权函数的时间响应函数中的常数C,从而构建了GM(1,1)的时间响应函数的最优模型。经大量的数据模拟和与GM(1,1)对比,发现优化的GM(1,1)模型的模拟精度和预测精度均较高。     

在ARIMA(0,1,1)需求下的牛鞭效应与信息共享的评价

本文考虑一个包含一个供应商和一个零售商的两级供应链,研究在需求模型ARIMA(0,1,1)下牛鞭效应的量化和信息共享的价值,比较信息共享之前和之后的差异,其结果表明信息共享能给供应商带来减轻牛鞭效应、减少现有平均库存以及降低成本等好处。     

级库存(R,Q)策略的简单应用

考查由一个中心仓库和多个零售商构成的两级供应链配送系统,研究基于泊松需求假设的级库存(R,Q)策略的优化和应用.分析中心仓库在随机的提前期内的需求分布和缺货引起的零售商订货时延,提出优化级库存订货点的迭代计算算法.最后给出了具体的算例.     

灰色预测模型GM(1,1)在中国环保投资总额预测中的应用

文章首先阐明由于环保产业项目的功实施依赖于经济可行性,所以政府部门等的资金支持是必不可少的.然后,简要介绍了灰色预测方法GM(1.1)模型的适用条件、构造步骤及检验方法.接着,运用灰色理论研究了中国环保投资总额2000年至2005年的变化规律,建立了中国环保投资总额增长的灰色预测模型.最后,对中国未来"十一五"期间(2006-2010)各年度环保投资情况进行了预测,从而看到中国在生态工业体系建设方面的政府投资拉动作用.     

非等间距GM(1,1)模型背景值的优化

基于背景值是影响灰色建模精度的重要因素之一,本文对非等间距GM(1,1)模型中的背景值构造进行了研究,根据灰色模型的指数特性和积分特点,利用非齐次指数函数来拟合一次累加生成序列,提出了一种重构非等间距GM(1,1)模型背景值的方法。实例表明利用优化的背景值计算公式建立的非等间距GM(1,1)模型显著地改善了模拟和预测精度。该背景值不仅适合于非等间距建模,也适合于等间距建模,具有精度高、适用性强的特点。     

一类新的SBO及其在GM(1,1)中的应用研究

利用缓冲算子提高数据序列光滑性是提高灰色GM(1,1)模型预测精度的重要途径之一。在对缓冲算子和已有强化缓冲算子研究的基础上,构造了一类新的强化缓冲算子(strengthening buffer operator,SBO),有效地解决了冲击扰动数据序列在建模预测过程中常常出现的定量预测结果与定性分析结论不符的问题,实例分析结果表明:这类新的强化缓冲算子能显著提高数据预测模型的预测精度。     

基于初始条件优化的GM(1,1）幂模型及其应用

针对GM(1,1)幂模型幂指数和初始条件优化问题,提出了一种基于初始条件和幂指数协同优化的方法。根据新信息优先原理,通过引入权重信息控制函数优化初始条件,表现新旧信息在初始条件构建中作用大小的变化规律,最大限度提取小样本序列中的有效信息,反应新旧信息共同对系统趋势变化的影响;以平均相对误差最小化为目标,参数间约束关系作为条件,构建非线性优化模型,实现GM(1,1)幂模型的幂指数和初始条件协同优化。最后,通过我国网络购物用户规模预测实例研究表明,优化的模型实现模型平均相对误差在理论上的最小化,其建模效果要优于其他对比模型,并将其用于2016-2020年网购用户规模预测,表明本文模型的实用性和有效性。