Parallel Batch Scheduling of Deteriorating Jobs with Release Dates and Rejection
Joint Authors
Source
Issue
Vol. 2014, Issue 2014 (31 Dec. 2014), pp.1-7, 7 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2014-07-20
Country of Publication
Egypt
No. of Pages
7
Main Subjects
Medicine
Information Technology and Computer Science
Abstract EN
We consider the unbounded parallel batch scheduling with deterioration, release dates, and rejection.
Each job is either accepted and processed on a single batching machine, or rejected by paying penalties.
The processing time of a job is a simple linear increasing function of its starting time.
The objective is to minimize the sum of the makespan of the accepted jobs and the total penalty ofthe rejected jobs.
First, we show that the problem is NP-hard in the ordinary sense.
Then, we present two pseudopolynomial time algorithms and a fully polynomial-time approximation scheme to solve this problem.
Furthermore, we provide an optimal O ( n log n ) time algorithm for the case where jobs have identical release dates.
American Psychological Association (APA)
Zou, Juan& Miao, Cuixia. 2014. Parallel Batch Scheduling of Deteriorating Jobs with Release Dates and Rejection. The Scientific World Journal،Vol. 2014, no. 2014, pp.1-7.
https://search.emarefa.net/detail/BIM-1048995
Modern Language Association (MLA)
Zou, Juan& Miao, Cuixia. Parallel Batch Scheduling of Deteriorating Jobs with Release Dates and Rejection. The Scientific World Journal No. 2014 (2014), pp.1-7.
https://search.emarefa.net/detail/BIM-1048995
American Medical Association (AMA)
Zou, Juan& Miao, Cuixia. Parallel Batch Scheduling of Deteriorating Jobs with Release Dates and Rejection. The Scientific World Journal. 2014. Vol. 2014, no. 2014, pp.1-7.
https://search.emarefa.net/detail/BIM-1048995
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1048995