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

multiprocessor task scheduling to minimize the maximum tardiness and the total completion time

IEEE TRANSACTIONS ON ROBOTICS AND AUTOMATION 2000年第6期16卷 824-830页

作者： Cai, XQ Lee, CY Wong, TL Chinese Univ Hong Kong Dept Syst Engn & Engn Management Sha Tin Hong Kong Peoples R China Texas A&M Univ Dept Ind Engn College Stn TX 77843 USA

We consider a scheduling problem with two parallel processors, where one task may need the processing of more than one processor simultaneously. Alternatives are available to allocate processors to process a task. Under a given alternative, a task is assigned to some specific processor(s), and requires correspondingly a specific processing time. task preemption is allowed. The problem is to minimize the maximum tardiness of task completion times from their due dates, through determining the following: 1) the optimal assignment of each task to processor(s) and 2) the optimal schedule for each processor to process the tasks assigned to it. We present a two-stage approach, which can generate an optimal solution in pseudopolynomial time. We also apply/extend the two-stage approach to other problems where the number of processors required by each task is prespecified, preemption is prohibited, and the total completion time is to be minimized.

关键词： dynamic programming heuristic algorithms maximum tardiness multiprocessor task scheduling resource allocation total completion time

来源：评论

学校读者我要写书评

暂无评论

multiprocessor task scheduling Optimization for Cyber-Physical System Using an Improved Salp Swarm Optimization Algorithm

引用

SN Computer Science 2024年第1期5卷 184页

作者： Acharya, Biswaranjan Panda, Sucheta Ray, Niranjan K. Department of Computer Application Veer Surendra Sai University of Technology Burla Odisha Sambalpur 768018 India School of Computer Engineering KIIT Deemed to be University Odisha Bhubaneswar 751024 India

Salp Swarm Algorithm (SSA) is a bio-inspired optimization algorithm used in this paper to optimize the multiprocessor scheduling process in the current cyber-physical system. Although SSA is mainly utilized in terms of local search, in our case, an improved version has been introduced with the use of a Local Search Algorithm (LSA) and binary SSA, namely Improved SSA (ISSA). More to the point, eight optimization algorithms are compared with this proposed ISSA namely SSA, Particle Swarm Optimization (PSO), Genetic Algorithm (GA), Grey Wolf Optimizer (GWO), Jaya Algorithm (JAYA), Chaotic Squirrel Search Algorithm (CSSA), Quantum-inspired Binary Chaotic Salp Swarm Algorithm (QBCSSA) and Space Transformation Search (STS) with SSA is termed as STS-SSA. The performance of ISSA along with the other 6 meta-heuristic and 2 improved versions of SSA algorithms are compared with 12 traditional benchmark functions and evaluated for 100 and 300 dimensions. Convergent curves have also been demonstrated and the proposed ISSA has been shown to find a global optimum within the very initial phase of iterations. For calculating the efficiency of the proposed algorithm, the gear train design problem has been employed. The proposed algorithm has demonstrated higher accuracy rates and better convergent values than the other applied algorithms. © 2024, The Author(s), under exclusive licence to Springer Nature Singapore Pte Ltd.

关键词： Benchmark function Cyber-physical system Gear train strategy Global optima Grid computing Local search algorithm (LSA) multiprocessor task scheduling Salp swarm algorithm

来源：评论

学校读者我要写书评

暂无评论

A comparison of multiprocessor task scheduling algorithms with communication costs

引用

COMPUTERS & OPERATIONS RESEARCH 2008年第3期35卷 976-993页

作者： Hwang, Reakook Gen, Mitsuo Katayama, Hiroshi Waseda Univ Grad Sch Sci & Engn Dept Ind & Management Syst Engn Tokyo 1698555 Japan Waseda Univ Grad Sch Informat Prod & Syst Dept Informat Architecture Kitakyushu Fukuoka 8080135 Japan

Both parallel and distributed network environment systems play a vital role in the improvement of high performance computing. Of primary concern when analyzing these systems is multiprocessor task scheduling. Therefore, this paper addresses the challenge of multiprocessor task scheduling parallel programs, represented as directed acyclic task graph (DAG), forexecution on multiprocessors with communication costs. Moreover, we investigate an alternative paradigm, where genetic algorithms (GAs) have recently received p much attention. which is a class of robust stochastic search algorithms for various combinatorial optimization problems. We design the new encoding mechanism with a multi-functional chromosome that uses the priority representation-the so-called priority-based multi-chromosome (PMC). PMC can efficiently represent a task schedule and assign tasks to processors. The proposed priority-based GA has show effective performance in various parallel environments for scheduling methods. (c) 2006 Elsevier Ltd. All rights reserved.

关键词： multiprocessor task scheduling genetic algorithm priority-based multi-chromosome (PMC)

来源：评论

学校读者我要写书评

暂无评论

WORST-CASE PERFORMANCE EVALUATION ON multiprocessor task scheduling WITH RESOURCE AUGMENTATION

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2011年第4期22卷 971-982页

作者： Ye, Deshi He, Qinming Zhejiang Univ Coll Comp Sci Hangzhou 310027 Zhejiang Peoples R China

We study the worst-case performance of approximation algorithms for the problem of multiprocessor task scheduling on m, identical processors with resource augmentation, whose objective is to minimize the makespan. In this case, the approximation algorithms are given k (k >= 0) extra processors than the optimal off-line algorithm. For on-line algorithms, the Greedy algorithm and shelf algorithms are studied. For off-line algorithm, we consider the LPT (longest processing time) algorithm. Particularly, we prove that the schedule produced by the LPT algorithm is no longer than the optimal off-line algorithm if and only if k >= m - 2.

关键词： Performance evaluation multiprocessor task scheduling resource augmentation on-line algorithm virtual machine

来源：评论

学校读者我要写书评

暂无评论

Heuristic algorithms for multiprocessor task scheduling in a two-stage hybrid flow-shop

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2003年第2期149卷 390-403页

作者： Oguz, C Ercan, MF Cheng, TCE Fung, YF Hong Kong Polytech Univ Dept Management Kowloon Hong Kong Peoples R China Hong Kong Polytech Univ Dept Elect Engn Kowloon Hong Kong Peoples R China

The aim of this paper is to propose heuristic algorithms for a two-stage flow-shop scheduling problem with multiprocessor tasks to minimize the makespan. The heuristic algorithms are constructive in nature. They schedule the tasks one at a time from a given sequence. The rules considered for sequencing the tasks are based on simple priority rules from the literature. Some lower bounds for the problem are also derived to be used in the performance analysis of the heuristic algorithms. Next, the average performance of the proposed heuristic algorithms is analyzed by a computational experiment using randomly generated problem instances. The results suggest that these heuristic algorithms are both efficient and effective. The paper concludes with a discussion of the insights obtained from the experimental analysis about this type of scheduling problems. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： heuristics flow-shop makespan multiprocessor task scheduling performance evaluation

来源：评论

学校读者我要写书评

暂无评论

Lower bound algorithms for multiprocessor task scheduling with ready times

引用

International Transactions in Operational Research 2005年第5期12卷 481-508页

作者： Caramia, Massimiliano Iovanella, Antonio Istituto per le Applicazioni del Calcolo M. Picone Viale del Policlinico Rome 137-00161 Italy Dipartimento di Statistica Probabilità e Statistiche applicate University of Rome La Sapienza Rome 5-00185 Piazzale Aldo Moro Italy Dipartimento di Informatica Sistemi e Produzione University of Rome Tor Vergata Rome 1-00133 Via del Politecnico Italy

In this paper, we deal with multiprocessor task scheduling with ready times and prespecified processor allocation. We consider an on-line scenario where tasks arrive over time, and, at any point in time, the scheduler only has knowledge of the released tasks. An application of this problem arises in wavelength division multiplexing broadcasting where the main future will be in the so-called one-to-many transmission. We propose algorithms to find lower bounds of the minimum makespan, and present experiments on various scenarios. © 2017 Wiley. All rights reserved.

关键词： Algorithm Lower bound multiprocessor task scheduling

来源：评论

学校读者我要写书评

暂无评论

Performance evaluation on multiprocessor task scheduling with resource augmentation

Performance evaluation on multiprocessor task scheduling wit...

引用

International Symposium on Performance Evaluation Computer and Telecommunication Systems

作者： Ye, Deshi He, Qinming Zhejiang Univ Coll Comp Sci Hangzhou 310027 Zhejiang Peoples R China

ISBN: (纸本)9781565553224

We study the worst-case performance of approximation algorithms for the problem of multiprocessor task scheduling on m identical processors with resource augmentation, whose objective is to minimize the makespan. In this case, the approximation algorithms are given k (k >= 0) extra processors than the optimal off-line algorithm. For on-line algorithms, the Greedy algorithm and shelf algorithms are studied. For off-line algorithm, we consider the LPT (longest processing time) algorithm. Particularly, we prove that the schedule produced by the LPT algorithm is no longer than the optimal off-line algorithm if and only if k >= m - 2.

关键词： Performance evaluation multiprocessor task scheduling Resource augmentation On-line algorithm Off-line algorithm

来源：评论

学校读者我要写书评

暂无评论

Elephant Herding Optimization for multiprocessor task scheduling in Heterogeneous Environment 1

引用

2nd International Conference on Computational Intelligence in Pattern Recognition (CIPR)

作者： Sahoo, Ronali Madhusmita Padhy, Sasmita Kumari Veer Surendra Sai Univ Technol Dept Comp Applicat Burla 768018 Odisha India

ISBN: (数字)9789811524493

ISBN: (纸本)9789811524493;9789811524486

In this study, a novel method has been implemented to solve the problems of task scheduling. This study observances the problem of dynamic multiprocessor task scheduling in a heterogeneous grid environment. Here, the scheduling problem of task is designed as an optimization problem. Recently developed swarm intelligence-based metaheuristic algorithm named, elephant herding optimization (EHO) has been implemented to minimize the makespan for task scheduling problem. EHO method is motivated by the herding performance of group of elephants. The simulation results verified that the implemented algorithm surpasses various other metaheuristic algorithms, such as shuffled frog leaping algorithm (SFLA), particle swarm optimization (PSO) and genetic algorithm (GA).

关键词： multiprocessor task scheduling Grid computing Elephant herding optimization (EHO)

来源：评论

学校读者我要写书评

暂无评论

Heuristic algorithms for multiprocessor task scheduling in a two-stage hybrid flow-shop

Heuristic algorithms for multiprocessor task scheduling in a...

引用

7th International Workshop on Project Managment and scheduling

作者： Oguz, C Ercan, MF Cheng, TCE Fung, YF Hong Kong Polytech Univ Dept Management Kowloon Hong Kong Peoples R China Hong Kong Polytech Univ Dept Elect Engn Kowloon Hong Kong Peoples R China

关键词： heuristics flow-shop makespan multiprocessor task scheduling performance evaluation

来源：评论

学校读者我要写书评

暂无评论

multiprocessor task Graph scheduling Using a Novel Graph-Like Learning Automata

引用

INTERNATIONAL JOURNAL OF GRID AND DISTRIBUTED COMPUTING 2015年第1期8卷 41-54页

作者： Boveiri, H. R. Islamic Azad Univ Shushtar Branch Sama Tech & Vocat Training Coll Shushtar Iran

Optimized task scheduling is one of the most important challenges in multiprocessor environments such as parallel and distributed systems. In such these systems, each parallel program is decomposed into the smaller segments so-called tasks. task execution times, precedence constrains and communication costs are modeled by using a directed acyclic graph (DAG) named task graph. The goal is to minimize the program finish-time (makespan) by means of mapping the tasks to the processor elements in such a way that precedence constrains are preserved. This problem is shown to be NP-hard in general form and some restricted ones. Therefore, utilization of heuristic and meta-heuristic approaches to solve this problem is logical. Learning automata (LA) is an abstract model to interact with stochastic environment, which tries to reform itself based on the environment feedback. Although a learning automaton itself is a simple component, a group of them by cooperating each other can show complicated behavior, and can coverage to desired solutions under appropriate learning algorithm. In this paper, an ingenious graph-like learning automata in which each task in the task graph is represented by a learning automaton tries to solve the multiprocessor task-scheduling problem in a collective manner. Set of different experiments on various real-world task-graphs has been done and archived results are so promising compared to the traditional methods and genetic algorithm.

关键词： Learning automata multiprocessor task scheduling parallel and distributed systems task graph

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：