{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:29:16Z","timestamp":1787340556101,"version":"3.56.0"},"reference-count":7,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1975,12]]},"abstract":"<jats:p>A scheduling rule is given for determining the processing order of tasks which have the precedence structure of chains. It is assumed that the service times follow known distributions, that they are all independent, that costs are accrued by tasks at a constant rate until their service requirements are satisfied, that all the tasks are available at time 0 and that the service is interruptible at task-specific sets of points. The rule consists of computing for each chain an \u201coptimal assignment\u201d for its tasks and a rank function which depends on this assignment. Choosing at each point in time the chain with the smallest rank produces an optimal schedule. It is proved that the \u201coptimal assignments\u201d have the desirable property that as long as a task does not exceed its allotted service time, no preemption should take place.<\/jats:p>","DOI":"10.1137\/0204041","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T05:56:23Z","timestamp":1109224583000},"page":"478-490","source":"Crossref","is-referenced-by-count":27,"title":["On Scheduling Chains of Jobs on One Processor with Limited Preemption"],"prefix":"10.1137","volume":"4","author":[{"given":"John","family":"Bruno","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha","family":"Hofri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","unstructured":"J. Bruno, E. Coffman, D. Johnson,  On batch scheduling of jobs with stochastic service and cost structures on a single server, Tech. Rep., 159, Dept. of Computer Sci., Pennsylvania State Univ., University Park,  1974"},{"key":"R2","volume-title":"Theory of scheduling","author":"Conway Richard W.","year":"1967"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1137\/0123021"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"R5","unstructured":"L. Schrage,  Optimal scheduling disciplines for a single machine under various degrees of information,  44th ORSA Conf., Boston,  1974, April"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1145\/321796.321803"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1287\/opre.23.2.283"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0204041","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:09Z","timestamp":1787337549000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0204041"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1975,12]]},"references-count":7,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1975,12]]}},"alternative-id":["10.1137\/0204041"],"URL":"https:\/\/doi.org\/10.1137\/0204041","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1975,12]]}}}