{"entities":{"Q1060946":{"pageid":1071698,"ns":120,"title":"Item:Q1060946","lastrevid":66059079,"modified":"2026-04-12T07:15:41Z","type":"item","id":"Q1060946","labels":{"en":{"language":"en","value":"Worst-case analysis of a scheduling algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3910119"}},"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":"Q1060946$06DBC708-C4D2-417F-827A-9CF7CCD97C7A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"58cd38ea899a9790bcf8acadec6cca801f38a7b1","datavalue":{"value":{"text":"Worst-case analysis of a scheduling algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1060946$D5629EF2-F68B-4506-969E-849015C09588","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8028cf9baf4a703c013123f209bf0ee0911cba85","datavalue":{"value":"0569.90045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060946$FDBC772F-0DE1-41C3-A1BD-54820380913C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"19ceea39213393eee594632fba908cfe65f7c227","datavalue":{"value":"10.1016/0167-6377(85)90043-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060946$D6302B61-BECB-416D-9577-1F977B29530D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060946$B86DCD9B-A531-4FB2-A9C7-52410A6417A1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1060946$174443FD-D1A8-4A45-9556-0321502D7790","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fe94882eba8ca360c950c13062e688a81516f542","datavalue":{"value":"A heuristic proposed by \\textit{O. Ibarra} and \\textit{C. Kim} [J. Assoc. Comput. Mach. 24, 280-289 (1977; Zbl 0382.90048)] for scheduling independent tasks on unrelated processors is analyzed. The heuristic may create a schedule which finishes in time m*OPT, where m is the number of processors, and OPT is the time used in the optimal schedule. This compares unfavorably with the heuristics described by \\textit{E. Davis} and \\textit{J. Jaffe} [ibid. 28, 721-736 (1981; Zbl 0472.68020)], which have worst-case behavior which is \\(O(OPT*m^{0.5})\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060946$9DACECA5-4E2A-418C-8838-FB7FEA95EE8E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060946$C58EE96F-D29B-44DC-9C56-B4EB32785338","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060946$7EFAEDBD-A65F-495E-82C4-A02D26427A7E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"45e29945b2f5d21062eeb1e60c9963d732a63f6a","datavalue":{"value":"3910119","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060946$D3B63858-650B-4733-A242-B989F4C7C27A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b938dfa52cc4dde211f8bda3d75afd44dc6a9852","datavalue":{"value":"scheduling algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060946$DBA05F37-841D-4944-ADD0-C76F4632DC93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f641bd239fe6f0d5fb2cc0d2b3f89cbc609bab87","datavalue":{"value":"heuristic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060946$D59D07D2-6B82-42BF-80A2-84785D77E25B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3a9b7ebc463b388cfd935ce1042f0f1c5c126631","datavalue":{"value":"independent tasks","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060946$670AF235-3200-47E4-80F1-49015EB5D691","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9747c545e77686a4917c4e37895d15d9822cd103","datavalue":{"value":"unrelated processors","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060946$D8D6AD38-0C2F-49E1-B5B1-DD7F404C852E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84da93b2d5f45a9347fafdc03b0b5f74af0d84c2","datavalue":{"value":"worst-case behavior","type":"string"},"datatype":"string"},"type":"statement","id":"Q1060946$7B239D13-61A9-43BE-9010-0FDCB4EB996E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0ef8392e01c11e85b032ddf62d87088b822bd19a","datavalue":{"value":{"entity-type":"item","numeric-id":344852,"id":"Q344852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060946$824C4DC8-AF84-46F5-A9C3-F7A1C71680F5","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":"Q1060946$FD15F9B1-4F1D-4E04-AE94-EEED590B8213","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"112e194e1d17fbffd89d0891047d7e59c38e87d1","datavalue":{"value":"https://doi.org/10.1016/0167-6377(85)90043-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1060946$5D8753E3-4B30-415B-9C78-1FFBBF0C63B8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8f22e9868b57c9372a031eb829dde1090f4503bf","datavalue":{"value":"W2075962074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1060946$7747E2A9-417F-431D-ADC0-B42D2A56A972","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc52e5fd73d3b2f0935b0c4b7164d9dab1788fd3","datavalue":{"value":{"entity-type":"item","numeric-id":4769981,"id":"Q4769981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060946$9FB8D1EB-65DF-4094-B5DF-D9C6B069BCD3","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":"Q1060946$5939AEE1-43C6-4DFB-BD8B-A597A792366A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060946$D1588124-ECA2-4819-887F-9B26B4A11AA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33e8a7ecbe695332ed12405b42bedc2893b98ce3","datavalue":{"value":{"entity-type":"item","numeric-id":4095869,"id":"Q4095869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060946$13E4DE69-7021-451D-89A6-766C6DEAF5D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b27292a0dcc90836a68b3d2305667c316dd6ac71","datavalue":{"value":{"entity-type":"item","numeric-id":4160662,"id":"Q4160662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1060946$E3212ADC-CF81-43BA-880F-2AA68D388EA7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1ad9ce804e592e249784669ef81d9081e85be55","datavalue":{"value":{"entity-type":"item","numeric-id":3340132,"id":"Q3340132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a92e3416fdb48b5b0a1732a01a82a3b1566e6ec","datavalue":{"value":{"amount":"+0.8595007658004761","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":"Q1060946$7253E07E-4951-4DF3-BE86-186A83651AC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34085e53b1790f2383f1b4b7d259cf98f96fa6d2","datavalue":{"value":{"entity-type":"item","numeric-id":3677169,"id":"Q3677169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"878b070573f6c8ca797030ce2b9425634212f00f","datavalue":{"value":{"amount":"+0.8356854915618896","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":"Q1060946$F517B584-FF71-4021-948A-8AA92780C204","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6b1e924721791ed3b3e445bd495fb3550b653f8","datavalue":{"value":{"entity-type":"item","numeric-id":1097028,"id":"Q1097028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e4d20dd6d3e97599c4484e749bb89e5032d6bdc","datavalue":{"value":{"amount":"+0.8342065811157227","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":"Q1060946$D055F87D-548B-4B4D-BDDA-3DA146D385F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94f199d1ba086c06eb9e560db780d4a9996fb652","datavalue":{"value":{"entity-type":"item","numeric-id":3789320,"id":"Q3789320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"891e76448a28b4e5bf9e5bbce1cc5ba47fd5d86d","datavalue":{"value":{"amount":"+0.8302362561225891","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":"Q1060946$E24CA6F6-688C-44CA-9590-3DE2C681A7D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6ad4e00065c0682ad3f3e2ea7d622ea35cda23d","datavalue":{"value":{"entity-type":"item","numeric-id":3725543,"id":"Q3725543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cfcd6d6d8174845b2ea31946a50ccb6a7512be66","datavalue":{"value":{"amount":"+0.8167327046394348","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":"Q1060946$5CDEDB89-B7C1-41A7-868B-03701BF4D133","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Worst-case analysis of a scheduling algorithm","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Worst-case_analysis_of_a_scheduling_algorithm"}}}}}