Parallel-machine scheduling with release dates and rejection

Liqi Zhang and Lingfa Lu ()
Additional contact information
Liqi Zhang: Henan Agricultural University
Lingfa Lu: Zhengzhou University

4OR, 2016, vol. 14, issue 2, No 4, 165-172

Abstract: 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: Scheduling; Rejection penalty; Dynamic programming; FPTAS; 90B35 (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (19)

Downloads: (external link)
http://link.springer.com/10.1007/s10288-016-0304-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:aqjoor:v:14:y:2016:i:2:d:10.1007_s10288-016-0304-4

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-016-0304-4

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().