Scheduling jobs with temporal distance constraints

Han Ching-Chih; Lin Kwei-Jay; J. W.S. Liu

doi:10.1137/s0097539791218081

Scheduling jobs with temporal distance constraints

Han Ching-Chih^*, Lin Kwei-Jay, J. W.S. Liu

^*Corresponding author for this work

University of Michigan, Ann Arbor

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

12 Scopus citations

Abstract

The job scheduling problems for real-time jobs with temporal distance constraints (JSD) are presented. In JSD, the start times of two related jobs must be within a given distance. The general JSD problem is NP-hard. We define the multilevel unit-time JSD (MUJSD) problem for systems with m chains of unit-time jobs in which neighboring jobs in each chain must be scheduled within c time units. We present an O(n²)-time algorithm, where n is the total number of jobs in the system, and also an O(m²c²)-time algorithm. Some other variations of the JSD problems are also investigated.

Original language	English
Pages (from-to)	1104-1121
Number of pages	18
Journal	SIAM Journal on Computing
Volume	24
Issue number	5
DOIs	https://doi.org/10.1137/s0097539791218081
State	Published - 1995
Externally published	Yes

Access to Document

10.1137/s0097539791218081

Cite this

@article{a4eea1629b18453a92877fb202af861c,

title = "Scheduling jobs with temporal distance constraints",

abstract = "The job scheduling problems for real-time jobs with temporal distance constraints (JSD) are presented. In JSD, the start times of two related jobs must be within a given distance. The general JSD problem is NP-hard. We define the multilevel unit-time JSD (MUJSD) problem for systems with m chains of unit-time jobs in which neighboring jobs in each chain must be scheduled within c time units. We present an O(n2)-time algorithm, where n is the total number of jobs in the system, and also an O(m2c2)-time algorithm. Some other variations of the JSD problems are also investigated.",

author = "Han Ching-Chih and Lin Kwei-Jay and Liu, {J. W.S.}",

year = "1995",

doi = "10.1137/s0097539791218081",

language = "英语",

volume = "24",

pages = "1104--1121",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "5",

}

TY - JOUR

T1 - Scheduling jobs with temporal distance constraints

AU - Ching-Chih, Han

AU - Kwei-Jay, Lin

AU - Liu, J. W.S.

PY - 1995

Y1 - 1995

N2 - The job scheduling problems for real-time jobs with temporal distance constraints (JSD) are presented. In JSD, the start times of two related jobs must be within a given distance. The general JSD problem is NP-hard. We define the multilevel unit-time JSD (MUJSD) problem for systems with m chains of unit-time jobs in which neighboring jobs in each chain must be scheduled within c time units. We present an O(n2)-time algorithm, where n is the total number of jobs in the system, and also an O(m2c2)-time algorithm. Some other variations of the JSD problems are also investigated.

AB - The job scheduling problems for real-time jobs with temporal distance constraints (JSD) are presented. In JSD, the start times of two related jobs must be within a given distance. The general JSD problem is NP-hard. We define the multilevel unit-time JSD (MUJSD) problem for systems with m chains of unit-time jobs in which neighboring jobs in each chain must be scheduled within c time units. We present an O(n2)-time algorithm, where n is the total number of jobs in the system, and also an O(m2c2)-time algorithm. Some other variations of the JSD problems are also investigated.

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

U2 - 10.1137/s0097539791218081

DO - 10.1137/s0097539791218081

M3 - 文章

AN - SCOPUS:0029498814

SN - 0097-5397

VL - 24

SP - 1104

EP - 1121

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 5

ER -

Scheduling jobs with temporal distance constraints

Abstract

Access to Document

Other files and links

Fingerprint

Cite this