Minimizing non-decreasing separable objective functions for the unit-time open shop scheduling problem

Edwin Tai Chiu Cheng; Natalia V. Shakhlevich

doi:10.1016/j.ejor.2004.04.014

Minimizing non-decreasing separable objective functions for the unit-time open shop scheduling problem

Edwin Tai Chiu Cheng, Natalia V. Shakhlevich

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

3 Citations (Scopus)

Abstract

In this paper we study both the non-preemptive and preemptive versions of the popular unit-time open shop scheduling problem. For the set of feasible schedules which satisfy a predetermined order of job completion times, we construct the linear description of the convex hull of the vectors of the job completion times. Based on the properties of the resulting scheduling polyhedron, we show that the problem of constructing an optimal schedule minimizing an arbitrary non-decreasing separable cost function of job completion times is polynomially solvable.

Original language	English
Pages (from-to)	444-456
Number of pages	13
Journal	European Journal of Operational Research
Volume	165
Issue number	2
DOIs	https://doi.org/10.1016/j.ejor.2004.04.014
Publication status	Published - 1 Sept 2005

Keywords

Open shop scheduling
Parallel machine scheduling
Scheduling
Separable non-decreasing function

ASJC Scopus subject areas

Modelling and Simulation
Management Science and Operations Research
Information Systems and Management

More information

10.1016/j.ejor.2004.04.014

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

Cite this

@article{edcd40183e4d4da886fd56b1f6b4871e,

title = "Minimizing non-decreasing separable objective functions for the unit-time open shop scheduling problem",

abstract = "In this paper we study both the non-preemptive and preemptive versions of the popular unit-time open shop scheduling problem. For the set of feasible schedules which satisfy a predetermined order of job completion times, we construct the linear description of the convex hull of the vectors of the job completion times. Based on the properties of the resulting scheduling polyhedron, we show that the problem of constructing an optimal schedule minimizing an arbitrary non-decreasing separable cost function of job completion times is polynomially solvable.",

keywords = "Open shop scheduling, Parallel machine scheduling, Scheduling, Separable non-decreasing function",

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

year = "2005",

month = sep,

day = "1",

doi = "10.1016/j.ejor.2004.04.014",

language = "English",

volume = "165",

pages = "444--456",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - Minimizing non-decreasing separable objective functions for the unit-time open shop scheduling problem

AU - Cheng, Edwin Tai Chiu

AU - Shakhlevich, Natalia V.

PY - 2005/9/1

Y1 - 2005/9/1

N2 - In this paper we study both the non-preemptive and preemptive versions of the popular unit-time open shop scheduling problem. For the set of feasible schedules which satisfy a predetermined order of job completion times, we construct the linear description of the convex hull of the vectors of the job completion times. Based on the properties of the resulting scheduling polyhedron, we show that the problem of constructing an optimal schedule minimizing an arbitrary non-decreasing separable cost function of job completion times is polynomially solvable.

AB - In this paper we study both the non-preemptive and preemptive versions of the popular unit-time open shop scheduling problem. For the set of feasible schedules which satisfy a predetermined order of job completion times, we construct the linear description of the convex hull of the vectors of the job completion times. Based on the properties of the resulting scheduling polyhedron, we show that the problem of constructing an optimal schedule minimizing an arbitrary non-decreasing separable cost function of job completion times is polynomially solvable.

KW - Open shop scheduling

KW - Parallel machine scheduling

KW - Scheduling

KW - Separable non-decreasing function

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

U2 - 10.1016/j.ejor.2004.04.014

DO - 10.1016/j.ejor.2004.04.014

M3 - Journal article

SN - 0377-2217

VL - 165

SP - 444

EP - 456

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 2

ER -

Minimizing non-decreasing separable objective functions for the unit-time open shop scheduling problem

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this