{"entities":{"Q1317007":{"pageid":1327757,"ns":120,"title":"Item:Q1317007","lastrevid":67159278,"modified":"2026-04-12T15:41:27Z","type":"item","id":"Q1317007","labels":{"en":{"language":"en","value":"Bounds and asymptotic results for the uniform parallel processor weighted flow time problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 527398"}},"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":"Q1317007$8F9A9A70-B0C7-40AD-AF76-198CE723E565","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1210c959bcb58ef5ff93f7dcd9ebeea26cbf4003","datavalue":{"value":{"text":"Bounds and asymptotic results for the uniform parallel processor weighted flow time problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1317007$DECC0821-4AB2-4E5E-8E27-C0871EF8E256","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6d19b657090e89043a239b003ad572df9176eb24","datavalue":{"value":"0804.90078","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1317007$BC7CD2FA-1700-4588-999A-52FFBBD3BE42","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"82f817476d667f1e46b43ad075e104981cee4705","datavalue":{"value":"10.1016/0167-6377(93)90100-U","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1317007$143D639E-6F1A-4904-8B83-29B0D8572A61","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"50585e0f3f4df2cd54a7098990041cafe647b10e","datavalue":{"value":{"entity-type":"item","numeric-id":1266723,"id":"Q1266723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1317007$6828FE98-83AD-458B-B26C-B1CCEEF85832","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":"Q1317007$EDD45337-138C-4E08-A17C-21356787F48A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"97cc0ef6135536f7019a2050f286830402ccf036","datavalue":{"value":{"time":"+1995-01-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1317007$818E8E01-6C7F-443B-8DDF-B9F4796B2F4D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c0996ffdd6c90833765164cea52cf5d9b891cf7f","datavalue":{"value":"Scheduling \\(n\\) jobs with known process times and weights on \\(m\\) parallel processors of different speed with the objective to minimize weighted flow time is known to be an NP-complete optimization problem. The author derives lower and upper bounds for the uniform processor problem which generalize well-known bounds for the identical processor problem. These bounds are used to show asymptotic properties of the uniform processor problem. Based on this it is shown that the heuristic of scheduling jobs on the first available processor in order of nondecreasing process time to weight ratio is asymptotically relatively optimal for a growing number of jobs. Also, the lower bound is asymptotically relatively optimal.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1317007$C073DD35-39DB-4B93-A575-86FDC3BE2FD7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1317007$928135C2-20FA-4796-9782-3F58437CCDDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1317007$DAF5E5EF-A08A-465E-808F-5DBB5DCF9FC5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8ecd80b77168392170e7254d117f108fd70e7efa","datavalue":{"value":"527398","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1317007$7DF25494-164A-4097-A8A7-06BF71BB6F44","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc7de13e1ec61a6d90ee3bb3490f2d9daf13111b","datavalue":{"value":"parallel processors","type":"string"},"datatype":"string"},"type":"statement","id":"Q1317007$DCE49EC5-1FC7-4F35-8AAB-62825C4FDA81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c325b6fd937c827dbc6d2e6598c246493dad9913","datavalue":{"value":"weighted flow time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1317007$23B3A449-3406-4A7D-85AB-E350FB7F365F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fad79bafbd21dfcfb56ade5bf07d65a9f40f5be0","datavalue":{"value":"asymptotic properties","type":"string"},"datatype":"string"},"type":"statement","id":"Q1317007$E3112EDE-B24F-40F5-94C1-6A77E02AA869","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e20d9662fd6a26b8901bb5fb0aee61151eca6eb8","datavalue":{"value":"uniform processor problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1317007$5D7964FD-E43F-4B0D-B1A9-55B46C29F415","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2499add345269c93c5ed1b650d8b90573cb6b1a8","datavalue":{"value":{"entity-type":"item","numeric-id":242846,"id":"Q242846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1317007$8FDC7B8B-FFBD-4FC7-AA73-94592E86055F","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":"Q1317007$1E1F8248-DC26-419A-B1EE-E575195A77A2","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":"Q1317007$0037340F-4A93-4193-8FB6-282E58353665","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d15190b4fc4ab12d8a44989183ab515c14f8bca8","datavalue":{"value":{"entity-type":"item","numeric-id":3315284,"id":"Q3315284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1317007$32848A5A-D9EA-4E72-91D4-6375914BFB2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf91d589b7422c3bd5126152fd793309d8b3739f","datavalue":{"value":{"entity-type":"item","numeric-id":3770267,"id":"Q3770267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1317007$A1FB2902-8CBB-45BD-B417-9AF847B2A9FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94689d731dcb0fb79295316eee7713ce7c245443","datavalue":{"value":{"entity-type":"item","numeric-id":3824091,"id":"Q3824091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1317007$AC647B9A-9783-4DDE-95F0-6593AD240149","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ddb2ff9e3148900f3238eb44a8641719b99ef98","datavalue":{"value":{"entity-type":"item","numeric-id":3329209,"id":"Q3329209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1317007$102A5D98-4217-4B70-9E2F-D94013DB2D01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8190d2c99be27c9c7b9cde7af52de10373476d7d","datavalue":{"value":{"entity-type":"item","numeric-id":1197880,"id":"Q1197880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1317007$B48E73F7-C18B-405B-9228-E3C9F6247BFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"488f2a801841893445353ffeb66e399e31a77049","datavalue":{"value":{"entity-type":"item","numeric-id":4005798,"id":"Q4005798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1317007$C244D398-A7E0-4F9A-96C6-30D209E565E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b53599a7fea5b8dcf02c4e4cc3f099f2f51d005","datavalue":{"value":{"entity-type":"item","numeric-id":922283,"id":"Q922283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1317007$C2338F2D-55E7-4C98-92F6-DA1F7B5B36CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f8753a5aaa19a5eb1e0c30f480959c13579eb26","datavalue":{"value":{"entity-type":"item","numeric-id":4012780,"id":"Q4012780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1317007$FFD5B4DF-E725-4D44-8313-39F3E17045D6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9ecc5640aaf4ea5f06ec45c3f450f94ccc338ec","datavalue":{"value":{"entity-type":"item","numeric-id":4005798,"id":"Q4005798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"073c7d3bc867e7ebd82d37ea99a1008677474bfc","datavalue":{"value":{"amount":"+0.8817837834358215","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":"Q1317007$FEE87319-8B71-4F56-AC81-B917D274A6AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74ebc327a758c65520938a6c924fbfacb21b8860","datavalue":{"value":{"entity-type":"item","numeric-id":1197880,"id":"Q1197880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"073c7d3bc867e7ebd82d37ea99a1008677474bfc","datavalue":{"value":{"amount":"+0.8817837834358215","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":"Q1317007$432BB403-8943-45D5-A71D-785AEF51DD30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"52b560942df0cbcfdaf4e500bf3c3c08cc2b319b","datavalue":{"value":{"entity-type":"item","numeric-id":1129956,"id":"Q1129956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6078b83099f3ae182d9fcfa6063316686df13b0b","datavalue":{"value":{"amount":"+0.8596757650375366","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":"Q1317007$8106D81C-B765-4B4C-9D3E-DC6D71E27BCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56c3fc5c787e10c16de4eacf0fc809df2223eedb","datavalue":{"value":{"entity-type":"item","numeric-id":1806644,"id":"Q1806644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f1b2c6fa2e6c32f82983701c39224a72288e034","datavalue":{"value":{"amount":"+0.8491408228874207","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":"Q1317007$64D5AAEA-467B-4EB6-8CC0-1E19612ACE18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b30cf7c10b839279964e18ab3c891b5eae342435","datavalue":{"value":{"entity-type":"item","numeric-id":1310018,"id":"Q1310018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4f364275ba32466a555a7480a561f1188ca808a","datavalue":{"value":{"amount":"+0.8481191396713257","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":"Q1317007$0896E8B8-5EE1-40A7-AF85-517D3993F7BF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bounds and asymptotic results for the uniform parallel processor weighted flow time problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bounds_and_asymptotic_results_for_the_uniform_parallel_processor_weighted_flow_time_problem"}}}}}