{"entities":{"Q806667":{"pageid":808515,"ns":120,"title":"Item:Q806667","lastrevid":64518915,"modified":"2026-04-11T20:26:06Z","type":"item","id":"Q806667","labels":{"en":{"language":"en","value":"Bounds for nonpreemptive scheduling of jobs with similar processing times on multiprocessor systems using the LPT-algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4207213"}},"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":"Q806667$3A0520D8-67B3-4FE0-BC9A-699FEB71B446","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ee643733f9babab213516540dc14ff57897c99f7","datavalue":{"value":{"text":"Bounds for nonpreemptive scheduling of jobs with similar processing times on multiprocessor systems using the LPT-algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q806667$F1B4DF7A-8606-42E5-B1C0-D6905D205EBB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"103978fb5b2711695f67f236a22fa07341253ee4","datavalue":{"value":"0729.90053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q806667$8C6A98EA-3ECB-42ED-8BEB-12A0260ED4D7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c0bfd9b640f0180cd6464c5ce11c92ae0726eca1","datavalue":{"value":"10.1007/BF02238297","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q806667$512C64DC-0EAC-4407-9440-D33157EE6B44","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b79ece58f33b59758a066cb6b9ee149bab3a2c9a","datavalue":{"value":{"entity-type":"item","numeric-id":167642,"id":"Q167642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q806667$9953D161-5642-4422-8944-1E70ADAAB1F9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q806667$3C2F7AC7-202B-4396-A998-F25BEDA1081B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c17db6d4e71aac3d29519abf58723e5b77a52ac7","datavalue":{"value":"The well-known, NP-complete problem of scheduling a set of n independent jobs nonpreemptively on m identical parallel processors to minimize the maximum finish time is considered. Let \\(\\omega_ 0\\) be the finish time of an optimal schedule and \\(\\omega\\) the finish time of a schedule found by the Longest Processing Time (LPT-)heuristic. We will improve the Graham-bound for the LPT-heuristic \\((\\omega /\\omega_ 0\\leq 4/3-1/3m)\\), which is tight in general, by considering only jobs with similar processing times.","type":"string"},"datatype":"string"},"type":"statement","id":"Q806667$7DA15680-845E-41D5-8D29-04BC38EDC180","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q806667$DC1B3756-AA5E-47B6-A497-09D39BC805C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q806667$B61701AE-4742-4394-A868-88F8A3614D44","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"977ee7f7147d30af837f37afce6b1acfe8437169","datavalue":{"value":"4207213","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q806667$49596D66-8090-4812-BF75-0C0E0B3FED1C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d8d38228fccf03d8ea62140a5a7888db058af7b","datavalue":{"value":"nonpreemptive scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q806667$0496F4EC-A679-4FF9-B857-265ABA73233B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e2c617fa26fce196a02401296ade49036a02b19e","datavalue":{"value":"worst case analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q806667$B8942DB0-F147-445B-BAB6-3BCE5F0C9368","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dabe7ab3da79233737cc9b8e608fd8326ec65a7b","datavalue":{"value":"identical parallel processors","type":"string"},"datatype":"string"},"type":"statement","id":"Q806667$92EB0A51-E29F-42E5-8F88-E5F4F8D2ED34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c23699510207f6d0494f9c2a09681690c9cce7e","datavalue":{"value":"similar processing times","type":"string"},"datatype":"string"},"type":"statement","id":"Q806667$4463D684-6101-44B3-8C60-D49F1485876B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ec51fa007de578c25240787d9d2f9961dbdea3da","datavalue":{"value":{"entity-type":"item","numeric-id":257208,"id":"Q257208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q806667$15470F47-1D3A-4ACF-8C21-81A58322E4C9","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":"Q806667$F1E72E7B-7A48-4C42-9AAB-47D2AE250579","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2fa50a3fd9fcb80710777f0ff18532f942a078a7","datavalue":{"value":{"entity-type":"item","numeric-id":3900980,"id":"Q3900980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q806667$D00ABF87-A391-42FE-B809-130EC21ACD64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9661dc321e9197c44616cc21a898b0798188a31","datavalue":{"value":{"entity-type":"item","numeric-id":4131987,"id":"Q4131987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q806667$EE94084C-47B1-4455-9C6A-66656E63B23B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a62af7ec2eae31085b45e2485228d8678c8c12b0","datavalue":{"value":{"entity-type":"item","numeric-id":4151721,"id":"Q4151721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q806667$29F3FCC0-1B8A-4EA7-9EB1-993036AF2354","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":"Q806667$F93B154B-8BE5-4E90-96C2-E64B68D6C8C3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5600f0834b533f18dcaaa73968aaa5d5b16a8721","datavalue":{"value":"https://doi.org/10.1007/bf02238297","type":"string"},"datatype":"url"},"type":"statement","id":"Q806667$006B9771-799A-4C14-B120-F46FE59E0543","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9056fdc7043ed6695492f2f4f8a16fb3a60c0e47","datavalue":{"value":"W1546966627","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q806667$120E3F6A-FE9D-47BD-A28C-D7965E6593CE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ec2acacd85b8acffc492a9a7e2e82cf8463a26a","datavalue":{"value":{"entity-type":"item","numeric-id":583889,"id":"Q583889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de5122487a22a0b783643b1f6378557f4fbb7be8","datavalue":{"value":{"amount":"+0.8671955466270447","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":"Q806667$E9FC14F7-715A-45B1-A29D-23F6262CD99F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a78e8090446643860a85c583e81a84f501dd1d3b","datavalue":{"value":{"entity-type":"item","numeric-id":3989473,"id":"Q3989473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5087e00e84f7b5efd460029ee890422d086095ce","datavalue":{"value":{"amount":"+0.8632662296295166","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":"Q806667$7A5C323F-D428-4C67-9B5C-D15599BF832A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4e1d653e75e68be8ba791a86552fd68d5130e0a","datavalue":{"value":{"entity-type":"item","numeric-id":5903677,"id":"Q5903677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc7e6598c25d6766956cc6de48043f9789319151","datavalue":{"value":{"amount":"+0.8619192242622375","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":"Q806667$D92DDCA1-B569-41AA-B1C5-4230674FDDC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b719767aade05547a230b3846b15758d72b4924d","datavalue":{"value":{"entity-type":"item","numeric-id":4514752,"id":"Q4514752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28710e6096e6580ec6a8a1ae72e840799f92fb49","datavalue":{"value":{"amount":"+0.8576682806015015","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":"Q806667$FF55F276-AE32-4BCA-882E-568CF5AE8F8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"421935406768af710e02bf482d81f188fe7b8901","datavalue":{"value":{"entity-type":"item","numeric-id":1196214,"id":"Q1196214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f312e6060b9ce64743d14ef1c7710f514f1d1abe","datavalue":{"value":{"amount":"+0.8572183847427368","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":"Q806667$B7EBFA85-D64B-48AA-A142-C5774E499DA8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bounds for nonpreemptive scheduling of jobs with similar processing times on multiprocessor systems using the LPT-algorithm","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bounds_for_nonpreemptive_scheduling_of_jobs_with_similar_processing_times_on_multiprocessor_systems_using_the_LPT-algorithm"}}}}}