Affiliation: | 1.College of Information and Management Science,Henan Agricultural University,Zhengzhou,People’s Republic of China;2.School of Mathematics and Statistics,Zhengzhou University,Zhengzhou,People’s Republic of China |
Abstract: | In this paper, we consider the parallel-machine scheduling problem with release dates and rejection. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on one of the m identical parallel machines. The objective is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. When m is a fixed constant, we provide a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme for the problem. When m is arbitrary, we present a 2-approximation algorithm for the problem. |