Paper Info
Title
Scheduling with Rejection to Minimize the Makespan
Abstract
In this paper, we consider the scheduling with rejection. The objective functions are to minimize the maximum completion time of the processed ones when the total compression cost is given. Firstly, we prove that the problem 1|rej | C max /TCP is NP-hard, which implying that P m |rej | C max /TCP , 1 |rej , r j |C max /TCP , 1 |rej , on *** line |C max /TCP are all NP-hard. Secondly, for problem P m |rej | C max /TCP , we design a pseudopolynomial time dynamic programming algorithm that solves it exactly and an FPTAS (full polynomial time approximation scheme) when m is a constant. We also design a pseudopolynomial time dynamic programming algorithm and an FPTAS for the case of non-identical job arrival problem 1 |rej , r j |C max /TCP . In the end, we consider the on-line problem 1 |rej , on *** line |C max /TCP and prove that there doesn't exist any on-line algorithm with a constant competitive ratio for it, even if the jobs only have two different release times.
Year
DOI
Venue
2009
10.1007/978-3-642-02026-1_39
COCOA
Keywords
Field
DocType
non-identical job arrival problem,pseudopolynomial time,problem p m,c max,maximum completion time,p m,on-line problem,different release time,dynamic programming algorithm,full polynomial time approximation,polynomial time approximation scheme,objective function,competitive ratio
Dynamic programming,Discrete mathematics,Approximation algorithm,Combinatorics,Job shop scheduling,Scheduling (computing),Polynomial-time approximation scheme,Mathematics,Competitive analysis
Conference
Volume
ISSN
Citations 
5573
0302-9743
8
PageRank 
References 
Authors
0.56
9
3
Name
Order
Citations
PageRank
Yuzhong Zhang125225.71
Jianfeng Ren229116.97
Chengfei Wang3150.99