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

parallel-batch scheduling with deterioration and rejection on a single machine

Applied Mathematics(A Journal of Chinese Universities) 2020年第2期35卷 141-156页

作者： LI Da-wei LU Xi-wen School of Science East China University of Science and TechnologyShanghai 200237China.

The single machine parallel-batch scheduling with deteriorating jobs and rejection is considered in this paper.A job is either rejected,in which a rejection penalty should be paid,or accepted and processed on the *** job’s processing time is an increasing linear function of its starting *** machine can process any number of jobs simultaneously as a *** processing time of a batch is equal to the largest processing time of the jobs in the *** objectives are to minimize the makespan and the total weighted completion time,respectively,under the condition that the total rejection penalty cannot exceed a given upper bound *** show that both problems are NP-complete and present dynamic programming algorithms and fully polynomial time approximation schemes(FPTASs)for the considered problems.

关键词： parallel-batch scheduling rejection deterioration FPTAS NP-complete

来源：评论

学校读者我要写书评

暂无评论

parallel-batch scheduling With Deterioration and Group Technology

引用

IEEE ACCESS 2019年 7卷 119082-119086页

作者： Miao, Cuixia Qufu Normal Univ Sch Math Sci Qufu 273165 Shandong Peoples R China

parallel-batch scheduling with deterioration and group technology is a modern scheduling model, in which the jobs are classified into groups by the similar production requirements, and setup time, which may be fixed or deterioration function of the starting time, is required between jobs of different groups. We consider this scheduling to minimize the makespan in this paper. Based on Fully batching Longest Deteriorating Rate, we show that our two single-machine scheduling problems are solved in polynomial time. Procedure Partition (A, F, rho) is useful for designing algorithm in combinational optimization. We use this procedure to present fully polynomial time approximation schemes for our two parallel-machine scheduling problems, which is the best algorithm as its' objective value can be fully close to the optimal value.

关键词： parallel-batch scheduling deterioration group technology fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

The unbounded parallel-batch scheduling with rejection

引用

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY 2012年第3期63卷 293-298页

作者： Zhang, L. Q. Lu, L. F. Ng, C. T. Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China Zhengzhou Univ Zhengzhou Henan Peoples R China

In this paper, we consider the unbounded parallel-batch scheduling with rejection. A job is either rejected, in which case a certain penalty has to be paid, or accepted and processed in batches on a machine. The processing time of a batch is defined as the longest processing time of the jobs contained in it. Four problems are considered: (1) to minimize the sum of the total completion time of the accepted jobs and the total rejection penalty of the rejected jobs;(2) to minimize the total completion time of the accepted jobs subject to an upper bound on the total rejection penalty of the rejected jobs;(3) to minimize the total rejection penalty of the rejected jobs subject to an upper bound on the total completion time of the accepted jobs;(4) to find the set of all the Pareto optimal schedules. We provide a polynomial-time algorithm for the first problem. Furthermore, we show that all the other three problems are binary NP-hard and present a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme for them. Journal of the Operational Research Society (2012) 63, 293-298. doi:10.1057/jors.2011.31 Published online 4 May 2011

关键词： parallel-batch scheduling rejection penalty polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Unbounded parallel-batch scheduling with drop-line tasks

引用

JOURNAL OF scheduling 2019年第4期22卷 449-463页

作者： Gao, Yuan Yuan, Jinjiang Wei, Zhigang Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Henan Peoples R China Zhengzhou XindaJiean Informat Technol Co Ltd Zhengzhou 450001 Henan Peoples R China

In this paper, we study unbounded parallel-batch scheduling with drop-line tasks to minimize a regular objective function, where by drop-line tasks we mean that the completion time of each task (job) is equal to the sum of the starting time of the batch containing the task and the processing time of the task. In the problems considered in this paper, we assume that the tasks have individual release dates and the general regular objective function to be minimized is either of the sum-form or of the max-form. We then study the computational complexity of these problems on an unbounded parallel-batch processor. We show that (i) the problems are binary NP-hard and are solvable in pseudo-polynomial times, and (ii) when the number of processing times or release dates is a constant, the problems are solvable in polynomial times. We also point out some consequences of approximation algorithms.

关键词： parallel-batch scheduling Drop-line tasks Release dates Computational complexity

来源：评论

学校读者我要写书评

暂无评论

Unbounded parallel-batch scheduling with family jobs and delivery coordination

引用

INFORMATION PROCESSING LETTERS 2011年第12期111卷 575-582页

作者： Li, Shisheng Yuan, Jinjiang Fan, Baoqiang Zhengzhou Univ Dept Math Zhengzhou 450001 Peoples R China Ludong Univ Dept Math & Informat Yantai 264025 Peoples R China

We study a scheduling problem that integrates parallel-batch production with family jobs and job delivery at the same time. The jobs are first processed on an unbounded parallel-batch machine and then delivered in batches to their specified customers by a transportation vehicle. We assume that jobs from different families (customers) cannot be processed together by the batch machine and also transported together by the vehicle. The objective is to minimize the time when the vehicle finishes delivering the last delivery batch to its customer and returns to the machine. We first show that the problem is NP-hard, and then propose for it a heuristic algorithm with a worst-case performance ratio of 3/2. (C) 2011 Elsevier B.V. All rights reserved.

关键词： parallel-batch scheduling Family jobs batch delivery Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

A note on unbounded parallel-batch scheduling

引用

INFORMATION PROCESSING LETTERS 2015年第12期115卷 969-974页

作者： Geng, Zhichao Yuan, Jinjiang Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Henan Peoples R China

This paper revisits the scheduling problem on an unbounded parallel batch machine for minimizing a maximum cost f(max). It was reported in the literature that the decision version of the problem is solvable in O (n(2) + n log P) time, where n is the number of jobs and P is the total processing time of jobs. This implies that the optimization version for minimizing fmax can be solved in weakly polynomial time. But a strongly polynomial-time algorithm has not been provided for this problem. In this paper, we present an O (n(4))-time algorithm for the Pareto optimization problem for minimizing C-max and f(max), where Cam is the maximum completion time of jobs. Consequently, the problem for minimizing fmax can also be solved in O (n(4)) time. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Analysis of algorithm parallel-batch scheduling Maximum cost Strongly polynomial time Pareto optimization

来源：评论

学校读者我要写书评

暂无评论

A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan

引用

JOURNAL OF scheduling 2011年第4期14卷 361-369页

作者： Yuan, Jinjiang Fu, Ruyan Ng, C. T. Cheng, T. C. E. Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China Zhengzhou Univ Dept Math Zhengzhou 450001 Henan Peoples R China China Univ Min & Technol Sch Sci Xuzhou 221116 Jiangsu Peoples R China

We consider online scheduling with restarts in an unbounded parallel-batch processing system to minimize the makespan. By online we mean that jobs arrive over time and all the information on a job is unknown before its arrival time (release date) and restart means that a running batch may be interrupted, losing all the work done on it, and the jobs in the interrupted batch are released and become independently unscheduled jobs. It is known in the literature that the considered problem has no online algorithm with a competitive ratio less than (5 - root 5)/2. We give an online algorithm for the considered problem with a competitive ratio (5 - root 5)/2 approximate to 1.382.

关键词： parallel-batch scheduling Online algorithm Restart Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

Bounded parallel-batch scheduling on single and multi machines for deteriorating jobs

引用

INFORMATION PROCESSING LETTERS 2011年第16期111卷 798-803页

作者： Miao, Cuixia Zhang, Yuzhong Cao, Zhigang Qufu Normal Univ Sch Math Sci Qufu 273165 Shandong Peoples R China Qufu Normal Univ Sch Management Rizhao 276826 Shandong Peoples R China CAS Key Lab Management Decis & Informat Syst AMSS Beijing 100190 Peoples R China

We consider the bounded parallel-batch scheduling problem in which the processing time of a job is a simple linear function of its starting time. The objective is to minimize the makespan. When the jobs have identical release dates, we present an optimal algorithm for the single-machine problem and an fully polynomial-time approximation scheme for the parallel-machine problem. When the jobs have distinct release dates, we show that the single-machine problem is NP-hard and present an optimal algorithm for one special case. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Analysis of algorithms parallel-batch scheduling Deteriorating job NP-hard Fully polynomial time approximation scheme (FPTAS)

来源：评论

学校读者我要写书评

暂无评论

Online parallel-batch scheduling to minimize total weighted completion time on single unbounded machine

引用

INFORMATION PROCESSING LETTERS 2016年第8期116卷 526-531页

作者： Fang, Yang Lu, Xiwen Shanghai Zhenhua Heavy Ind Co Ltd Shanghai Peoples R China Shanghai Jiao Tong Univ Antai Coll Econ & Management Shanghai 200030 Peoples R China E China Univ Sci & Technol Sch Sci Dept Math Shanghai 200237 Peoples R China

The online parallel-batch scheduling problem on single unbounded machine to minimize total weighted job completion time is studied. For the general case of processing time, we give an online algorithm with competitive ratio root 5 + 1. When all jobs have identical processing times, we provide an optimal online algorithm. (C) 2016 Elsevier B.V. All rights reserved.

关键词： parallel-batch scheduling Online algorithm Analysis of algorithms Unbounded machine Total weighted completion time

来源：评论

学校读者我要写书评

暂无评论

Unbounded parallel-batch scheduling under agreeable release and processing to minimize total weighted number of tardy jobs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2019年第3期38卷 698-711页

作者： Gao, Yuan Yuan, Jinjiang Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Henan Peoples R China

We study the unbounded parallel-batch scheduling problem with the jobs having agreeable release dates and processing times to minimize the total weighted number of tardy jobs. In this problem, we consider two types of jobs: batch jobs and drop-line jobs. For batch jobs, the completion time of a job is given by the completion time of the batch containing this job. For drop-line jobs, the completion time of a job is given by the starting time of the batch containing this job plus the processing time of this job. For both of batch jobs and drop-line jobs, we show that (1) the problems are binary NP-hard, (2) the problems are solvable in pseudo-polynomial times, and when the number of weights is a constant, the problems are solvable in polynomial times, and (3) the problems have a fully polynomial-time approximation scheme.

关键词： parallel-batch scheduling Release dates Drop-line jobs Polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：