.png){kind=icon}
.png){kind=icon}
Return
Algorithms for Scheduling Problems with Rejection
.png){kind=icon}
OA
AI
DOI：10.26599/TST.2023.9010146.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
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.
Keywords:
Schedules
Approximation algorithms
Job shop scheduling
Costs
Processor scheduling
Heuristic algorithms
Dynamic scheduling
approximation algorithm
dynamic programming
fully polynomial approximation scheme
scheduling
rejection
Journal
T
IF:
3.5
Papers:
987
Citations:
2.5K