Scheduling Jobs with Piecewise Linear Decreasing Processing Times

Edwin Tai Chiu Cheng; Qing Ding; Mikhail Y. Kovalyov; Aleksander Bachman; Adam Janiak

doi:10.1002/nav.10073

Scheduling Jobs with Piecewise Linear Decreasing Processing Times

Edwin Tai Chiu Cheng, Qing Ding, Mikhail Y. Kovalyov, Aleksander Bachman, Adam Janiak

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

56 Citations (Scopus)

Abstract

We study the problems of scheduling a set of nonpreemptive jobs on a single or multiple machines without idle times where the processing time of a job is a piecewise linear nonincreasing function of its start time. The objectives are the minimization of makespan and minimization of total job completion time. The single machine problems are proved to be NP-hard, and some properties of their optimal solutions are established. A pseudopolynomial time algorithm is constructed for makespan minimization. Several heuristics are derived for both total completion time and makespan minimization. Computational experiments are conducted to evaluate their efficiency. NP-hardness proofs and polynomial time algorithms are presented for some special cases of the parallel machine problems.

Original language	English
Pages (from-to)	531-554
Number of pages	24
Journal	Naval Research Logistics
Volume	50
Issue number	6
DOIs	https://doi.org/10.1002/nav.10073
Publication status	Published - 1 Sept 2003

Keywords

Computational complexity
Machine scheduling
Start time dependent processing times

ASJC Scopus subject areas

Modelling and Simulation
Ocean Engineering
Management Science and Operations Research

More information

10.1002/nav.10073

Cite this

@article{41cc108b6a0a4bab9baadc57c096fd9c,

title = "Scheduling Jobs with Piecewise Linear Decreasing Processing Times",

abstract = "We study the problems of scheduling a set of nonpreemptive jobs on a single or multiple machines without idle times where the processing time of a job is a piecewise linear nonincreasing function of its start time. The objectives are the minimization of makespan and minimization of total job completion time. The single machine problems are proved to be NP-hard, and some properties of their optimal solutions are established. A pseudopolynomial time algorithm is constructed for makespan minimization. Several heuristics are derived for both total completion time and makespan minimization. Computational experiments are conducted to evaluate their efficiency. NP-hardness proofs and polynomial time algorithms are presented for some special cases of the parallel machine problems.",

keywords = "Computational complexity, Machine scheduling, Start time dependent processing times",

author = "Cheng, {Edwin Tai Chiu} and Qing Ding and Kovalyov, {Mikhail Y.} and Aleksander Bachman and Adam Janiak",

year = "2003",

month = sep,

day = "1",

doi = "10.1002/nav.10073",

language = "English",

volume = "50",

pages = "531--554",

journal = "Naval Research Logistics",

issn = "0894-069X",

publisher = "John Wiley & Sons Inc.",

number = "6",

}

TY - JOUR

T1 - Scheduling Jobs with Piecewise Linear Decreasing Processing Times

AU - Cheng, Edwin Tai Chiu

AU - Ding, Qing

AU - Kovalyov, Mikhail Y.

AU - Bachman, Aleksander

AU - Janiak, Adam

PY - 2003/9/1

Y1 - 2003/9/1

N2 - We study the problems of scheduling a set of nonpreemptive jobs on a single or multiple machines without idle times where the processing time of a job is a piecewise linear nonincreasing function of its start time. The objectives are the minimization of makespan and minimization of total job completion time. The single machine problems are proved to be NP-hard, and some properties of their optimal solutions are established. A pseudopolynomial time algorithm is constructed for makespan minimization. Several heuristics are derived for both total completion time and makespan minimization. Computational experiments are conducted to evaluate their efficiency. NP-hardness proofs and polynomial time algorithms are presented for some special cases of the parallel machine problems.

AB - We study the problems of scheduling a set of nonpreemptive jobs on a single or multiple machines without idle times where the processing time of a job is a piecewise linear nonincreasing function of its start time. The objectives are the minimization of makespan and minimization of total job completion time. The single machine problems are proved to be NP-hard, and some properties of their optimal solutions are established. A pseudopolynomial time algorithm is constructed for makespan minimization. Several heuristics are derived for both total completion time and makespan minimization. Computational experiments are conducted to evaluate their efficiency. NP-hardness proofs and polynomial time algorithms are presented for some special cases of the parallel machine problems.

KW - Computational complexity

KW - Machine scheduling

KW - Start time dependent processing times

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

U2 - 10.1002/nav.10073

DO - 10.1002/nav.10073

M3 - Journal article

SN - 0894-069X

VL - 50

SP - 531

EP - 554

JO - Naval Research Logistics

JF - Naval Research Logistics

IS - 6

ER -

Scheduling Jobs with Piecewise Linear Decreasing Processing Times

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this