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

Online scheduling in a parallel batch processing system to minimize makespan using restarts

THEORETICAL COMPUTER SCIENCE 2007年第1-3期374卷 196-202页

作者： Fu, Ruyan Tian, Ji Yuan, Jinjiang Lin, Yixun Zhengzhou Univ Dept Math Zhengzhou 450052 Peoples R China

We consider an online scheduling problem in a parallel batch processing system with jobs in a batch being allowed to restart. Online means that jobs arrive over time, and all jobs' characteristics are unknown before their arrival times. A parallel batch processing machine can handle up to several jobs simultaneously. All jobs in a batch start and complete at the same time. The processing time of a batch is equal to the longest processing time of jobs in the batch. We are allowed to restart a batch, that is, a running batch may be interrupted, losing all the work done on it. Jobs in the interrupted batch are released and become independently unscheduled jobs. We deal with an unbounded model where each batch's capacity is sufficiently large. We provide a linear online algorithm with competitive ratio 3/2 for the problem. We also show that the considered problem has no online algorithm using restarts with competitive ratio less than (5 - root 5)/2. (C) 2007 Elsevier B.V. All rights reserved.

关键词： single machine scheduling parallel batch online algorithm restart competitive ratio

来源：评论

学校读者我要写书评

暂无评论

A best possible online algorithm for parallel batch scheduling with delivery times and limited restart

引用

OPTIMIZATION LETTERS 2021年第4期15卷 1155-1173页

作者： Liu, Hailing Lu, Xiwen Li, Wenjie East China Univ Sci & Technol Dept Math Shanghai 200237 Peoples R China Henan Univ Engn Coll Sci Zhengzhou 451191 Henan Peoples R China Luoyang Normal Univ Sch Math Sci Luoyang 471934 Henan Peoples R China

We consider the online scheduling on an unbounded (drop-line) parallel batch machine to minimize the time by which all jobs have been delivered. In this paper, all jobs arrive over time and the running batches are allowed limited restart. Here limited restart means that a running batch which contains restarted jobs cannot be restarted again. A drop-line parallel batch machine can process several jobs simultaneously as a batch, and all jobs in a batch start at the same time, and the completion time of a job equals the sum of its starting time and its processing time. Here we consider the restricted model: all jobs have agreeable processing times and delivery times. We provide a best possible online algorithm H with a competitive ratio of I for the problem on an unbounded parallel batch machine and the corresponding problem on an unbounded drop-line parallel batch machine, respectively.

关键词： Online scheduling parallel batch Drop-line Limited restart Delivery nine

来源：评论

学校读者我要写书评

暂无评论

A PTAS for parallel batch scheduling with rejection and dynamic job arrivals

引用

THEORETICAL COMPUTER SCIENCE 2009年第27-29期410卷 2732-2745页

作者： Cao, Zhigang Yang, Xiaoguang Chinese Acad Sci Key Lab Management Decis & Informat Syst Acad Math & Syst Sci Beijing 100190 Peoples R China

In the parallel batch scheduling model, a group of jobs can be scheduled together as a batch while the processing time of this batch is the greatest processing time among its members;in the model of scheduling with rejection, any job can be rejected with a corresponding penalty cost added to the objective value. In this paper, we present a PTAS for the combined model of the above two scheduling models where jobs arrive dynamically. The objective is to minimize the sum of the makespan of the accepted jobs and the total penalty of the rejected ones. Our basic approaches are dynamic programming and roundings. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Scheduling parallel batch Dynamic job arrivals Rejection PTAS

来源：评论

学校读者我要写书评

暂无评论

Online Scheduling on a parallel batch Machine with Delivery Times and Limited Restarts

引用

Journal of the Operations Research Society of China 2022年第1期10卷 113-131页

作者： Hai-Ling Liu Xi-Wen Lu Department of Mathematics East China University of Science and TechnologyShanghai 200237China College of Science Henan University of EngineeringZhengzhou 451191HenanChina

The online scheduling on an unbounded parallel batch machine with delivery times and limited restarts is studied in this ***,online means that jobs arrive over time and the characteristics of a job become known until it *** restarts mean that once a running batch contains at least one restarted job,it cannot be restarted *** goal is to minimize the time by which all jobs have been *** consider a restricted model that the delivery time of each job is no more than its processing *** present a best possible online algorithm with a competitive ratio of 3/2 for the problem.

关键词： Online scheduling parallel batch Limited restart Delivery time

来源：评论

学校读者我要写书评

暂无评论

parallel batch scheduling: Impact of increasing machine capacity

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2022年 108卷 102567-102567页

作者： Xu, Jun Wang, Jun-Qiang Liu, Zhixin Northwestern Polytech Univ Performance Anal Ctr Prod & Operat Syst PacPos Xian 710072 Shaanxi Peoples R China Northwestern Polytech Univ Sch Mech Engn Dept Ind Engn Xian 710072 Shaanxi Peoples R China Univ Michigan Dearborn Coll Business Dept Management Studies 19000 Hubbard Dr Dearborn MI 48126 USA

Scheduling performance naturally improves with increased machine capacity, but the per-unit improvement typically decreases or even keeps unchanged with excessive capacity. We consider parallel batch scheduling on identical machines to minimize the makespan, with and without preemption. The machine capacity is the maximum number of jobs that a machine can process simultaneously. We quantitatively analyze the impact of capacity augmentation on the makespan in the form of increasing machine capacity. Considering machines costs, we need to determine the machine capacity that minimizes the weighted sum of the makespan and capacity costs. First, we obtain an upper bound of the ratio between the minimum makespans of two scheduling problems with different machine capacities. Second, noting the intractability of the scheduling problem without preemption, we analyze the upper bound of the ratio between the obtained makespans by heuristics of two scheduling problems with different machine capacities. Third, for the preemptive case, we develop a polynomial time algorithm to obtain the optimal machine capacity, and also present another polynomial time algorithm to obtain the optimal machine capacity as well as for bounding the approximation ratio of the non-preemptive case. Fourth, we design an approximation algorithm using machine capacity found in the preemptive case to yield a schedule for the non-preemptive case, and analyze the worst case performance ratio of the algorithm. This research provides new insights into performance improvement with increased machine capacity in parallel batch scheduling, and analyzes the trade-off between the makespan and capacity costs. (c) 2021 Elsevier Ltd. All rights reserved.

关键词： Scheduling parallel machines parallel batch Capacity augmentation Approximation algorithm Worst case ratio

来源：评论

学校读者我要写书评

暂无评论

Impact of Machine Capacity Augmentation on the Total Completion Time for parallel batch Machines Scheduling 21

Impact of Machine Capacity Augmentation on the Total Complet...

引用

21st International Conference on Networking, Sensing and Control, ICNSC 2024

作者： Xu, Jun Ao, Junxiang Pan, Xuanru Fan, Guo-Qiang Guangzhou Institute of Technology Xidian University Guangzhou510555 China School of Electro-Mechanical Engineering Xidian University Xi'an710071 China School of Economics and Management Xidian University Xi'an710126 China

ISBN: (纸本)9798350365221

Production scheduling performance can not only be improved by good algorithms but also by resource augmentation. This paper studies identical parallel batch machines scheduling to minimize total completion time with machine capacity augmentation. The parallel batch machine can process multiple jobs as a batch simultaneously. We quantitatively analyze the impact of machine capacity augmentation on total completion time for unit processing time jobs. We derive an upper bound and lower bound of the impact ratio. This research provides new insights into production scheduling performance improvement with machine capacity augmentation. © 2024 IEEE.

关键词： impact analysis machine capacity augmentation parallel batch scheduling

来源：评论

学校读者我要写书评

暂无评论

NEC's approach for parallel processing on mainframe systems (parallel OLTP, parallel batch and parallel SQL)

引用

NEC RESEARCH & DEVELOPMENT 1998年第3期39卷 324-334页

作者： Andoh, M Ogawa, S Anezaki, A Ootaki, M Kuribayashi, K Sano, T NEC Corp Ltd Comp Software Div 1 Tokyo Japan NEC Corp Ltd Middle Software Div Tokyo Japan

NEC's "parallel ACOS" series has realized high cost/performance mainframes using highly paralleled TCMP (Tightly Coupled Multiprocessor) which consists of a multiple number of one-chip-CMOS (Complementary Metal Oxide Semiconductor)-processors and make it possible to connect more than eight processors. "ACOS-4/XVP PX," NEC's operating system of mainframe utilizes this new hardware technology and introduces parallel processing to the business application areas on mainframe (including online transaction processing, batch processing, and database processing). It also realizes substantial reductions in the turnaround time and response time, as well as to make extensive improvements in the throughput, scalability, and fault tolerant feature. This paper describes the structures and characteristics of parallel processing on online transaction processing (parallel OLTP: Online Transaction Processing), batch processing (parallel batch), and database processing (parallel SQL: Structured Query Language).

关键词： ACOS-4 XVP PX parallel OLTP (Online Transaction Processing) parallel batch parallel SQL (Structured Query Language) VIS II (Versatile Information System II) OLF/TP-TD (Open Link Facilities Transaction Processing Transaction Distributor) TD-F (Transaction Distributor for FNP) JES-PX (Job Entry System parallel Extended) JOB-PX/ANALYZER RIQS II (Relational Information Query System II)

来源：评论

学校读者我要写书评

暂无评论

An Online Scheduling Problem on a Drop-Line parallel batch Machine with Delivery Times and Limited Restart

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2021年第6期38卷 2150011-2150011页

作者： Liu, Hailing Lu, Xiwen East China Univ Sci & Technol Dept Math Shanghai 200237 Peoples R China Henan Univ Engn Coll Sci Zhengzhou 451191 Henan Peoples R China

This paper studies online scheduling on an unbounded drop-line parallel batch machine with delivery times and limited restarts. A drop-line parallel batch machine is a system that can process some jobs simultaneously as a batch. Jobs in a batch have the same starting time and the completion time of a job is equal to its starting time plus its processing time. Limited restarts mean that a running batch containing at least one restarted job cannot be restarted again. The objective is to minimize the time by which all jobs have been delivered. We prove that any online algorithm has a competitive ratio of at least 1 + alpha, where alpha(alpha approximate to 0.5188) is the positive solution of the equation x(x + x(2) + x(3) + 1) = 1. We provide a best possible (1 + alpha)-competitive online algorithm for the problem. Furthermore, we study the restricted problem with small delivery times and provide a best possible online algorithm with a competitive ratio of 3/2.

关键词： Online scheduling drop-line parallel batch limited restart delivery

来源：评论

学校读者我要写书评

暂无评论

RESEARCH ON THE parallel-batch SCHEDULING WITH LINEARLY LOOKAHEAD MODEL

引用

JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION 2021年第6期17卷 3551-3558页

作者： Jiao, Chengwen Feng, Qi Zhongyuan Univ Technol Coll Sci Zhengzhou 450007 Henan Peoples R China

In this paper, we consider the new online scheduling model with linear lookahead intervals, which has the character that at any time t, one can foresee the jobs that will coming in the time interval (t, lambda t+beta] with lambda >= 1, beta >= 0. We consider online scheduling of unit length jobs on m identical parallel-batch machines under this new lookahead model to minimize the maximum flowtime and the makespan, respectively. We give some lower bounds for these problems with the batch capacity b = infinity and b < infinity, respectively. And for the bounded model to minimize makespan, we give an online algorithm with competitive ratio 1 + alpha for 1 <= lambda < 4/3, 0 <= beta <= 4-3 lambda/6 and 3/2 for lambda >= 1, 0 <= beta < 1, where alpha is the positive root of lambda alpha(2) + (lambda + beta)alpha + beta -1 = 0. The online algorithm is best possible when 1 <= lambda < 4/3, 0 <= beta <= 4-3 lambda/6.

关键词： Online scheduling parallel batch linearly lookahead makespan maximum flowtime competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Single machine parallel-batch scheduling with deteriorating jobs

引用

THEORETICAL COMPUTER SCIENCE 2009年第8-10期410卷 830-836页

作者： Qi, Xianglai Zhou, Shiguo Yuan, Jinjiang Zhengzhou Univ Dept Math Zhengzhou 450052 Henan Peoples R China

We consider several single machine parallel-batch scheduling problems in which the processing time of a job is a linear function of its starting time. We give a polynomial-time algorithm for minimizing the maximum cost, an O(n(5)) time algorithm for minimizing the number of tardy jobs, and an O(n(2)) time algorithm for minimizing the total weighted completion time. Furthermore, we prove that the problem for minimizing the weighted number of tardy jobs is binary NP-hard. (C) 2009 Published by Elsevier B.V.

关键词： Scheduling parallel batch Deteriorating jobs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：