{"entities":{"Q582203":{"pageid":583970,"ns":120,"title":"Item:Q582203","lastrevid":62936514,"modified":"2026-04-11T09:05:49Z","type":"item","id":"Q582203","labels":{"en":{"language":"en","value":"A polynomial algorithm to optimally schedule tasks on a virtual distributed system under tree-like precedence constraints"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4130179"}},"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":"Q582203$D4B273DF-258D-4C2A-B760-0D74DCE814DB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a420472fcacf20fb0b88e86f8901e148e4e836e8","datavalue":{"value":{"text":"A polynomial algorithm to optimally schedule tasks on a virtual distributed system under tree-like precedence constraints","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q582203$ED0326F9-FBF8-4A85-8434-BCBCC89AD11E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4e915a28729f3a57a4fccdde9a80e8a52b41064d","datavalue":{"value":"0689.90045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582203$E4E42F76-7F26-4F10-AEC8-F62F8D72586B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"aae663a3a7060abd154f8797e14b8f2eb7cd549e","datavalue":{"value":"10.1016/0377-2217(89)90216-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582203$22E49D6F-7DF6-411E-8674-06522B920625","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2c89d5939ca74040a3930791a0f4d9dba6dbf4c0","datavalue":{"value":{"entity-type":"item","numeric-id":496703,"id":"Q496703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582203$CB806ADE-9560-404E-A25E-92C575D5CCB6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38576f39a6df37711cb397d1408ced7e3814cc6e","datavalue":{"value":{"entity-type":"item","numeric-id":62319,"id":"Q62319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582203$56AE37C5-751B-43D7-9FBA-C8243B9D8A3A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q582203$824824C4-9B79-45ED-AB91-90441E27FD9D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2a64c959e1f20726b6bd63cba34383bb66d00386","datavalue":{"value":"Considered is a computer system with an unbounded number of independent interchangeable processors with independent memory. The paper deals with a job scheduling problem in which the jobs are depending from each other through a tree-like structure. This means that any ``root'' job cannot be performed before all ``branch'' jobs have been performed. In this situation the jobs running on different processors must communicate with each other because of the independent memory. We assume that the maximum communication time is less than the minimum task processing time. In this case the paper gives a polynomial algorithm for the optimal job scheduling problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q582203$69BC45CE-87B7-4313-B461-AFDA4A16D951","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582203$2E3BDD14-4C4A-417B-93A8-B6E4309DB2E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582203$9D2B7057-5CB4-47E5-881F-CA24666E5E29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ec3769495799f08479987ac368adf64f125a2b66","datavalue":{"value":"68N25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582203$37EEC6E9-23A6-4F2A-9693-1DD7B5D155CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582203$158D8C98-0295-49E6-83BA-64444B49FC38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"418d4d19aa7c87e33d52e580c9c108a1bc2de096","datavalue":{"value":"90C90","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582203$46B3DF1E-B5FF-4A9E-8B3B-197F8E6E67DA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"72c97a92c5c3559ee56ac3a819cf80e7a21f8fdf","datavalue":{"value":"4130179","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582203$E4B0A1C9-EB5C-4C21-99AC-AA3FD0EA67EB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"14dcbebcbe3b83ef13ba9c8b164ec516dd25646c","datavalue":{"value":"tree-like precedence constraints","type":"string"},"datatype":"string"},"type":"statement","id":"Q582203$BFAC9F05-95FC-4417-9B63-FA1F560FEB59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ddc14051a93e8c78a1da682d6f4184d91e9c6088","datavalue":{"value":"graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q582203$C2B967AB-2D7A-4655-8A93-B47CD961CC66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e225ac4aec700ae2c67cab0cb7802b0627e7a3da","datavalue":{"value":"distributed system","type":"string"},"datatype":"string"},"type":"statement","id":"Q582203$EB73B541-A6E7-4894-9C51-D3B6EF2ADD3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"909e2eaac56186650ac0287c5163009bf6e396fe","datavalue":{"value":"independent interchangeable processors","type":"string"},"datatype":"string"},"type":"statement","id":"Q582203$6C2C2695-B11A-4F0D-9398-AB7A62C4E141","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"93914bbc68eae64d6117bd8d3de1bbdbe5627c0f","datavalue":{"value":"independent memory","type":"string"},"datatype":"string"},"type":"statement","id":"Q582203$C70CD941-64E1-4B51-A695-44A042FCEEE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q582203$9D2D1EC7-3369-4DB3-A952-1B96D08582AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0c7f45d5508caffe16d0119570f5bee8a7624e66","datavalue":{"value":"optimal job scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q582203$0AFD07DB-C3BF-43A7-8AE2-A7CD9E48A7A2","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":"Q582203$169C69CC-8D40-41D5-9DF6-8D3DE9C3B9BB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6f2523ba20ab48a970ee44421c89b92d335c8061","datavalue":{"value":"https://doi.org/10.1016/0377-2217(89)90216-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q582203$DC76C3AE-A50C-4B66-81C9-F2DEF3FF7629","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4578c0b7bd3bcdabe905446538960e93e59bb3b2","datavalue":{"value":"W2057461902","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q582203$334B1876-0B8E-474F-9236-E7351A93FC5F","rank":"normal"}],"P223":[{"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":"Q582203$8E77A19E-3D4A-4914-B5CF-B75B1CA89E27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2eceaca992e1087373bf441a63a5275f034836fc","datavalue":{"value":{"entity-type":"item","numeric-id":4068433,"id":"Q4068433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q582203$A3E6CE5F-A57F-4657-8A24-130B9F1A32D9","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":"Q582203$F06DBD1F-7465-4C9F-89B1-2238442896FC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4884a743bd65bffa0fd2f0cf2731a424cc20485d","datavalue":{"value":{"entity-type":"item","numeric-id":1278306,"id":"Q1278306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ebd77704225d94f9cd2000a317ad77e73638977b","datavalue":{"value":{"amount":"+0.8506063222885132","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":"Q582203$C8A92885-B9A6-4BEF-91CF-03CDC2192A28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"482fb0de8f95510ce34b8866f91fe1b2c7117ac8","datavalue":{"value":{"entity-type":"item","numeric-id":1327224,"id":"Q1327224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e69fcbe465c26b5762d408433458938aab3093a8","datavalue":{"value":{"amount":"+0.8242364525794983","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":"Q582203$8F2CE535-3F96-437C-92ED-1DE18C140A53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc6222734bb58dca6d3093f196b13c08d41e287e","datavalue":{"value":{"entity-type":"item","numeric-id":3468873,"id":"Q3468873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bfd04fa933800f8d757f43bbb1107c16578a3f29","datavalue":{"value":{"amount":"+0.814319908618927","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":"Q582203$D5CDF22E-C33D-42E3-BC25-34E8BC743872","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74426e15e1837ad4a01b40188e0df1f9ce76a9b9","datavalue":{"value":{"entity-type":"item","numeric-id":1904382,"id":"Q1904382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79d12aad2c6209dc88660a6f6917f8cba4bc42f7","datavalue":{"value":{"amount":"+0.804094135761261","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":"Q582203$4BD9C1EE-5AAD-4275-B878-36FB6CE3D383","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed27e23ca1c3ae7f2b841285d32d3fbc7fae0868","datavalue":{"value":{"entity-type":"item","numeric-id":4724421,"id":"Q4724421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79d12aad2c6209dc88660a6f6917f8cba4bc42f7","datavalue":{"value":{"amount":"+0.804094135761261","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":"Q582203$CC0A0A09-165F-41E7-A5F0-A6297DF85B30","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A polynomial algorithm to optimally schedule tasks on a virtual distributed system under tree-like precedence constraints","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_polynomial_algorithm_to_optimally_schedule_tasks_on_a_virtual_distributed_system_under_tree-like_precedence_constraints"}}}}}