Scheduling deteriorating jobs on a single machine with release times and rejection

Ming Liu; Feifeng Zheng; Chengbin Chu; Yinfeng Xu

doi:10.1142/S1793830912500322

Scheduling deteriorating jobs on a single machine with release times and rejection

Ming Liu
, Feifeng Zheng
, Chengbin Chu
, Yinfeng Xu

School of Management

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

This paper considers scheduling deteriorating jobs on a single machine with release times and rejection. Deteriorating job means that its actual processing time is a increasing function on its execution starting time. In this situation, jobs can be rejected by paying penalties. Each job is associated with a release time. The objective is to minimize the makespan plus the total penalty incurred by rejecting jobs. We present two dynamic programming algorithms and then design an FPTAS for the considered problem.

Original language	English
Article number	1250032
Journal	Discrete Mathematics, Algorithms and Applications
Volume	4
Issue number	2
DOIs	https://doi.org/10.1142/S1793830912500322
State	Published - 1 Jun 2012

Keywords

Deteriorating job
Rejection
Release times
Scheduling

Access to Document

10.1142/S1793830912500322

Cite this

@article{aa7eb1a1cdfa436c9d6b9064dce594de,

title = "Scheduling deteriorating jobs on a single machine with release times and rejection",

abstract = "This paper considers scheduling deteriorating jobs on a single machine with release times and rejection. Deteriorating job means that its actual processing time is a increasing function on its execution starting time. In this situation, jobs can be rejected by paying penalties. Each job is associated with a release time. The objective is to minimize the makespan plus the total penalty incurred by rejecting jobs. We present two dynamic programming algorithms and then design an FPTAS for the considered problem.",

keywords = "Deteriorating job, Rejection, Release times, Scheduling",

author = "Ming Liu and Feifeng Zheng and Chengbin Chu and Yinfeng Xu",

note = "Publisher Copyright: {\textcopyright} 2012 World Scientific Publishing Company.",

year = "2012",

month = jun,

day = "1",

doi = "10.1142/S1793830912500322",

language = "英语",

volume = "4",

journal = "Discrete Mathematics, Algorithms and Applications",

issn = "1793-8309",

publisher = "World Scientific",

number = "2",

}

TY - JOUR

T1 - Scheduling deteriorating jobs on a single machine with release times and rejection

AU - Liu, Ming

AU - Zheng, Feifeng

AU - Chu, Chengbin

AU - Xu, Yinfeng

PY - 2012/6/1

Y1 - 2012/6/1

N2 - This paper considers scheduling deteriorating jobs on a single machine with release times and rejection. Deteriorating job means that its actual processing time is a increasing function on its execution starting time. In this situation, jobs can be rejected by paying penalties. Each job is associated with a release time. The objective is to minimize the makespan plus the total penalty incurred by rejecting jobs. We present two dynamic programming algorithms and then design an FPTAS for the considered problem.

AB - This paper considers scheduling deteriorating jobs on a single machine with release times and rejection. Deteriorating job means that its actual processing time is a increasing function on its execution starting time. In this situation, jobs can be rejected by paying penalties. Each job is associated with a release time. The objective is to minimize the makespan plus the total penalty incurred by rejecting jobs. We present two dynamic programming algorithms and then design an FPTAS for the considered problem.

KW - Deteriorating job

KW - Rejection

KW - Release times

KW - Scheduling

UR - https://www.scopus.com/pages/publications/85028229818

U2 - 10.1142/S1793830912500322

DO - 10.1142/S1793830912500322

M3 - 文章

AN - SCOPUS:85028229818

SN - 1793-8309

VL - 4

JO - Discrete Mathematics, Algorithms and Applications

JF - Discrete Mathematics, Algorithms and Applications

IS - 2

M1 - 1250032

ER -

Scheduling deteriorating jobs on a single machine with release times and rejection

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this