Scheduling Simple Linear Deteriorating Jobs with Rejection

Juan Zou and Yuzhong Zhang

Mathematical Problems in Engineering, 2014, vol. 2014, 1-7

Abstract:

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.

Date: 2014
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2014/170475.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2014/170475.xml (text/xml)

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:hin:jnlmpe:170475

DOI: 10.1155/2014/170475

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().