Online scheduling on parallel machines with two GoS levels

This paper investigates the online scheduling problem on parallel and identical machines with a new feature that service requests from various customers are entitled to many different grade of service (GoS) levels. Hence each job and machine are labeled with the GoS levels, and each job can be processed by a particular machine only when the GoS level of the job is not less than that of the machine. The goal is to minimize the makespan. In this paper, we consider the problem with two GoS levels. It assumes that the GoS levels of the first k machines and the last m−k machines are 1 and 2, respectively. And every job has a GoS level of 1 alternatively or 2. We first prove the lower bound of the problem under consideration is at least 2. Then we discuss the performance of algorithm AW presented in Azar et al. (J. Algorithms 18:221–237, 1995) for the problem and show it has a tight bound of 4−1/m. Finally, we present an approximation algorithm with competitive ratio . Research supported by Natural Science Foundation of Zhejiang Province (Y605316) and its preliminary version appeared in Proceedings of AAIM2006, LNCS, 4041, 11-21.     

The canadian traveller problem and its competitive analysis

From the online point of view, we study the Canadian Traveller Problem (CTP), in which the traveller knows in advance the structure of the graph and the costs of all edges. However, some edges may fail and the traveller only observes that upon reaching an adjacent vertex of the blocked edge. The goal is to find the least-cost route from the source O to the destination D, more precisely, to find an adaptive strategy minimizing the competitive ratio, which compares the performance of this strategy with that of a hypothetical offline algorithm that knows the entire topology in advance. In this paper, we present two adaptive strategies—a greedy or myopic strategy and a comparison strategy combining the greedy strategy and the reposition strategy in which the traveller backtracks to the source every time when he/she sees a failed edge. We prove tight competitive ratios of 2 ^k+1−1 and 2k+1 respectively for the two strategies, where k is the number of failed edges in the graph. Finally, we propose an explanation of why the greedy strategy and the comparison strategy are usually preferred by drivers in an urban traffic environment, based on an argument related to the length of the second-shortest path in a grid graph. We would like to acknowledge the support from NSF of China (No. 70525004, No. 70121001 and No. 60736027), and the support from K.C. Wong Education Foundation, Hong Kong.     

Single machine batch scheduling with release times

Motivated by a high-throughput logging system, we investigate the single machine scheduling problem with batching, where jobs have release times and processing times, and batches require a setup time. Our objective is to minimize the total flow time, in the online setting. For the online problem where all jobs have identical processing times, we propose a 2-competitive algorithm and we prove a corresponding lower bound. Moreover, we show that if jobs with arbitrary processing times can be processed in any order, any online algorithm has a linear competitive ratio in the worst case. A preliminary version of a part of this paper was presented at the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS 2006). We gratefully acknowledge reviewers’ comments that helped to improve the presentation of this work. Supported by the Swiss SBF under contract no. C05.0047 within COST-295 (DYNAMO) of the European Union. Research carried out while B. Weber was affiliated with the Institute of Theoretical Computer Science, ETH Zurich.     

Semi-online scheduling with “end of sequence” information

We study a variant of classical scheduling, which is called scheduling with “end of sequence” information. It is known in advance that the last job has the longest processing time. Moreover, the last job is marked, and thus it is known for every new job whether it is the final job of the sequence. We explore this model on two uniformly related machines, that is, two machines with possibly different speeds. Two objectives are considered, maximizing the minimum completion time and minimizing the maximum completion time (makespan). Let s be the speed ratio between the two machines, we consider the competitive ratios which are possible to achieve for the two problems as functions of s. We present algorithms for different values of s and lower bounds on the competitive ratio. The proposed algorithms are best possible for a wide range of values of s. For the overall competitive ratio, we show tight bounds of ϕ + 1 ≈ 2.618 for the first problem, and upper and lower bounds of 1.5 and 1.46557 for the second problem. The authors would like to dedicate this paper to the memory of our colleague and friend Yong He who passed away in August 2005 after struggling with illness. D. Ye: Research was supported in part by NSFC (10601048).     

Trade-offs in Online Purchase Decisions:: Two Empirical Studies in Europe

The Internet offers firms a new way to market their products and services and to interact with their end-consumers. While many firms have developed websites, very little is known about the trade-offs consumers are willing to make when making online purchases. With millions of websites competing for attention, online firms need to know in what way consumers make purchase decisions online. Consumers mainly evaluate websites on the basis of choice and convenience. In this paper, we present the results of two European studies that examine what consumers actually value in an online environment. In study 1, we assess choice-related trade-offs in terms of number of product categories, variety of products within a given category and product-related information. Conjoint analysis revealed that product-related information represents an important decision-making variable. In study 2, we assess convenience-related trade-offs in terms of logistics, fulfilment and security. Conjoint analysis revealed that fulfilment is the most important variable related to online handling. Finally, our study clearly indicates that firms have to distinguish different consumer segments on the basis of their preferences. This knowledge enables online firms to use their resources more effectively.     

A note on online strip packing

In online strip packing we are asked to pack a list of rectangles one by one into a vertical strip of unit width, without any information about future rectangles. The goal is to minimize the total height of strip used. The best known algorithm is First Fit Shelf algorithm (Baker and Schwarz in SIAM J. Comput. 12(3):508–525, 1983), which has an absolute competitive ratio of 6.99 under the assumption that the height of each rectangle is bounded from above by one. We improve the shelf algorithm and show an absolute competitive ratio of without the restriction on rectangle heights. Our algorithm also beats the best known online algorithm for parallel job scheduling. Ye’s research supported by NSFC(10601048). Zhang’s research supported by NSFC(60573020).     

在线拍卖中的“托”出价研究

本文分析了独立的私人估价环境下最优保留价格与竞买人数之间的关系,纠正了最优保留价格与竞买人数无关的传统观点.在此基础上,讨论了卖者可能递交"托"出价的条件以及拍卖中只剩下一个竞买人时卖者的最优"托"出价.     

中国情景下网络广告心理效果的影响因素分析

基于一项对563位中国消费者进行的网络广告心理效果的问卷调查,本文对网络广告心理效果的影响因素进行了探索性因素分析,得到了反映网络广告心理效果评价的九个因素,将它们与传统广告心理效果指标进行比较分析,指出该指标体系中适应能力、媒体运用、时代气息及结构布局四个因素是由网络媒体的特殊性带来的,而其余的购买信息、情感驱动、主题认知、记忆效果、亲和程度五个因素则反映了网络广告作为广告而言的基本功能.     

基于心流体验视角的在线消费者购买行为影响因素研究

在线消费者处于虚拟的网络环境中,具有其独特的需求和行为特征,而"心流体验"理论在解释影响在线消费者行为的情感和认知因素方面有重要意义.本文将从"心流体验"视角探索影响在线消费者购物行为的因素.本文研究表明,网站设计维度、表现维度、消费者自身维度和网站内容维度都会显著影响在线消费者心流体验,从而导致消费者增加无计划的购买数量以及增强重复购买的意愿.     

需求依赖于库存的易变质品在线采购问题研究

根据现实生活中常见的库存量越大越吸引消费者购买兴趣的现象,本文建立了需求依赖于库存的易变质品采购模型。在不假设价格服从任何分布的条件下,提出了采购价格不确定背景下的易变质品在线采购策略。本文采用在线问题及其竞争分析的方法来进行建模分析,设计出有效的在线竞争采购价格驱动的(s,S)策略,与离线最优策略进行比较,得出理论竞争比和最优经济采购数量和采购时间间隔。最后,通过数值算例说明该策略在现实中具有较好的实际竞争性能比,且在多个价格序列下都表现良好,从而说明了该策略是鲁棒的,可以为企业提供有价值的决策建议。     

企业竞争行为的回应预测研究

竞争回应的预测是竞争互动领域的一个核心论题。由于传统的竞争互动理论主要是以市场行为为核心的研究,而在相当大的程度上忽视了非市场行为的重要性与价值。本文以中国家电行业为研究对象,采用结构化内容分析法,试图从市场与非市场的角度全面探讨竞争回应的预测问题,以期为中国企业的管理者们在制定与实施战略,以及预测竞争对手策略与行为选择时提供一些重要的实践启示。     

Online interval scheduling: randomized and multiprocessor cases

We consider the problem of scheduling a set of equal-length intervals arriving online, where each interval is associated with a weight and the objective is to maximize the total weight of completed intervals. An optimal 4-competitive algorithm has long been known in the deterministic case, but the randomized case remains open. We give the first randomized algorithm for this problem, achieving a competitive ratio of 3.5822. We also prove a randomized lower bound of 4/3, which is an improvement over the previous 5/4 result. Then we show that the techniques can be carried to the deterministic multiprocessor case, giving a 3.5822-competitive 2-processor algorithm, and a 4/3 lower bound for any number of processors. We also give a lower bound of 2 for the case of two processors. A preliminary version of this paper appeared in the Proceedings of COCOON 2007, LNCS, vol. 4598, pp. 176–186. The work described in this paper was fully supported by a grant from City University of Hong Kong (SRG 7001969), and NSFC Grant No. 70525004 and 70702030.     

虚拟社区成员参与动机的实证研究——以网络游戏为例

以Richard Bartle的Intere st Graph模型和Nicholas的五因素理论研究成果为基础,我们利用一对一深度访谈和焦点座谈会的研究方法,挖掘出驱动人们参与网络虚拟社区的关键动机,并发展了适应中国网络虚拟社区参与动机的量表.本研究进一步利用该动机量表进行了实证研究,通过数据分析得出了驱动人们参与虚拟社区的八大动机,它们分别为领导、沉溺、攻击与贬低、性、赚钱、角色探索、亲和以及休闲与自由.本研究还发现,成就动机和领导动机并非相互独立,他们相互融合为一个动机.     

多阶段占线赁购问题与竞争分析

经典占线赁购决策是建立在设备使用寿命无限大的假设下进行竞争策略分析,是一种单阶段的占线决策问题。论文把设备使用寿命因素考虑进占线赁购问题,扩展单阶段占线赁购问题为多阶段占线赁购。给出了该问题的离线解;设计了等长赁购策略,证明该策略是唯一最优策略;给出了风险策略基本性质,为进一步研究多阶段占线赁购风险补偿模型奠定了基础。     

具有概率分布在线租赁问题策略研究

在经济系统中,决策越来越呈现出在线性特征,传统优化方法在解决这类在线问题时,通常假设未来输入是一随机变量从而寻求概率意义上的最优决策。近年来,在优化领域兴起了一种新的研究方法——在线算法与竞争分析,为解决这类在线问题提供了新的视角,但传统的竞争分析方法有意规避概率分布假设。对于在线租赁决策问题,由于其输入结构简单且具有良好的统计性质,似乎忽略这些有用的信息而只运用标准的竞争比方法分析显然具有不足之处。在本文中,我们将其输入结构的概率分布引入纯竞争分析方法中,从而建立了具有概率情形的最优在线租赁模型,并得到了最优竞争策略及其竞争比。     

网络中选择环境对多样化寻求行为的影响研究

消费者在选择产品时通常会发生多样化寻求行为,而其对信息刺激的需要是消费者产生多样化寻求行为的原因之一。本文通过实验方法研究了在网络购物中,消费者是否会通过平衡从产品选择和选择环境中所获得的这两种刺激来达到其最佳刺激水平。研究结果显示,在网络环境下,通过改变选择环境中消费者同期购买的其他产品类别的构成,增加对受试者的刺激,会减少其在目标产品选择中的多样化寻求行为。     

A successive approximation algorithm for the multiple knapsack problem

It is well-known that the multiple knapsack problem is NP-hard, and does not admit an FPTAS even for the case of two identical knapsacks. Whereas the 0-1 knapsack problem with only one knapsack has been intensively studied, and some effective exact or approximation algorithms exist. A natural approach for the multiple knapsack problem is to pack the knapsacks successively by using an effective algorithm for the 0-1 knapsack problem. This paper considers such an approximation algorithm that packs the knapsacks in the nondecreasing order of their capacities. We analyze this algorithm for 2 and 3 knapsack problems by the worst-case analysis method and give all their error bounds.     

网上交易中的声誉机制——来自淘宝网的证据

本文主要研究在法律缺失或法律不完善情况下网上交易中声誉机制的作用.计量回归结果显示,卖方的个人声誉(用卖方信用度来衡量)对其销售量有正面的影响,但这种影响是非线性的:存在两个临界点,低于下临界点,卖方信用度对卖家商品的销售量没有影响;高于上临界点,卖家商品的销售量也不会因为卖方信用度的提高而增加.属于商盟的卖家在给定时间内的销售量高于不属于任何商盟的卖家.从而验证了网上交易中卖家个人声誉和卖家所属商盟集体声誉的作用.本文根据实证结果进一步提出一个推测:网上交易市场存在较大的搜寻成本,这削弱了声誉机制的作用.     

从竞争优势到竞争优势群

在当今的超强竞争时代,环境的动态性日益成为影响企业竞争成败的关键因素,从动态的角度分析竞争优势成为当务之急。本文从动态的角度构建了竞争优势群分析框架,对竞争优势的维持、增强、权衡和更新等问题进行了研究。