Single machine scheduling of unit-time jobs with controllable release dates

Edwin Tai Chiu Cheng; Natalia V. Shakhlevich

doi:10.1023/A:1024826720369

Single machine scheduling of unit-time jobs with controllable release dates

Edwin Tai Chiu Cheng, Natalia V. Shakhlevich

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

4 Citations (Scopus)

Abstract

The paper presents a bicriterion approach to solve the single-machine scheduling problem in which the job release dates can be compressed while incurring additional costs. The two criteria are the makespan and the compression cost. For the case of equal job processing times, an O(n4) algorithm is developed to construct integer Pareto optimal points. We discuss how the algorithm developed can be modified to construct an ε-approximation of noninteger Pareto optimal points. The complexity status of the problem with total weighted completion time criterion is also established.

Original language	English
Pages (from-to)	293-311
Number of pages	19
Journal	Journal of Global Optimization
Volume	27
Issue number	2-3
DOIs	https://doi.org/10.1023/A:1024826720369
Publication status	Published - 1 Nov 2003

Keywords

Controllable release dates
Deterministic
Multiple criteria
Scheduling
Single machine

ASJC Scopus subject areas

Applied Mathematics
Control and Optimization
Management Science and Operations Research
Global and Planetary Change

More information

10.1023/A:1024826720369

Cite this

@article{02c7a7aa4d6a499a9a503faa9142a176,

title = "Single machine scheduling of unit-time jobs with controllable release dates",

abstract = "The paper presents a bicriterion approach to solve the single-machine scheduling problem in which the job release dates can be compressed while incurring additional costs. The two criteria are the makespan and the compression cost. For the case of equal job processing times, an O(n4) algorithm is developed to construct integer Pareto optimal points. We discuss how the algorithm developed can be modified to construct an ε-approximation of noninteger Pareto optimal points. The complexity status of the problem with total weighted completion time criterion is also established.",

keywords = "Controllable release dates, Deterministic, Multiple criteria, Scheduling, Single machine",

author = "Cheng, {Edwin Tai Chiu} and Shakhlevich, {Natalia V.}",

year = "2003",

month = nov,

day = "1",

doi = "10.1023/A:1024826720369",

language = "English",

volume = "27",

pages = "293--311",

journal = "Journal of Global Optimization",

issn = "0925-5001",

publisher = "Springer Netherlands",

number = "2-3",

}

TY - JOUR

T1 - Single machine scheduling of unit-time jobs with controllable release dates

AU - Cheng, Edwin Tai Chiu

AU - Shakhlevich, Natalia V.

PY - 2003/11/1

Y1 - 2003/11/1

N2 - The paper presents a bicriterion approach to solve the single-machine scheduling problem in which the job release dates can be compressed while incurring additional costs. The two criteria are the makespan and the compression cost. For the case of equal job processing times, an O(n4) algorithm is developed to construct integer Pareto optimal points. We discuss how the algorithm developed can be modified to construct an ε-approximation of noninteger Pareto optimal points. The complexity status of the problem with total weighted completion time criterion is also established.

AB - The paper presents a bicriterion approach to solve the single-machine scheduling problem in which the job release dates can be compressed while incurring additional costs. The two criteria are the makespan and the compression cost. For the case of equal job processing times, an O(n4) algorithm is developed to construct integer Pareto optimal points. We discuss how the algorithm developed can be modified to construct an ε-approximation of noninteger Pareto optimal points. The complexity status of the problem with total weighted completion time criterion is also established.

KW - Controllable release dates

KW - Deterministic

KW - Multiple criteria

KW - Scheduling

KW - Single machine

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

U2 - 10.1023/A:1024826720369

DO - 10.1023/A:1024826720369

M3 - Journal article

SN - 0925-5001

VL - 27

SP - 293

EP - 311

JO - Journal of Global Optimization

JF - Journal of Global Optimization

IS - 2-3

ER -

Single machine scheduling of unit-time jobs with controllable release dates

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this