Two-machine open shop problem with controllable processing times

Edwin Tai Chiu Cheng; Natalia V. Shakhlevich

doi:10.1016/j.disopt.2006.10.010

Two-machine open shop problem with controllable processing times

Edwin Tai Chiu Cheng, Natalia V. Shakhlevich

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

10 Citations (Scopus)

Abstract

We consider a two-machine open shop problem in which the job processing times are controllable and can be compressed while incurring additional costs. We show that the problem of minimizing a linear compression cost function for a given upper bound on the makespan can be solved in O (n) time. For the bicriteria problem of minimizing the makespan and compression cost, we propose an O (n log n) algorithm that finds all breakpoints of the efficient frontier.

Original language	English
Pages (from-to)	175-184
Number of pages	10
Journal	Discrete Optimization
Volume	4
Issue number	2
DOIs	https://doi.org/10.1016/j.disopt.2006.10.010
Publication status	Published - 1 Jun 2007

Keywords

Controllable processing times
Knapsack problem
Open shop scheduling
Resource allocation problem

ASJC Scopus subject areas

Theoretical Computer Science
Computational Theory and Mathematics
Applied Mathematics

More information

10.1016/j.disopt.2006.10.010

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

Cite this

@article{54028edea0fc46fd9e8cdb69ac35863c,

title = "Two-machine open shop problem with controllable processing times",

abstract = "We consider a two-machine open shop problem in which the job processing times are controllable and can be compressed while incurring additional costs. We show that the problem of minimizing a linear compression cost function for a given upper bound on the makespan can be solved in O (n) time. For the bicriteria problem of minimizing the makespan and compression cost, we propose an O (n log n) algorithm that finds all breakpoints of the efficient frontier.",

keywords = "Controllable processing times, Knapsack problem, Open shop scheduling, Resource allocation problem",

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

year = "2007",

month = jun,

day = "1",

doi = "10.1016/j.disopt.2006.10.010",

language = "English",

volume = "4",

pages = "175--184",

journal = "Discrete Optimization",

issn = "1572-5286",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Two-machine open shop problem with controllable processing times

AU - Cheng, Edwin Tai Chiu

AU - Shakhlevich, Natalia V.

PY - 2007/6/1

Y1 - 2007/6/1

N2 - We consider a two-machine open shop problem in which the job processing times are controllable and can be compressed while incurring additional costs. We show that the problem of minimizing a linear compression cost function for a given upper bound on the makespan can be solved in O (n) time. For the bicriteria problem of minimizing the makespan and compression cost, we propose an O (n log n) algorithm that finds all breakpoints of the efficient frontier.

AB - We consider a two-machine open shop problem in which the job processing times are controllable and can be compressed while incurring additional costs. We show that the problem of minimizing a linear compression cost function for a given upper bound on the makespan can be solved in O (n) time. For the bicriteria problem of minimizing the makespan and compression cost, we propose an O (n log n) algorithm that finds all breakpoints of the efficient frontier.

KW - Controllable processing times

KW - Knapsack problem

KW - Open shop scheduling

KW - Resource allocation problem

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

U2 - 10.1016/j.disopt.2006.10.010

DO - 10.1016/j.disopt.2006.10.010

M3 - Journal article

SN - 1572-5286

VL - 4

SP - 175

EP - 184

JO - Discrete Optimization

JF - Discrete Optimization

IS - 2

ER -

Two-machine open shop problem with controllable processing times

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this