{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T07:41:28Z","timestamp":1697960488387},"reference-count":10,"publisher":"Wiley","issue":"12","license":[{"start":{"date-parts":[[2007,9,5]],"date-time":"2007-09-05T00:00:00Z","timestamp":1188950400000},"content-version":"vor","delay-in-days":6821,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems &amp; Computers in Japan"],"published-print":{"date-parts":[[1989,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A tree\u2010connected processor system (TPS) is a system in which <jats:italic>m<\/jats:italic> processors are connected in the form of an in\u2010tree or out\u2010tree. Each job arriving at a TPS flows on a directed path, from a processor specified for the job to the root (or on a directed path from the root to a processor specified for the job), and is processed by processors lying on the directed path. This paper discusses the feasibility decision problem on a TPS. It is a problem to decide whether or not each job can be processed within its deadline from its arrival time, and to find a schedule if the processing is feasible which realizes the processing. As a result for general TPS's, it is shown that the problem can be solved in <jats:italic>O(mn<\/jats:italic> log <jats:italic>n)<\/jats:italic> time for jobs with unit processing times, where <jats:italic>m<\/jats:italic> is the number of processors and <jats:italic>n<\/jats:italic> is the number of jobs. Especially, an algorithm proposed for TPS with an in\u2010tree structure is on\u2010line and can be used even when the information concerning jobs is obtained only at their arrivals.<\/jats:p>","DOI":"10.1002\/scj.4690201205","type":"journal-article","created":{"date-parts":[[2009,11,19]],"date-time":"2009-11-19T22:36:02Z","timestamp":1258670162000},"page":"48-57","source":"Crossref","is-referenced-by-count":0,"title":["Finding a Feasible Schedule on a Tree\u2010Connected Processor System"],"prefix":"10.1002","volume":"20","author":[{"given":"Tsuyoshi","family":"Kawaguchi","sequence":"first","affiliation":[]},{"given":"Seiki","family":"Kyan","sequence":"additional","affiliation":[]},{"given":"Kenji","family":"Onaga","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2007,9,6]]},"reference":[{"key":"e_1_2_1_2_2","volume-title":"Theory of Scheduling","author":"Conway K. W.","year":"1967"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-009-7801-0_4"},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","unstructured":"B. B.Simons A fast algorithm for single processor scheduling. 19th Annual Symposium on Foundation of Computer Science. IEEE Computer Society Long Beach California pp.246\u2013252(1978).","DOI":"10.1109\/SFCS.1978.4"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/0210018"},{"key":"e_1_2_1_6_2","volume-title":"Computers and Intractability\u2014A Guide to the Theory of NP\u2010Completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","unstructured":"B. B.Simons A fast algorithm for multiprocessor scheduling. 21st Annual Symposium on Foundation of Computer Society Long Beach California pp.50\u201353(1980).","DOI":"10.1109\/SFCS.1980.3"},{"key":"e_1_2_1_8_2","unstructured":"T.Kawaguchi K.OnagaandS.Kyan Scheduling jobs on a tree\u2010connected processor system. Papers of Technical Group on Circuits and Systems I.E.C.I.E. Japan CAS87\u2010208 (Dec.1987)."},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70743-X"},{"key":"e_1_2_1_10_2","unstructured":"J.Blazewicz W.Cellary R.Slowinski andJ.Weglarz Scheduling under Resource Constraints\u2014Deterministic Models (Annals of Operations Research 7). J. C. Baltzer AG Basel\u2010Switzerland (1986)."},{"key":"e_1_2_1_11_2","volume-title":"The Design and Analysis of Computer Algorithms","author":"Aho A. V.","year":"1974"}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.4690201205","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.4690201205","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T16:32:56Z","timestamp":1697905976000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.4690201205"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,1]]},"references-count":10,"journal-issue":{"issue":"12","published-print":{"date-parts":[[1989,1]]}},"alternative-id":["10.1002\/scj.4690201205"],"URL":"https:\/\/doi.org\/10.1002\/scj.4690201205","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"value":"0882-1666","type":"print"},{"value":"1520-684X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,1]]}}}