{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,27]],"date-time":"2023-08-27T05:59:54Z","timestamp":1693115994162},"reference-count":44,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[1995,6,1]],"date-time":"1995-06-01T00:00:00Z","timestamp":801964800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":6621,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1995,6]]},"DOI":"10.1016\/0304-3975(94)00282-n","type":"journal-article","created":{"date-parts":[[2003,5,13]],"date-time":"2003-05-13T00:04:58Z","timestamp":1052784298000},"page":"277-314","source":"Crossref","is-referenced-by-count":1,"title":["Random trees in queueing systems with deadlines"],"prefix":"10.1016","volume":"144","author":[{"given":"U.","family":"Schmid","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/0304-3975(94)00282-N_BIB1","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1137\/0221043","article-title":"Maximum size of a dynamic data structure: hashing with lazy deletion revisited","volume":"21","author":"Aldous","year":"1992","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(94)00282-N_BIB2","doi-asserted-by":"crossref","first-page":"887","DOI":"10.2307\/1427345","article-title":"Single-server queues with impatient customers","volume":"16","author":"Baccelli","year":"1984","journal-title":"Adv. Appl. Prob."},{"key":"10.1016\/0304-3975(94)00282-N_BIB3","series-title":"Proc. IEEE Real-Time Systems Symp.","first-page":"106","article-title":"On the competitiveness of on-line real-time task scheduling","author":"Baruah","year":"1991"},{"key":"10.1016\/0304-3975(94)00282-N_BIB4","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1137\/1016082","article-title":"Asymptotic methods in enumeration","volume":"16","author":"Bender","year":"1974","journal-title":"SIAM Rev."},{"key":"10.1016\/0304-3975(94)00282-N_BIB5","series-title":"Scheduling in Computer and Manufacturing Systems","author":"Blazewicz","year":"1993"},{"key":"10.1016\/0304-3975(94)00282-N_BIB6","doi-asserted-by":"crossref","first-page":"370","DOI":"10.1007\/BF02074875","article-title":"FCFS scheduling in a hard real-time environment under rush-hour conditions","volume":"32","author":"Blieberger","year":"1991","journal-title":"BIT"},{"key":"10.1016\/0304-3975(94)00282-N_BIB7","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0166-5316(92)90035-F","article-title":"Preemptive LCFS scheduling in hard real-time applications","volume":"15","author":"Blieberger","year":"1992","journal-title":"Performance Evaluation"},{"key":"10.1016\/0304-3975(94)00282-N_BIB8","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1016\/0097-3165(84)90055-4","article-title":"Remarks on an asymptotic method in combinatorics","volume":"37","author":"Canfield","year":"1984","journal-title":"J. Combin. Theory Ser. A"},{"key":"10.1016\/0304-3975(94)00282-N_BIB9","series-title":"Tutorial: Hard Real-Time Systems","article-title":"Scheduling algorithms for hard real-time systems \u2014 a brief survey","author":"Cheng","year":"1988"},{"key":"10.1016\/0304-3975(94)00282-N_BIB10","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/BF00365326","article-title":"Dynamic scheduling of real-time tasks under precendence constraints","volume":"2","author":"Chetto","year":"1990","journal-title":"Real-Time Systems"},{"key":"10.1016\/0304-3975(94)00282-N_BIB11","series-title":"The Single-Server Queue","author":"Cohen","year":"1982"},{"key":"10.1016\/0304-3975(94)00282-N_BIB12","series-title":"Deterministic and Stochastic Scheduling","year":"1982"},{"key":"10.1016\/0304-3975(94)00282-N_BIB13","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1002\/rsa.3240050106","article-title":"The instability time distribution behaviour of slotted ALOHA","volume":"5","author":"Drmota","year":"1994","journal-title":"Random Structures and Algorithms"},{"key":"10.1016\/0304-3975(94)00282-N_BIB14","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1137\/0153018","article-title":"Exponential limiting distributions in queueing systems with deadlines","volume":"53","author":"Drmota","year":"1993","journal-title":"SIAM J. Appl. Math."},{"key":"10.1016\/0304-3975(94)00282-N_BIB15","doi-asserted-by":"crossref","first-page":"1567","DOI":"10.1109\/18.259641","article-title":"The analysis of the expected successful operation time of slotted ALOHA","volume":"39","author":"Drmota","year":"1993","journal-title":"IEEE J. Inform. Th."},{"key":"10.1016\/0304-3975(94)00282-N_BIB16_1","article-title":"Analyse d'algorithmes de manipulation d'arbes et de fichiers","author":"Flajolet","year":"1979","journal-title":"Th\u00e8se Paris-Sud-Orsay"},{"key":"10.1016\/0304-3975(94)00282-N_BIB16_2","first-page":"1","volume":"34\u201335","author":"Flajolet","year":"1981","journal-title":"Cahiers de BURO"},{"key":"10.1016\/0304-3975(94)00282-N_BIB17","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1137\/0403019","article-title":"Singularity analysis of generating functions","volume":"3","author":"Flajolet","year":"1990","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/0304-3975(94)00282-N_BIB18","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0304-3975(79)90009-4","article-title":"The number of registers required to evaluate arithmetic expressions","volume":"9","author":"Flajolet","year":"1979","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/0304-3975(94)00282-N_BIB19","doi-asserted-by":"crossref","first-page":"1349","DOI":"10.1287\/mnsc.23.12.1349","article-title":"The Markovian queue with bounded waiting time","volume":"23","author":"Gavish","year":"1977","journal-title":"Management Sci."},{"key":"10.1016\/0304-3975(94)00282-N_BIB20","doi-asserted-by":"crossref","first-page":"807","DOI":"10.1137\/0220050","article-title":"The Maximum size of dynamic data structures","volume":"20","author":"Kenyon-Mathieu","year":"1991","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(94)00282-N_BIB21","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0890-5401(87)90009-5","article-title":"On the recursion depth of special tree traversal algorithms","volume":"74","author":"Kirschenhofer","year":"1987","journal-title":"Inform. and Comput."},{"key":"10.1016\/0304-3975(94)00282-N_BIB22","series-title":"Queueing Systems","author":"Kleinrock","year":"1975"},{"key":"10.1016\/0304-3975(94)00282-N_BIB23","series-title":"Proc. IEEE Real-Time Systems Symp.","first-page":"290","article-title":"Dover: An optimal on-line scheduling algorithm for overloaded real-time systems","author":"Koren","year":"1992"},{"key":"10.1016\/0304-3975(94)00282-N_BIB24","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1145\/173942.173943","article-title":"Open issues and challenges in providing quality of service guarantees in high-speed networks","volume":"23","author":"Kurose","year":"1993","journal-title":"ACM Comput. Comm. Rev."},{"key":"10.1016\/0304-3975(94)00282-N_BIB25","series-title":"Proc. IEEE Real-Time Systems Symp.","first-page":"110","article-title":"An optimal algorithm for scheduling soft-aperiodic tasks in fixed-priority preemptive systems","author":"Lehoczky","year":"1992"},{"key":"10.1016\/0304-3975(94)00282-N_BIB26","series-title":"Proc. 8th Internat. Conf. on Fundamentals of Computing Theory FCT '91","first-page":"339","article-title":"Data structures maxima","author":"Louchard","year":"1991"},{"key":"10.1016\/0304-3975(94)00282-N_BIB27","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/rsa.3240020404","article-title":"Colliding stacks: a large deviations analysis","volume":"2","author":"Maier","year":"1991","journal-title":"Random Structures and Algorithms"},{"key":"10.1016\/0304-3975(94)00282-N_BIB28","series-title":"Proc. 3rd Workshop Algorithms and Data Structures WADS '93","first-page":"495","article-title":"The exhaustion of shared memory: stochastic results","author":"Maier","year":"1993"},{"key":"10.1016\/0304-3975(94)00282-N_BIB29","series-title":"Theory of Functions of a Complex Variable","author":"Markushevic","year":"1965"},{"key":"10.1016\/0304-3975(94)00282-N_BIB30","doi-asserted-by":"crossref","first-page":"997","DOI":"10.4153\/CJM-1978-085-0","article-title":"On the altitude of nodes in random trees","volume":"30","author":"Meir","year":"1978","journal-title":"Canada J. Math."},{"key":"10.1016\/0304-3975(94)00282-N_BIB31","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0097-3165(89)90078-2","article-title":"On an asymptotic method in enumeration","volume":"A 51","author":"Meir","year":"1989","journal-title":"J. Combin. Theory Ser."},{"key":"10.1016\/0304-3975(94)00282-N_BIB32","doi-asserted-by":"crossref","first-page":"832","DOI":"10.1145\/48014.48019","article-title":"Optimal scheduling policies for a class of queues with customer deadlines to the beginning of service","volume":"35","author":"Panwar","year":"1988","journal-title":"J. ACM"},{"key":"10.1016\/0304-3975(94)00282-N_BIB33","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1287\/opre.31.3.559","article-title":"Stochastic scheduling with release dates and due dates","volume":"31","author":"Pinedo","year":"1983","journal-title":"Oper. Res."},{"key":"10.1016\/0304-3975(94)00282-N_BIB34","unstructured":"U. Schmid, Static priority scheduling of aperiodic real-time tasks, submitted."},{"key":"10.1016\/0304-3975(94)00282-N_BIB35","doi-asserted-by":"crossref","DOI":"10.1007\/BF01088621","article-title":"Monitoring distributed real-time systems","volume":"7","author":"Schmid","year":"1994","journal-title":"Real-time Systems"},{"key":"10.1016\/0304-3975(94)00282-N_BIB36","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1016\/0022-0000(92)90036-I","article-title":"Some investigations on FCFS scheduling in hard real-time applications","volume":"45","author":"Schmid","year":"1992","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/0304-3975(94)00282-N_BIB37","doi-asserted-by":"crossref","unstructured":"U. Schmid and J. Blieberger, On nonpreemptive LCFS scheduling with deadlines, J. Algorithms, to appear.","DOI":"10.1006\/jagm.1995.1004"},{"key":"10.1016\/0304-3975(94)00282-N_BIB38","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF02320193","article-title":"An optimal lateness and tardiness scheduling in real-time systems","volume":"47","author":"Stoyenko","year":"1992","journal-title":"Computing"},{"key":"10.1016\/0304-3975(94)00282-N_BIB39","series-title":"Combinatorial Methods in the Theory of Stochastic Processes","author":"Tak\u00e1cs","year":"1977"},{"key":"10.1016\/0304-3975(94)00282-N_BIB40","series-title":"Proc. Joint Conf. Performance '93 and Sigmetrics '93","first-page":"560","article-title":"Providing quality of service in packet switched networks","volume":"Vol. 729","author":"Towsley","year":"1993"},{"key":"10.1016\/0304-3975(94)00282-N_BIB41","series-title":"Foundations of Real-Time Computing: Scheduling and Resource Management","year":"1991"},{"key":"10.1016\/0304-3975(94)00282-N_BIB42","first-page":"431","article-title":"Average case analysis of algorithms and data structures","volume":"Vol. A","author":"Vitter","year":"1990"},{"key":"10.1016\/0304-3975(94)00282-N_BIB43","series-title":"Proc. IEEE Real-Time Systems Symp.","first-page":"156","article-title":"Performance analysis of FCFS and improved FCFS scheduling algorithms for dynamic real-time computer systems","author":"Zhao","year":"1989"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759400282N?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759400282N?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,16]],"date-time":"2019-04-16T08:27:59Z","timestamp":1555403279000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/030439759400282N"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,6]]},"references-count":44,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[1995,6]]}},"alternative-id":["030439759400282N"],"URL":"https:\/\/doi.org\/10.1016\/0304-3975(94)00282-n","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[1995,6]]}}}