检索结果-内蒙古大学图书馆

Optimal algorithms for online single machine scheduling with deteriorating jobs

THEORETICAL COMPUTER SCIENCE 2012年 445卷 75-81页

作者： Liu, Ming Zheng, Feifeng Wang, Shijin Huo, Jiazhen Donghua Univ Glorious Sun Sch Business & Management Shanghai 200051 Peoples R China Tongji Univ Sch Econ & Management Shanghai 200092 Peoples R China Xi An Jiao Tong Univ Sch Management Xian 710049 Shaanxi Peoples R China

In many realistic scenarios of job processing, one job consumes a longer time to be satisfied with a later start time of processing. This phenomenon is known as job's deterioration effect. Such effect is unexplored in the context of online environment. In this paper we study online single machine scheduling for deteriorating jobs, where jobs arrive over time and become known to any online algorithm on their arrivals. The processing time of each job is a linearly increasing function of its start time. We mainly investigate three online models that minimize makespan, total completion time and maximum delivery time, respectively. For each model we present an optimal online algorithm in competitiveness. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Scheduling online algorithm Deteriorating job Competitive analysis

来源：评论

学校读者我要写书评

暂无评论

online hierarchical parallel-machine scheduling in shared manufacturing to minimize the total completion time

引用

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY 2023年第11期74卷 2432-2454页

作者： Wei, Qi Wu, Yong Cheng, T. C. E. Sun, Fengxin Jiang, Yiwei Ningbo Univ Finance & Econ Ningbo Peoples R China Hong Kong Polytech Univ Kowloon Hong Kong Peoples R China Ningbo Univ Technol Ningbo Peoples R China Zhejiang Gongshang Univ Contemporary Business & Trade Res Ctr Hangzhou Peoples R China Zhejiang Gongshang Univ Contemporary Business & Trade Res Ctr Sch Management & E Business Hangzhou 310018 Peoples R China

We consider online hierarchical scheduling on m identical machines in shared manufacturing to minimize the total completion time. Each job has a unit-size processing time. The jobs arrive one by one and must be assigned to one of the m machines before the next job arrives. The jobs with a lower hierarchy can only be processed on the first k machines, 1 <= k <= m-1, and the jobs with a higher hierarchy can be processed on any one of the m machines. We first show that the lower bound of the problem is at least 1+min{1/m-k+1,max{2/k inverted right perpendiculexpressionr s right ceiling +3k+2m+4/ inverted right perpendiculexpressionr s right ceiling ,2/k left floor s right floor +3k+2m+4/ left floor s right floor }}, where s=root 2m+4/k. Proposing a greedy algorithm, we show that its tight competitive ratio is 1+2(m-k)k/m(root(4m-3k)k root+k)by analyzing a set of instances that must contain a worst-case instance, which is different from the general method of calculating the competitive ratio. In addition, for the case where k = 1, we present an improved online algorithm with a tight competitive ratio of 1+max{2/ inverted right perpendiculexpressionr root 2m+4 root right ceiling +2m+4/ inverted right perpendiculexpressionr root 2m+4 root right ceiling +3,2/ left floor root 2m+4 right floor +2m+4/ left floor root 2m+4 root right floor +3}, which is optimal for 2 <= m <= 5. Numerical experiments show that the greedy online algorithm has good performance, especially when k approaches 1 or m.

关键词： Share manufacturing hierarchical scheduling online algorithm competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Competitive online adaptive scheduling for sets of parallel jobs with fairness and efficiency

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2014年第3期74卷 2180-2192页

作者： Sun, Hongyang Hsu, Wen-Jing Cao, Yangjie Nanyang Technol Univ Sch Comp Engn Singapore 639798 Singapore Zhengzhou Univ Sch Software Engn Zhengzhou Peoples R China

We study online adaptive scheduling for multiple sets of parallel jobs, where each set may contain one or more jobs with time-varying parallelism. This two-level scheduling scenario arises naturally when multiple parallel applications are submitted by different users or user groups in large parallel systems, where both user-level fairness and system-wide efficiency are of important concerns. To achieve fairness, we use the well-known equi-partitioning algorithm to distribute the available processors among the active job sets at anytime. For efficiency, we apply a feedback-driven adaptive scheduler that periodically adjusts the processor allocations within each set by consciously exploiting the jobs' execution history. We show that our algorithm achieves asymptotically competitive performance with respect to the set response time, which incorporates two widely used performance metrics, namely, total response time and makespan, as special cases. Both theoretical analysis and simulation results demonstrate that our algorithm improves upon an existing scheduler that provides only fairness but lacks efficiency. Furthermore, we provide a generalized framework for analyzing a family of scheduling algorithms based on feedback-driven policies with provable efficiency. Finally, we consider an extended multi-level hierarchical scheduling model and present a fair and efficient solution that effectively reduces the problem to the two-level model. (C) 2013 Elsevier Inc. All rights reserved.

关键词： Adaptive scheduling Parallel jobs Set response time Multiprocessors online algorithm Competitive analysis Hierarchical scheduling Fairness Efficiency

来源：评论

学校读者我要写书评

暂无评论

online Throughput Maximization for Energy Harvesting Communication Systems with Battery Overflow

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2017年第1期16卷 185-197页

作者： Wu, Weiwei Wang, Jianping Wang, Xiumin Shan, Feng Luo, Junzhou Southeast Univ Sch Comp Sci & Engn Nanjing Jiangsu Peoples R China City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China HeFei Univ Technol Sch Comp & Engn Hefei Anhui Peoples R China

Energy harvesting communication system enables energy to be dynamically harvested from natural resources and stored in capacitated batteries to be used for future data transmission. In such a system, the amount of future energy to harvest is uncertain and the battery capacity is limited. As a consequence, battery overflow and energy dropping may happen, causing energy underutilization. To maximize the data throughput by using the energy efficiently, a rate-adaptive transmission schedule must address the trade-off between a high- rate transmission which avoids energy overflow and a low-rate transmission which avoids energy shortage. In this paper, we study an online throughput maximization problem without knowing future information. To the best of our knowledge, this is the first work studying the fully-online transmission rate scheduling problem for battery-capacitated energy harvesting communication systems. We consider the problem under two models of the communication channel, a static channel model that assumes the channel status is stable, and a fading channel model that assumes the channel status varies. For the former, we develop an online algorithm that approximates the offline optimal solution within a constant factor for all possible inputs. For the latter, that the channel gains vary in range [h(min), h(max)], we propose an online algorithm with a proven Theta(log(h(max)/h(min)))-competitive ratio. Our simulation results further validate the efficiency of the proposed online algorithms.

关键词： Energy harvesting battery capacity energy overflow energy-efficient rate scheduling throughput maximization online algorithm competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Randomized online File Allocation on Uniform Cactus Graphs

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2009年第12期E92D卷 2416-2421页

作者： Kawamura, Yasuyuki Matsubayashi, Akira Kanazawa Univ Div Elect Engn & Comp Sci Kanazawa Ishikawa 9201192 Japan

We study the online file allocation problem on ring networks. In this paper, we present a 7-competitive randomized algorithm against an adaptive online adversary on uniform cactus graphs. The algorithm is deterministic if the file size is 1. Moreover, we obtain lower bounds of 4.25 and 3.833 fora deterministic algorithm and a randomized algorithm against an adaptive online adversary, respectively, on ring networks.

关键词： online algorithm file allocation data management cactus graph

来源：评论

学校读者我要写书评

暂无评论

online rescheduling of multiple picking agents for warehouse management

引用

ROBOTICS AND COMPUTER-INTEGRATED MANUFACTURING 2011年第1期27卷 62-71页

作者： Rubrico, Jose I. U. Higashi, Toshimitu Tamura, Hirofumi Ota, Jun Univ Tokyo RACE Chiba 2708568 Japan Univ Tokyo Dept Precis Engn Bunkyo Ku Tokyo 1138656 Japan Murata Machinery Ltd Inuyama Aichi 4840076 Japan Murata Syst Ltd Minami Ku Kyoto 6018326 Japan

In this paper we present a solution for a dynamic rescheduling problem involving new orders arriving randomly while static orders have been given in advance in warehouse environments We propose two variations of an incremental static scheduling scheme one based on the steepest descent insertion called OR1 and the other on multistage rescheduling called OR2 Both techniques are enhanced by a local search procedure specifically designed for the problem at hand We also implemented several existing online algorithms to our problem for evaluative purposes Extensive statistical experiments based on real picking data indicate that the proposed methodologies are competitive with existing online schedulers and show that load-balancing algorithms such as OR1 yield the best results on the average and that OR2 is effective in reducing the picking time when dynamism is low to moderate (C) 2010 Elsevier Ltd All rights reserved

关键词： Dynamic scheduling Warehouse management online algorithm

来源：评论

学校读者我要写书评

暂无评论

online estimation of noise parameters for Kalman filter

引用

STRUCTURAL ENGINEERING AND MECHANICS 2013年第3期47卷 361-381页

作者： Yuen, Ka-Veng Liang, Peng-Fei Kuok, Sin-Chi Univ Macau Fac Sci & Technol Dept Civil & Environm Engn Taipa Peoples R China

A Bayesian probabilistic method is proposed for online estimation of the process noise and measurement noise parameters for Kalman filter. Kalman filter is a well-known recursive algorithm for state estimation of dynamical systems. In this algorithm, it is required to prescribe the covariance matrices of the process noise and measurement noise. However, inappropriate choice of these covariance matrices substantially deteriorates the performance of the Kalman filter. In this paper, a probabilistic method is proposed for online estimation of the noise parameters which govern the noise covariance matrices. The proposed Bayesian method not only estimates the optimal noise parameters but also quantifies the associated estimation uncertainty in an online manner. By utilizing the estimated noise parameters, reliable state estimation can be accomplished. Moreover, the proposed method does not assume any stationarity condition of the process noise and/or measurement noise. By removing the stationarity constraint, the proposed method enhances the applicability of the state estimation algorithm for nonstationary circumstances generally encountered in practice. To illustrate the efficacy and efficiency of the proposed method, examples using a fifty-story building with different stationarity scenarios of the process noise and measurement noise are presented.

关键词： Bayesian probabilistic approach Kalman filter online algorithm process noise measurement noise structural health monitoring

来源：评论

学校读者我要写书评

暂无评论

online bin packing problem with buffer and bounded size revisited

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2017年第2期33卷 530-542页

作者： Zhang, Minghui Han, Xin Lan, Yan Ting, Hing-Fung Dalian Univ Technol Sch Software Technol Dalian 116620 Peoples R China Dalian Neusoft Univ Informat Software Engn Dept Dalian 116023 Peoples R China Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

In this paper we study the online bin packing with buffer and bounded size, i.e., there are items with size within where , 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.

关键词： Bin packing online algorithm Asymptotic competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Collaborative online Edge Caching With Bayesian Clustering in Wireless Networks

引用

IEEE INTERNET OF THINGS JOURNAL 2020年第2期7卷 1548-1560页

作者： Liu, Junyan Li, Dapeng Xu, Youyun Nanjing Univ Posts & Telecommun Key Lab Broadband Wireless Commun & Sensor Networ Nanjing 210003 Peoples R China Southeast Univ Natl Mobile Commun Res Lab Nanjing 210096 Peoples R China

In this article, we study the edge caching problem by considering the heterogeneous context with unknown users' preferences. The cache provider (CP) can personalize the users' storage based on available data to maximize the overall cache hit rate, accounting for the dynamic natures of both mobile edge cache scenarios and the users' preferences. Toward this end, we introduce an online Bayesian clustering caching algorithm for the CP to autonomously learn the users' interactive cache hit data in a collaborative way while maintaining sustainable scalability. Specifically, a Bayesian generative framework called the Dirichlet multinomial mixture (DMM) model is used to describe the uncertainty about the latent number of users' clusters, each of which consists of the users with the same preference. Then, a dynamic clustering policy is proposed to obtain both the underlying mapping of users to clusters and the preferences of each cluster by using a collapsed Gibbs sampling algorithm. Subsequently, cache decisions are made according to the generated mappings by extending the traditional cache bandit algorithm to a new bandit mechanism with clusters of arms, capable of expediting the learning process between the exploitation and exploration. We theoretically characterize the value of dynamic Bayesian clustering for the long-term edge caching scenario with respect to the regret incurred by the noncluster schemes. Finally, using a real-world data set, our numerical results show that the proposed scheme outperforms the caching algorithms without clustering in the uncertain network scenario.

关键词： Heuristic algorithms Clustering algorithms Bayes methods Wireless communication Internet of Things Collaboration Hypercubes Bayesian clustering content cache edge computing online algorithm reinforcement learning

来源：评论

学校读者我要写书评

暂无评论

To store or not: online cost optimization for running big data jobs on the cloud

引用

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE 2024年 156卷 42-52页

作者： Fu, Xiankun Pan, Li Liu, Shijun Shandong Univ Sch Software Jinan Peoples R China

As businesses increasingly rely on cloud-based big data analytics services to drive insights, reducing the cost of storing and analyzing large volumes of data in the cloud has become a major concern. During the execution of big data analysis jobs, some of the generated data can be reused by subsequent jobs. By storing such intermediate data, the cost of running big data jobs can be greatly reduced for businesses using cloud services. An important challenge is how to determine which data should be stored in order to save costs. Existing storing strategies do not differentiate between data with different usage frequencies, resulting in significant storage costs in practical applications. To address the aforementioned challenges, in this paper we propose two online algorithms, one deterministic and the other randomized, which dynamically determine whether to store the data with the aim of saving cost. We show that our proposed deterministic algorithm (resp., randomized) incurs costs within a factor of 2 - alpha' (resp., 2/1+alpha') times the minimum cost obtained by an optimal offline algorithm which is assumed to know the exact future a priori. Finally, through extensive experiments with real-world workload of big data jobs in Alibaba Cloud environment, we demonstrate that our proposed online algorithms can achieve significant cost savings under common cloud pricing schemes.

关键词： Cloud computing Cost optimization online algorithm Big data analysis Competitive analysis algorithm design

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：