Parallel-machine scheduling with release dates and rejection |
| |
Authors: | Liqi?Zhang Email author" target="_blank">Lingfa?LuEmail author |
| |
Institution: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|