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

管理学院

Tongji University
Xi'an Jiaotong University
Ecole Centrale Paris

科研成果: 期刊稿件 › 文章 › 同行评审

3 引用（Scopus）

摘要

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.

源语言	英语
文章编号	1250032
期刊	Discrete Mathematics, Algorithms and Applications
卷	4
期	2
DOI	https://doi.org/10.1142/S1793830912500322
出版状态	已出版 - 1 6月 2012

访问文件

10.1142/S1793830912500322

其它文件与链接

链接到 Scopus 的出版物

引用此

@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

摘要

访问文件

其它文件与链接

学术指纹

引用此