摘要
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.
原文 | 英語 |
---|---|
頁(從 - 到) | 1104-1121 |
頁數 | 18 |
期刊 | SIAM Journal on Computing |
卷 | 24 |
發行號 | 5 |
DOIs | |
出版狀態 | 已出版 - 1995 |
對外發佈 | 是 |