{"entities":{"Q1602711":{"pageid":1613451,"ns":120,"title":"Item:Q1602711","lastrevid":72305610,"modified":"2026-04-14T04:00:29Z","type":"item","id":"Q1602711","labels":{"en":{"language":"en","value":"On-line scheduling with precedence constraints"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1758394"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602711$03C7736A-EC8A-47E7-BC4E-B9D178165CAD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d59311d2acb0b9908ca96308ac95285ef14100bd","datavalue":{"value":{"text":"On-line scheduling with precedence constraints","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1602711$0FCE839B-3CDF-48CC-8B7D-46F6ABB7A728","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8eb65d67a19cd4835fc6e86b3e55873085858461","datavalue":{"value":"0996.90038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1602711$75975059-EEBB-4029-AB5B-627BC3AD3EC7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6aab3a7a7eefcb2997873533dc02160487ff8221","datavalue":{"value":"10.1016/S0166-218X(01)00272-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1602711$6171D4F5-0205-4231-AD75-4679F435944B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"68814389157e3d8757e8eed17277cd2e82d90c5b","datavalue":{"value":{"entity-type":"item","numeric-id":526845,"id":"Q526845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602711$FD06777B-53CA-497C-92C8-404BAFDC0019","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2c3269ab44f9669f0576537dce123fd34c697ef0","datavalue":{"value":{"entity-type":"item","numeric-id":189394,"id":"Q189394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602711$79DF009B-E907-455A-971C-43BE04A6A1E5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602711$620AEAEA-7CE0-4154-BB3B-EC855D2633F1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1bdd63e74125a64b52265510548f082cbef9c284","datavalue":{"value":{"time":"+2002-06-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1602711$35DADA49-A348-4211-AEAC-727750483E30","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a26a8dc5c5ad1261060080acb0278bc2b9badb5c","datavalue":{"value":"The on-line problem of scheduling jobs with precedence constraints on \\(m\\) machines, is considered. The authors concentrate in two models, the model of uniformly related machines and the model of restricted assignment. For the related machines model, it is shown a lower bound of \\(\\Omega(\\sqrt{m})\\) for the competitive ratio of deterministic and randomized on-line algorithms, with or without preemptions even for known running times. This matches the deterministic upper bound of \\(O(\\sqrt{m})\\) given previously by Jaffe. The lower bound should be contrasted with the known bounds for jobs without precedence constraints. Specifically, without precedence constraints, if preemptions are allowed then the competitive ratio becomes \\(\\Theta(\\log m)\\), and if the running times of the jobs are known then there are \\(O(1)\\) competitive (preemptive and nonpreemptive) algorithms.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1602711$64923E55-EFEE-4587-A1CE-F1A077592D35","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"208fd2cac25388eac9d979aba68dad257ddb3873","datavalue":{"value":{"entity-type":"item","numeric-id":224835,"id":"Q224835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602711$36304802-3DFE-4A5D-81D5-5A16D88A57DF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1602711$115EE1B8-DE33-45D1-9D87-29240B56266C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1602711$B86E67EF-AC29-42FC-A66C-60294A4D24EE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6ab43ec83373d86a9193fb4104f7c897d7b5ef44","datavalue":{"value":"1758394","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1602711$AF298EFE-057D-4C05-AE2A-F9582C6E32C8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"56d85aa22959094ecc003ac28085d2ab6f8f44c0","datavalue":{"value":"competitive ratio","type":"string"},"datatype":"string"},"type":"statement","id":"Q1602711$1C854AAD-8713-4E40-BA19-8D20FE69C9C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a5bbee82e9755ef89170fea0bdfc83a215ffad17","datavalue":{"value":"on-line problem of scheduling jobs with precedence constraints","type":"string"},"datatype":"string"},"type":"statement","id":"Q1602711$D586AFA4-4D18-4001-8617-ADB6823CB154","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3a1af7af94c759b504d54cb2820246a65b769114","datavalue":{"value":"uniformly related machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1602711$D1C0043F-DE39-43E4-97A2-32CA55947BDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f8d86108bf89b1f35f997fdcfee58d221d51f4b","datavalue":{"value":"model of restricted assignment","type":"string"},"datatype":"string"},"type":"statement","id":"Q1602711$BB896A39-934F-40D9-977B-CB0559B22A4C","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602711$E863F14B-755A-4DA1-AB68-C529F4C0907D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1c2f8ee6bcf293da9b3e8f55c8df84b1d12c50f","datavalue":{"value":{"entity-type":"item","numeric-id":4327820,"id":"Q4327820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602711$95C1E999-F237-4E02-B318-E3B8F09BC285","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a64c66f84ef3d614c129d9701b7e0cb0d4d62295","datavalue":{"value":{"entity-type":"item","numeric-id":4223058,"id":"Q4223058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602711$2A74263D-D0CC-49D2-84DE-BF6769C8BD5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"174ea4156e2245d49acd0542149018931e18b167","datavalue":{"value":{"entity-type":"item","numeric-id":4238532,"id":"Q4238532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602711$D8ED2EAE-92F9-4C68-B96C-8A8B05E2A699","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa102313bd6282ba09c7a888a595d49e4fe03d7b","datavalue":{"value":{"entity-type":"item","numeric-id":3925878,"id":"Q3925878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602711$B83FC0CC-E392-4AD7-B2B1-10C8519A0314","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f38c74a7eaf0c2ef76f620f3c1fdff2be5ae3d7","datavalue":{"value":{"entity-type":"item","numeric-id":4400847,"id":"Q4400847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602711$9CFDA945-E607-4955-8FC8-79A8E0D27967","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b02f77b02765e13c4cbf73ce96615064dad64c5","datavalue":{"value":{"entity-type":"item","numeric-id":4139680,"id":"Q4139680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602711$10A50382-35C4-4316-B85E-ACF5A4863639","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df399851d600f5fc66b83855263f74637e3a379d","datavalue":{"value":{"entity-type":"item","numeric-id":5555416,"id":"Q5555416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602711$FBE72827-8C13-44CC-A8C2-61EB052C6846","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7470519bc10f2a005ff140469be5d8d581b53250","datavalue":{"value":{"entity-type":"item","numeric-id":5582060,"id":"Q5582060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602711$DDC0FB84-7508-4E88-B4BE-3C36FD7402A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"050487ebc7844a3ffa8ba5c0c4ec1da40782b513","datavalue":{"value":{"entity-type":"item","numeric-id":3792237,"id":"Q3792237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602711$358239CB-FFA0-4FDC-A198-265B61D82D24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80ca7ed71ed80eca8757cff9a278d704be0c563a","datavalue":{"value":{"entity-type":"item","numeric-id":4126043,"id":"Q4126043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602711$388BC3C0-2A32-4152-825E-C59D1003A28C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"698f6d1e33944778040f3a3513677bc52cb2ae51","datavalue":{"value":{"entity-type":"item","numeric-id":1145998,"id":"Q1145998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602711$3F07F110-311C-4306-B788-33E8C74391AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90941b800078ae0e3d3543dac175e40e094eb3ed","datavalue":{"value":{"entity-type":"item","numeric-id":1048670,"id":"Q1048670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602711$CE1BCB6F-9909-4DF8-A848-B68C3E116F01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b06d2463641f5232fd95a6758076cc17ba0b5c3","datavalue":{"value":{"entity-type":"item","numeric-id":4862799,"id":"Q4862799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1602711$24BC4838-BBD6-4098-9FB1-18A042A7271B","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"810325c0945a5b3b45d22ae93fe01e0b7e2d0d33","datavalue":{"value":"Q127333533","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1602711$BA0925E0-5014-41F1-BD6A-964F754C7029","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b60dcb2c9082d6353118da68f1d14ef6593da41","datavalue":{"value":{"entity-type":"item","numeric-id":2721976,"id":"Q2721976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86934d8568608a6b64a952516cb79f208698ab6f","datavalue":{"value":{"amount":"+0.985723316669464","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1602711$332DCF8C-9476-40B9-8D91-2AC0CA33C88A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eda70e1d9e99cc0be513428ae0bf57205cc4f3c1","datavalue":{"value":{"entity-type":"item","numeric-id":721932,"id":"Q721932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86934d8568608a6b64a952516cb79f208698ab6f","datavalue":{"value":{"amount":"+0.985723316669464","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1602711$6D8DE417-48EB-4604-BD41-8A4E9B3F3A5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"448425a8c33d0de059a516e9e7d3238087e42936","datavalue":{"value":{"entity-type":"item","numeric-id":1607065,"id":"Q1607065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28d5130c2ddb4d344a3a0c071510b2f30b1fb3cb","datavalue":{"value":{"amount":"+0.9528846144676208","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1602711$A52EB1DB-9EEB-4465-88C1-D3AD6E21756F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"213cbcd860036d93c82f15a2ec9971e6e4deb472","datavalue":{"value":{"entity-type":"item","numeric-id":4400847,"id":"Q4400847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c5d12cc151780660b792470e3cbe25078ab12bd","datavalue":{"value":{"amount":"+0.9499409794807434","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1602711$ED03C723-4329-4184-8560-74AC6042E84C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8af6e0281972e1ceb3be6d133eef602bdd4aad4","datavalue":{"value":{"entity-type":"item","numeric-id":5317172,"id":"Q5317172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5101935207cda288ed3d42394f42a6e45e11433a","datavalue":{"value":{"amount":"+0.876264214515686","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1602711$A342F5B0-D54C-429E-A8EF-C4D4CEB76A87","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On-line scheduling with precedence constraints","badges":[]}}}}}