The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 24 NO.5 / (1995))
Scheduling Jobs with Temporal Distance Constraints
Ching-Chih Han, Kwei-Jay Lin, Jane W.-S. Liu,
Pages. 1104-1121
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-algorithm, where $n$ is the total number of jobs in the system, and also an $O(m^2c^2)$-time algorithm. Some other variations of the JSD problems are also investigated.
Contents 1. Introduction
1.1. Related work
2. Scheduling jobs with distance constraints
2.1. The MUJSD problem
3. A pseudopolynomial time algorithm for MUJSD
3.1. Properties of the MUJSD schedules
3.2. The SMD algorithm
3.3. The schedulability condition for MUJSD systems
4. A polynomial-time algorithm for the MUJSD problem
4.1. Data structures
4.2. The PMD algorithm
4.3. Rescheduling job chains
4.4. Properties of algorithm PMD
5. Some extensions to the MUJSD problem
5.1. The general MUJSD problem
5.2. The bilevel tree UJSD problem
5.3. The multiprocessor problems
6. Conclusions
Key words deadline, job scheduling, precedence constraint, real-time systems, relative timing constraint, temporal distance.
Mathmatical Subject Classification 68Q25