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

33rd International Symposium on algorithms and Computation, ISAAC 2022

作者： Azar, Yossi Peretz, Eldad Touitou, Noam Tel Aviv University Israel Amazon Tel Aviv Israel

ISBN: (纸本)9783959772587

We consider the classic online problem of scheduling on multiple machines to minimize total flow time and total stretch where the input consists of estimates on the processing time provided for each job once released. The performance of such algorithms should depend on µ, the error in the estimates of the processing time for that instance (such an algorithm is called a distortion oblivious algorithm). Previously, a distortion oblivious algorithm to minimize flow time was provided only for a single machine. In this paper we extend the work to multiple machines and also consider the total stretch objective. In particular, we design a non-migrative distortion oblivious algorithm to minimize total flow time with a competitive ratio of O(µlog P), where P is the ratio between the maximum to minimum processing time. We show that with immediate-dispatching one cannot achieve a competitive ratio which is a function of µ and P;moreover, a competitive ratio which is sub-polynomial in the number of jobs is also impossible. We also present the first distortion-oblivious algorithm for minimizing the stretch time, both on a single and on multiple machines. The competitive ratio of these algorithms are O(µ2) which is optimal as we also prove a matching Ω(µ2) lower bound. © Yossi Azar, Eldad Peretz, and Noam Touitou.

关键词： scheduling algorithms

来源：评论

学校读者我要写书评

暂无评论

Scalable scheduling in Time-Sensitive Networking: An Efficient Stream Conflict Detection Method

引用

IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS 2025年第5期21卷 4105-4116页

作者： Xu, Lei Chen, Cailian Zhang, Yanzhou Li, Xin Wang, Shouliang Xu, Qimin Guan, Xinping Shanghai Jiao Tong Univ Sch Elect Informat & Elect Engn Shanghai 200240 Peoples R China Shanghai Key Lab Integrated Adm Technol Informat S Shanghai 200240 Peoples R China Minist Educ China Key Lab Syst Control & Informat Proc Shanghai 200240 Peoples R China Shanghai Jiao Tong Univ SJTU Paris Elite Inst Technol Shanghai 200240 Peoples R China

As an emerging communication technology, time-sensitive networking (TSN) holds the potential to enable real-time and deterministic interactions for streams within the Industrial Internet of Things. However, effectively and promptly scheduling large-scale streams in the TSN network poses a significant challenge due to high computational complexity. In this article, we conduct a schedulability analysis to preprocess the stream set with given routing paths, avoiding invalid searches and providing optimized guidance for stream routing. To accelerate the feasibility validation of potential solutions, an efficient stream conflict detection approach is proposed leveraging stream grouping with correlation analysis to compress the detection space. Integrating the above preprocess and efficient conflict detection, we develop a scalable scheduling algorithm with an incremental schedule synthesis to enhance scalability while ensuring low slot occupancy for all links. Evaluation results demonstrate that the proposed algorithm significantly reduces synthesis time and achieves low slot occupancy of all links compared to existing scheduling methods.

关键词： Job shop scheduling Routing Switches Complexity theory Scalability Industrial Internet of Things scheduling algorithms Schedules Real-time systems Logic gates Efficient conflict detection scalable scheduling stream grouping time-sensitive networking (TSN)

来源：评论

学校读者我要写书评

暂无评论

Efficient and fair PPO-based integrated scheduling method for multiple tasks of SATech-01 satellite

引用

Chinese Journal of Aeronautics 2024年第2期37卷 417-430页

作者： Qi SHI Lu LI Ziruo FANG Xingzi BI Huaqiu LIU Xiaofeng ZHANG Wen CHEN Jinpei YU Shanghai Satellite Network Research Institute CO. LTDShanghai 201210China Innovation Academy for Microsatellites of Chinese Academy of Sciences Shanghai 201306China University of Chinese Academy of Sciences Beijing 100039China

SATech-01 is an experimental satellite for space science exploration and on-orbit demonstration of advanced *** satellite is equipped with 16 experimental payloads and supports multiple working modes to meet the observation requirements of various *** to the limitation of platform power supply and data storage systems,proposing reasonable mission planning schemes to improve scientific revenue of the payloads becomes a critical *** this article,we formulate the integrated task scheduling of SATech-01 as a multi-objective optimization problem and propose a novel Fair Integrated scheduling with Proximal Policy Optimization(FIS-PPO)algorithm to solve *** use multiple decision heads to generate decisions for each task and design the action mask to ensure the schedule meeting the platform *** results show that FIS-PPO could push the capability of the platform to the limit and improve the overall observation efficiency by 31.5%compared to rule-based plans currently ***,fairness is considered in the reward design and our method achieves much better performance in terms of equal task *** of its low computational complexity,our task scheduling algorithm has the potential to be directly deployed on board for real-time task scheduling in future space projects.

关键词： Satellite observatories SATech-01 Multi-modes platform scheduling algorithms Reinforcement learning Proximal Policy Optimization(PPO)

来源：评论

学校读者我要写书评

暂无评论

Memory Priority scheduling Algorithm for Cloud Data Center Based on Machine Learning Dynamic Clustering Algorithm

引用

IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS 2025年第4期21卷 3485-3492页

作者： Liang, Bin Wu, Di Shiyou Univ Sch Comp Sci Xian 710065 Peoples R China Shaanxi Univ Sci & Technol Haojing Coll Xian 712046 Peoples R China

As the cloud data center (CDC) landscape continues to broaden, CDC resource utilization as the benchmark for assessing scheduling methodologies. Concurrently enhancing both CPU and memory utilization stands as a paramount priority. However, prevalent algorithms tend to solely prioritize CPU utilization while neglecting memory efficiency, ultimately escalating energy expenditure. This article initiates by conducting a comprehensive examination of memory utilization repercussions on CDCs. Subsequently, it facilitates the dynamic clustering of physical machines and virtual machine deployments, ensuring a balanced utilization profile. Furthermore, it introduces the memory priority scheduling algorithm for CDC based on machine learning dynamic clustering algorithm (PMPD). Comparative evaluations against other algorithms underscore the prowess of PMPD in concurrently optimizing CPU and memory utilization, thereby minimizing the number of active PMs and diminishing energy consumption of CDCs.

关键词： Virtual machines Clustering algorithms Heuristic algorithms Resource management Energy consumption scheduling algorithms Data centers Cloud computing Prediction algorithms Machine learning algorithms Cloud data center (CDC) clustering algorithm machine learning virtual machine (VM)

来源：评论

学校读者我要写书评

暂无评论

Priority-Dominated Traffic scheduling Enabled ATS in Time-Sensitive Networking

引用

IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT 2025年第1期22卷 470-484页

作者： Zhang, Lihui Sun, Gang Liu, Rulin Quan, Wei Yu, Hongfang Niyato, Dusit Univ Elect Sci & Technol China Minist Educ Key Lab Opt Fiber Sensing & Commun Chengdu 611731 Peoples R China Natl Univ Def Technol Coll Comp Changsha 410003 Peoples R China Nanyang Technol Univ Sch Comp Sci & Engn Jurong West 639815 Singapore

Time-Sensitive Networking (TSN) employs shaping mechanisms such as Time-Aware Shaping (TAS) and Cyclic Queuing and Forwarding (CQF), which depend heavily on precise time synchronization and complex Gate Control Lists (GCL) configurations, limiting their effectiveness in large-scale mixed traffic networks like those in vehicular systems. In response, IEEE 802.1Qcr protocol introduces the Asynchronous Traffic Shaping (ATS) mechanism, based on Urgency-Based Schedulers (UBS), to asynchronously address diverse traffic needs and ensure low and predictable latency. Nonetheless, no traffic scheduling algorithm exists that can be directly applied to ATS shapers in generic large-scale traffic scenarios to solve for fixed end-to-end (E2E) delay constraints and the number of priority *** this paper, we propose an urgency-based fast flow scheduling algorithm (UBFS) to address the issue. UBFS leverages domain-specific optimizing strategies with a focus on traffic delay urgency inspired by greedy algorithm for priority allocation across hops and flows, complemented by preprocessing for scenario solvability and dynamic verification to ensure scheduling feasibility. We benchmark UBFS against the method with both scalability and solution quality in typical network topology and demonstrate that UBFS achieves more rapid scheduling within seconds across linear, ring, and star topologies. Notably, UBFS significantly outperforms the baseline algorithm in scheduling efficiency in mixed and large-scale traffic environments, scheduling a larger number of flows. UBFS also reduces time costs by 2-10 times in delay-sensitive environments and by more than 10 times in large-scale scenarios, effectively balancing time efficiency, performance and scalability, thereby enhancing its applicability in real-world industrial settings.

关键词： Delays Job shop scheduling Scalability Heuristic algorithms Dynamic scheduling Costs Quality of service Synchronization scheduling algorithms Network topology Time-sensitive networking traffic scheduling asynchronous traffic shaping QoS high applicability

来源：评论

学校读者我要写书评

暂无评论

Performance analysis of buffered crossbar switch scheduling algorithms

引用

International Journal of Information and Computer Security 2015年第1期7卷 49-63页

作者： Prasanth, Narayanan Balasubramanian, Kannan Department of Information Technology National College of Engineering Maruthakulam Tirunelveli Tamilnadu27151 India Department of Computer Science and Engineering Mepco Schlenk Engineering College Sivakasi Tamilnadu India

The increasing demand for higher data rates on the internet requires routers that deliver high performance for high-speed connections. Nowadays high speed routers use the buffered crossbar switches, which have been the interest for research and commercialisation. In this paper, a study is made on the importance of buffered crossbar switches and their scheduling algorithms. Performance analysis is made for various buffered crossbar switch scheduling algorithms using non-uniform traffic patterns. © 2015 Inderscience Enterprises Ltd.

关键词： scheduling algorithms

来源：评论

学校读者我要写书评

暂无评论

Runtime performance of evolutionary algorithms for the chance-constrained makespan scheduling problem

引用

Theoretical Computer Science 2025年 1044卷

作者： Shi, Feng Huang, Daoyu Yan, Xiankun Neumann, Frank School of Computer Science and Engineering Central South University Hunan Changsha410083 China Xiangjiang Laboratory Hunan Changsha410205 China Optimisation and Logistics The University of Adelaide AdelaideSA5000 Australia

The makespan scheduling problem is an extensively studied NP-hard problem, and its simplest version is to find an allocation approach for a set of jobs with deterministic processing time to two identical machines such that the makespan is minimized. However, in real-life scenarios, the actual processing time of each job may be stochastic under the influence of external factors. Thus within this paper, we first propose a chance-constrained version of the makespan scheduling problem. Then we study the theoretical performance of RLS and (1+1) EA for three variants of the chance-constrained makespan scheduling problem. Within those variants, our theoretical analysis implies that distinct uncertainties influence the behaviors of the two algorithms. Specifically, we separately analyze the expected runtime of the two algorithms to obtain an optimal solution or almost optimal solution to the instances of the three variants. In addition, we further investigate the experimental performance of the two algorithms for the three variants. © 2025 The Authors

关键词： scheduling algorithms

来源：评论

学校读者我要写书评

暂无评论

Behavior scheduling for Multi-Robot Path Planning in Unknown Environment With Communication Constraints

引用

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2025年 22卷 10417-10428页

作者： Lu, Hui Zhao, Meng Zhou, Ping Mao, Kefei Beihang Univ Sch Elect & Informat Engn Beijing 100191 Peoples R China Beihang Univ Inst Unmanned Syst Beijing 100191 Peoples R China

The multi-robot system that combines flexibility and autonomy has unique advantages in many scenarios. In unknown environment, the threat posed by the environmental uncertainty to the path planning process cannot be ignored. The robots not only need to avoid obstacles, but also need to maintain communication with other robots to ensure timely negotiation. Inspired by the division of labor in biological community, this paper proposes robot behavior scheduling algorithm for multi-robot path planning in unknown environment with communication constraints. First, to avoid the occurrence of oscillation caused by a single force determining the robot behavior, the constituent elements of robot behavior are described in the form of multiple forces. Then, various robot behaviors are instantiated through a diverse combination of these elements and parameters. Finally, two complementary robot behavior scheduling methods are designed. The experiential potential field jointly constructed by robots is proposed to guide the robots to juggle avoidance, communication and planning task for the first time. The effectiveness of these behavior scheduling methods is verified in theory. The simulation experiment results based on real sensor parameters show that a small amount of robot detours can make the multi-robot system fully connected for 70% of the entire path planning process. Note to Practitioners-The motivation of this article is to avoid communication interruptions among robots when planning paths in unknown environment. When the robots perform the complex tasks, communication interruptions will lead to the inability of sharing environmental maps and allocation plans. The lack of such information may delay the task progress and even cause greater loss. This article focuses on the path planning demands in unknown environment and considers the automatic maintenance and reconstruction of the communication links among robots. Based on the analyses of the motivation in reaching the ta

关键词： Robots Path planning Robot kinematics Robot sensing systems Multi-robot systems scheduling Benchmark testing Propagation losses scheduling algorithms Communication networks Multi-robot system path planning communication constraints behavior scheduling experiential potential field

来源：评论

学校读者我要写书评

暂无评论

Courier: A Unified Communication Agent to Support Concurrent Flow scheduling in Cluster Computing

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2025年第5期36卷 861-876页

作者： Zhang, Zhaochen Zhang, Xu Bao, Zhaoxiang Wei, Liang Tan, Chaohong Dou, Wanchun Chen, Guihai Tian, Chen Nanjing Univ State Key Lab Novel Software Technol Nanjing 210093 Peoples R China Nanjing Univ Sch Elect Sci & Engn Nanjing 210093 Peoples R China Jiangsu Future Network Innovat Inst Zhenjiang 212013 Peoples R China

As one of the pillars in cluster computing frameworks, coflow scheduling algorithms can effectively shorten the network transmission time of cluster computing jobs, thus reducing the job completion times and improving the execution performance. However, most of existing coflow scheduling algorithms failed to consider the influences of concurrent flows, which can degrade their performance under a massive number of concurrent flows. To fill the gap, we propose a unified communication agent named Courier to minimize the number of concurrent flows in cluster computing applications, which is compatible with the mainstream coflow scheduling approaches. To maintain the scheduling order given by the scheduling algorithms, Courier merges multiple flows between each pair of hosts into a unified flow, and determines its order based on that of origin flows. In addition, in order to adapt to various types of topologies, Courier introduces a control mechanism to adjust the number of flows while maintaining the scheduling order. Extensive large-scale trace-driven simulations have shown that Courier is compatible with existing scheduling algorithms, and outperforms the state-of-the-art approaches by about 30% under a variety of workloads and topologies.

关键词： scheduling algorithms Cluster computing Data centers Topology Servers Switches scheduling Training Network topology Packet loss Data center network coflow scheduling congestion control

来源：评论

学校读者我要写书评

暂无评论

A Budget-Constrained Workflow scheduling Approach With Priority Adjustment and Critical Task Optimizing in Clouds

引用

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2025年 22卷 6907-6921页

作者： Fan, Mingjie Zhao, Xinchao Zuo, Xingquan Ye, Lingjuan Beijing Univ Posts & Telecommun Sch Sci Beijing 100876 Peoples R China Minist Educ Key Lab Math & Informat Networks Beijing 100876 Peoples R China Beijing Univ Posts & Telecommun Sch Comp Sci Beijing 100876 Peoples R China Minist Educ Key Lab Trustworthy Distributed Comp & Serv Beijing 100876 Peoples R China

In the rapidly evolving landscape of cloud computing, scheduling complex scientific workflows poses significant challenges, particularly with constraints like budget considerations. While recent years have seen considerable research focus on budget-constrained cloud workflow scheduling, existing studies primarily concentrate on constructing solutions without delving into potential enhancements. To address this gap, our paper introduces PACP-HEFT, a modified HEFT algorithm integrating priority adjustment and task optimization to minimize makespan. Leveraging the Heterogeneous Earliest-Finish-Time (HEFT) algorithm as its foundation, PACP-HEFT incorporates two priority adjusters informed by task characteristics gleaned from task dependency topology and real-time scheduling data. Additionally, a critical task optimizer conducts thorough analyses and optimizations to reduce overall makespan. Extensive experimentation with real-world workflows underscores PACP-HEFT's superior performance compared to contemporary algorithms.

关键词： scheduling Cloud computing Costs Heuristic algorithms scheduling algorithms Feature extraction Resource management workflow scheduling budget constraint priority adjustment critical task optimizing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：