Scheduling jobs with temporal distance constraints

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

*此作品的通信作者

研究成果: 期刊稿件文章同行評審

12 引文 斯高帕斯(Scopus)

摘要

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
對外發佈

指紋

深入研究「Scheduling jobs with temporal distance constraints」主題。共同形成了獨特的指紋。

引用此