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(n^{2})$-time algorithm, where n is the total number of jobs in the system, and also an $O(m^{2}c^{2})$-time algorithm. Some other variations of the JSD problems are also investigated.