{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,25]],"date-time":"2026-10-25T18:25:05Z","timestamp":1792952705379,"version":"4.5.0"},"reference-count":14,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1995,10]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/s0097539791218081","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:42:53Z","timestamp":1109227373000},"page":"1104-1121","source":"Crossref","is-referenced-by-count":18,"title":["Scheduling Jobs with Temporal Distance Constraints"],"prefix":"10.1137","volume":"24","author":[{"given":"Ching-Chih","family":"Han","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kwei-Jay","family":"Lin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jane W.-S.","family":"Liu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/0125042"},{"key":"R2","first-page":"1","volume":"31","author":"Blazewicz J.","year":"1987","journal-title":"Ann. Discrete Math."},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/0134037"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/0206029"},{"key":"R5","volume-title":"Computers and intractability","author":"Garey Michael R.","year":"1979"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"R7","unstructured":"C.C. Han,  Scheduling real-time computations with temporal distance and separation constraints and with extended deadlines, Tech. report, UIUCDCS-R-92-1748, Department of Computer Science, University of Illinois at Urbana-Champaign,  1992, Ph.D. thesis"},{"key":"R8","unstructured":"C.C. Han, K.J. Lin,  Scheduling jobs with temporal consistency constrainL~,  Proc. 6th IEEE Workshop on Real-Time Operating Systems and Software, Pittsburgh, PA,  1989,  18\u201323"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"C.C. Han, K.J. Lin,  Scheduling distance-constrained real-time tasks,  Proc. 13th IEEE Real-Time Systems Symposium, Phoenix, AZ,  1992,  300\u2013308","DOI":"10.1109\/REAL.1992.242649"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90091-9"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-009-7801-0_3"},{"key":"R12","volume-title":"Combinatorial Optimization: Annotated Bibliographies","author":"Lenstra J. K.","year":"1984"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/BF02280884"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.4"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539791218081","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:53:27Z","timestamp":1787338407000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539791218081"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,10]]},"references-count":14,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1995,10]]}},"alternative-id":["10.1137\/S0097539791218081"],"URL":"https:\/\/doi.org\/10.1137\/s0097539791218081","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,10]]}}}