Two-Agent Single Machine Scheduling with Deteriorating Jobs and Rejection

Dawei Li, Ganggang Li, Fangzheng Cheng and Yang Li

Mathematical Problems in Engineering, 2022, vol. 2022, 1-10

Abstract: We consider two two-agent scheduling problems with deteriorating jobs and rejection. Two agents A and B compete for the usage of a single machine. The actual processing time of job JjX is pjX=bjXa+bt, X∈A,B, where bjX is the normal processing time of JjX, a≥0, b≥0 and t denotes the starting time of JjX. A job is either rejected by paying a rejection penalty, or accepted and processed on the machine. The objective is to minimize the sum of the completion time of the accepted A-jobs and total rejection penalty of the rejected A-jobs subject to an upper bound on the sum of the given objective function fB of the accepted B-jobs and total rejection penalty of the rejected B-jobs, where fB∈CmaxB,∑CjB. We give dynamic programming algorithms for them, respectively. When fB=CmaxB, we present a fully polynomial-time approximation scheme (FPTAS) for the case a=0 and b=1. When fB=∑CjB, a fully polynomial-time approximation scheme is also presented.

Date: 2022
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://downloads.hindawi.com/journals/mpe/2022/3565133.pdf (application/pdf)
http://downloads.hindawi.com/journals/mpe/2022/3565133.xml (application/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:3565133

DOI: 10.1155/2022/3565133

Access Statistics for this article

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