.png){kind=icon}
返回
Algorithms for Scheduling Problems with Rejection
.png){kind=icon}
OA
AI
DOI：10.26599/TST.2023.9010146.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We study scheduling problems with rejection on parallel-machine. Each job consists of a processing time, a rejection cost, and a release date. The goal is to minimize the makespan of the jobs accepted when the total rejection cost is not larger than a given threshold. Firstly, we verify that these problems are NP-hard. Secondly, for the multiprocessor scheduling problem with rejection, we give a pseudo-polynomial algorithm and two fully polynomial approximation schemes (FPTAS for short) for fixed positive integer m, where m is the number of machines. For the scheduling problem with rejection and the job with non-identical release time on m machines, we also design a pseudo-polynomial algorithm and a fully polynomial approximation scheme when m is a fixed positive integer. We provide an approximation algorithm with the worst case performance 2 for arbitrary positive integer m. Finally, we discuss the online scheduling problem with rejection. We show that even if there are just two distinct arrive times for the jobs, there is not any online algorithm whose competitive ratio is constant for it.
Keyword:
Schedules
Approximation algorithms
Job shop scheduling
Costs
Processor scheduling
Heuristic algorithms
Dynamic scheduling
approximation algorithm
dynamic programming
fully polynomial approximation scheme
scheduling
rejection
期刊
T
IF:
3.5
论文数:
987
被引数:
2.5K
机构
引用论文
.png){kind=icon}
Cavity Preparation and Influence of Restorative Materials on the Prevention of Secondary Caries
PREAI
分享收藏Routing and scheduling optimization for UAV assisted delivery system: A hybrid approach无人机辅助交付系统的路由和调度优化: 一种混合方法
PREAI
分享收藏
查看更多内容