Scheduling jobs with fixed start and end times

Esther M. Arkin; Ellen B. Silverberg

doi:10.1016/0166-218X(87)90037-0

Scheduling jobs with fixed start and end times

Esther M. Arkin
, Ellen B. Silverberg

Applied Mathematics and Statistics

Stanford University

Research output: Contribution to journal › Article › peer-review

269 Scopus citations

Abstract

We analyze a scheduling problem in which each job has a fixed start and end time and a value. We describe an algorithm which maximizes the value of jobs completed by k identical machines. The algorithm runs in time O(n² log n), where n is the number of jobs. We also show that the problem is NP-complete under the following restriction: Associated with each job is a subset of the machines on which it can be processed. For a fixed number of machines k, an O(n^k+1) time algorithm is presented.

Original language	English
Pages (from-to)	1-8
Number of pages	8
Journal	Discrete Applied Mathematics
Volume	18
Issue number	1
DOIs	https://doi.org/10.1016/0166-218X(87)90037-0
State	Published - Sep 1987

Keywords

Clique
graph coloring
interval graphs
NP-complete
perfect graphs
scheduling problems
shortest paths

Access to Document

10.1016/0166-218X(87)90037-0

Cite this

@article{a4f9a36e95eb4129954986d937cab69d,

title = "Scheduling jobs with fixed start and end times",

abstract = "We analyze a scheduling problem in which each job has a fixed start and end time and a value. We describe an algorithm which maximizes the value of jobs completed by k identical machines. The algorithm runs in time O(n2 log n), where n is the number of jobs. We also show that the problem is NP-complete under the following restriction: Associated with each job is a subset of the machines on which it can be processed. For a fixed number of machines k, an O(nk+1) time algorithm is presented.",

keywords = "Clique, graph coloring, interval graphs, NP-complete, perfect graphs, scheduling problems, shortest paths",

author = "Arkin, \{Esther M.\} and Silverberg, \{Ellen B.\}",

year = "1987",

month = sep,

doi = "10.1016/0166-218X(87)90037-0",

language = "English",

volume = "18",

pages = "1--8",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

number = "1",

}

TY - JOUR

T1 - Scheduling jobs with fixed start and end times

AU - Arkin, Esther M.

AU - Silverberg, Ellen B.

PY - 1987/9

Y1 - 1987/9

N2 - We analyze a scheduling problem in which each job has a fixed start and end time and a value. We describe an algorithm which maximizes the value of jobs completed by k identical machines. The algorithm runs in time O(n2 log n), where n is the number of jobs. We also show that the problem is NP-complete under the following restriction: Associated with each job is a subset of the machines on which it can be processed. For a fixed number of machines k, an O(nk+1) time algorithm is presented.

AB - We analyze a scheduling problem in which each job has a fixed start and end time and a value. We describe an algorithm which maximizes the value of jobs completed by k identical machines. The algorithm runs in time O(n2 log n), where n is the number of jobs. We also show that the problem is NP-complete under the following restriction: Associated with each job is a subset of the machines on which it can be processed. For a fixed number of machines k, an O(nk+1) time algorithm is presented.

KW - Clique

KW - graph coloring

KW - interval graphs

KW - NP-complete

KW - perfect graphs

KW - scheduling problems

KW - shortest paths

UR - https://www.scopus.com/pages/publications/0023500313

U2 - 10.1016/0166-218X(87)90037-0

DO - 10.1016/0166-218X(87)90037-0

M3 - Article

AN - SCOPUS:0023500313

SN - 0166-218X

VL - 18

SP - 1

EP - 8

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1

ER -

Scheduling jobs with fixed start and end times

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this