An FPTAS for scheduling jobs with piecewise linear decreasing processing times to minimize makespan

Min Ji; Edwin Tai Chiu Cheng

doi:10.1016/j.ipl.2006.11.014

An FPTAS for scheduling jobs with piecewise linear decreasing processing times to minimize makespan

Min Ji, Edwin Tai Chiu Cheng

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

18 Citations (Scopus)

Abstract

We study the problems of scheduling a set of nonpreemptive jobs on a single machine and identical parallel machines, where the processing time of a job is a piecewise linear nonincreasing function of its start time. The objective is to minimize makespan. We first give a fully polynomial-time approximation scheme (FPTAS) for the case with a single machine. We then generalize the result to the case with m identical machines.

Original language	English
Pages (from-to)	41-47
Number of pages	7
Journal	Information Processing Letters
Volume	102
Issue number	2-3
DOIs	https://doi.org/10.1016/j.ipl.2006.11.014
Publication status	Published - 30 Apr 2007

Keywords

Approximation algorithms
Machine scheduling
Makespan
Start time-dependent processing times

ASJC Scopus subject areas

Computational Theory and Mathematics

More information

10.1016/j.ipl.2006.11.014

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

Cite this

@article{66264790d36f48c5b394ef9da9f6c5e9,

title = "An FPTAS for scheduling jobs with piecewise linear decreasing processing times to minimize makespan",

abstract = "We study the problems of scheduling a set of nonpreemptive jobs on a single machine and identical parallel machines, where the processing time of a job is a piecewise linear nonincreasing function of its start time. The objective is to minimize makespan. We first give a fully polynomial-time approximation scheme (FPTAS) for the case with a single machine. We then generalize the result to the case with m identical machines.",

keywords = "Approximation algorithms, Machine scheduling, Makespan, Start time-dependent processing times",

author = "Min Ji and Cheng, {Edwin Tai Chiu}",

year = "2007",

month = apr,

day = "30",

doi = "10.1016/j.ipl.2006.11.014",

language = "English",

volume = "102",

pages = "41--47",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "2-3",

}

TY - JOUR

T1 - An FPTAS for scheduling jobs with piecewise linear decreasing processing times to minimize makespan

AU - Ji, Min

AU - Cheng, Edwin Tai Chiu

PY - 2007/4/30

Y1 - 2007/4/30

N2 - We study the problems of scheduling a set of nonpreemptive jobs on a single machine and identical parallel machines, where the processing time of a job is a piecewise linear nonincreasing function of its start time. The objective is to minimize makespan. We first give a fully polynomial-time approximation scheme (FPTAS) for the case with a single machine. We then generalize the result to the case with m identical machines.

AB - We study the problems of scheduling a set of nonpreemptive jobs on a single machine and identical parallel machines, where the processing time of a job is a piecewise linear nonincreasing function of its start time. The objective is to minimize makespan. We first give a fully polynomial-time approximation scheme (FPTAS) for the case with a single machine. We then generalize the result to the case with m identical machines.

KW - Approximation algorithms

KW - Machine scheduling

KW - Makespan

KW - Start time-dependent processing times

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

U2 - 10.1016/j.ipl.2006.11.014

DO - 10.1016/j.ipl.2006.11.014

M3 - Journal article

SN - 0020-0190

VL - 102

SP - 41

EP - 47

JO - Information Processing Letters

JF - Information Processing Letters

IS - 2-3

ER -

An FPTAS for scheduling jobs with piecewise linear decreasing processing times to minimize makespan

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this