Scheduling Simple Linear Deteriorating Jobs with Rejection
Joint Authors
Source
Mathematical Problems in Engineering
Issue
Vol. 2014, Issue 2014 (31 Dec. 2014), pp.1-7, 7 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2014-07-14
Country of Publication
Egypt
No. of Pages
7
Main Subjects
Abstract EN
We consider the problems of scheduling deteriorating jobs with release dates on a single machine (parallel machines) and jobs can be rejected by paying penalties.
The processing time of a job is a simple linear increasing function of its starting time.
For a single machine model, the objective is to minimize the maximum lateness of the accepted jobs plus the total penalty of the rejected jobs.
We show that the problem is NP-hard in the strong sense and presents a fully polynomial time approximation scheme to solve it when all jobs have agreeable release dates and due dates.
For parallel-machine model, the objective is to minimize the maximum delivery completion time of the accepted jobs plus the total penalty of the rejected jobs.
When the jobs have identical release dates, we first propose a fully polynomial time approximation scheme to solve it.
Then, we present a heuristic algorithm for the case where all jobs have to be accepted and evaluate its efficiency by computational experiments.
American Psychological Association (APA)
Zou, Juan& Zhang, Yuzhong. 2014. Scheduling Simple Linear Deteriorating Jobs with Rejection. Mathematical Problems in Engineering،Vol. 2014, no. 2014, pp.1-7.
https://search.emarefa.net/detail/BIM-451489
Modern Language Association (MLA)
Zou, Juan& Zhang, Yuzhong. Scheduling Simple Linear Deteriorating Jobs with Rejection. Mathematical Problems in Engineering No. 2014 (2014), pp.1-7.
https://search.emarefa.net/detail/BIM-451489
American Medical Association (AMA)
Zou, Juan& Zhang, Yuzhong. Scheduling Simple Linear Deteriorating Jobs with Rejection. Mathematical Problems in Engineering. 2014. Vol. 2014, no. 2014, pp.1-7.
https://search.emarefa.net/detail/BIM-451489
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-451489