Single-machine scheduling with deteriorating jobs under a series-parallel graph constraint

Ji Bo Wang; Chi To Ng; Edwin Tai Chiu Cheng

doi:10.1016/j.cor.2006.12.026

Single-machine scheduling with deteriorating jobs under a series-parallel graph constraint

Ji Bo Wang, Chi To Ng, Edwin Tai Chiu Cheng

Research output: Journal article publication › Journal article › Academic research › peer-review

67 Citations (Scopus)

Abstract

This paper considers single-machine scheduling problems with deteriorating jobs, i.e., jobs whose processing times are an increasing function of their starting times. In addition, the jobs are related by a series-parallel graph. It is shown that for the general linear problem to minimize the makespan, polynomial algorithms exist. It is also shown that for the proportional linear problem of minimization of the total weighted completion time, polynomial algorithms exist, too.

Original language	English
Pages (from-to)	2684-2693
Number of pages	10
Journal	Computers and Operations Research
Volume	35
Issue number	8
DOIs	https://doi.org/10.1016/j.cor.2006.12.026
Publication status	Published - 1 Aug 2008

Keywords

Deteriorating jobs
Makespan
Scheduling
Series-parallel graph
Single machine
Total weighted completion time

ASJC Scopus subject areas

Information Systems and Management
Management Science and Operations Research
Applied Mathematics
Modelling and Simulation
Transportation

More information

10.1016/j.cor.2006.12.026

http://hdl.handle.net/10397/1266

Cite this

@article{f1fab8c7e70e48709fd41f5cbf999098,

title = "Single-machine scheduling with deteriorating jobs under a series-parallel graph constraint",

abstract = "This paper considers single-machine scheduling problems with deteriorating jobs, i.e., jobs whose processing times are an increasing function of their starting times. In addition, the jobs are related by a series-parallel graph. It is shown that for the general linear problem to minimize the makespan, polynomial algorithms exist. It is also shown that for the proportional linear problem of minimization of the total weighted completion time, polynomial algorithms exist, too.",

keywords = "Deteriorating jobs, Makespan, Scheduling, Series-parallel graph, Single machine, Total weighted completion time",

author = "Wang, {Ji Bo} and Ng, {Chi To} and Cheng, {Edwin Tai Chiu}",

year = "2008",

month = aug,

day = "1",

doi = "10.1016/j.cor.2006.12.026",

language = "English",

volume = "35",

pages = "2684--2693",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier Ltd",

number = "8",

}

TY - JOUR

T1 - Single-machine scheduling with deteriorating jobs under a series-parallel graph constraint

AU - Wang, Ji Bo

AU - Ng, Chi To

AU - Cheng, Edwin Tai Chiu

PY - 2008/8/1

Y1 - 2008/8/1

N2 - This paper considers single-machine scheduling problems with deteriorating jobs, i.e., jobs whose processing times are an increasing function of their starting times. In addition, the jobs are related by a series-parallel graph. It is shown that for the general linear problem to minimize the makespan, polynomial algorithms exist. It is also shown that for the proportional linear problem of minimization of the total weighted completion time, polynomial algorithms exist, too.

AB - This paper considers single-machine scheduling problems with deteriorating jobs, i.e., jobs whose processing times are an increasing function of their starting times. In addition, the jobs are related by a series-parallel graph. It is shown that for the general linear problem to minimize the makespan, polynomial algorithms exist. It is also shown that for the proportional linear problem of minimization of the total weighted completion time, polynomial algorithms exist, too.

KW - Deteriorating jobs

KW - Makespan

KW - Scheduling

KW - Series-parallel graph

KW - Single machine

KW - Total weighted completion time

UR - http://www.scopus.com/inward/record.url?scp=36849012070&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2006.12.026

DO - 10.1016/j.cor.2006.12.026

M3 - Journal article

SN - 0305-0548

VL - 35

SP - 2684

EP - 2693

JO - Computers and Operations Research

JF - Computers and Operations Research

IS - 8

ER -

Single-machine scheduling with deteriorating jobs under a series-parallel graph constraint

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this