{"entities":{"Q1197982":{"pageid":1208731,"ns":120,"title":"Item:Q1197982","lastrevid":66846633,"modified":"2026-04-12T13:15:16Z","type":"item","id":"Q1197982","labels":{"en":{"language":"en","value":"Scheduling multiprocessor tasks on three dedicated processors"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 92063"}},"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":"Q1197982$983EB711-1A3E-49EA-A31F-5D47B9D8BA34","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b839e87eff1dcb0f99594dc551e5489a5c78e669","datavalue":{"value":{"text":"Scheduling multiprocessor tasks on three dedicated processors","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1197982$333D598E-8829-4DDA-BDC5-770542550A3D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ded81c61c403b45cf670539a9a7b58d0b25c7a15","datavalue":{"value":"0776.68023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197982$809CC772-B892-4BAE-BA14-A980764AA3B9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"979bad6300f5ffdbfcc135402969019ce7cfb007","datavalue":{"value":"10.1016/0020-0190(92)90172-R","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197982$3117B70D-2DF3-4F88-8088-2F585789E8A6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197982$4AEF344E-12A0-46F5-AE04-C0BEE856D7C9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1197982$9C9F4D09-93B5-4679-B502-92003F674DDB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"44ea491a0d165424a8378920d58d45cb3052f490","datavalue":{"value":"The authors analyse the problem of scheduling a set of uni- and duo- processor tasks on three dedicated processors. The objective of the problem is to find a schedule with minimum length. The general problem is shown to be strongly NP-hard, which strengthens the best known complexity result. Finally, they present polynomially solvable special cases as well as an approximation algorithm for some hard subproblems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197982$A49B1083-0EDE-47E2-BA36-4A1983CEAF6E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197982$151F02C3-81FB-490F-8920-359F7FBB0D6E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0823b48051247471fdaef731d92b37e2ab25f247","datavalue":{"value":"92063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197982$3A7C33E4-4246-4DEB-8D51-4CBF7CA653C7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"db5e0888fa9957c443e210eb3c88f717e276ae13","datavalue":{"value":"parallel processing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197982$2681146C-B61A-4875-85E5-FC34B1760CCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197982$04838905-79BE-4CDF-8C77-5DCCD8BDD81A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197982$9FCBBC3B-0E83-4214-A370-9115B1BF1143","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4be94e0652db58f3504a5ea05be6df619cad5a25","datavalue":{"value":"resource allocation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197982$6EA7C6D4-8965-4C85-9696-8AC19627A1EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0605a1f2800486f9350885e9d3e822d311d76006","datavalue":{"value":"scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197982$DF7F8117-5C53-499E-8D4C-C398DBA507E1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9ea65ac05d3711d20bfd41cd5b0225d93e7a7d58","datavalue":{"value":{"entity-type":"item","numeric-id":224835,"id":"Q224835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197982$02C8D72E-0E83-48B3-8633-193F70615343","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"05f8aaa1fcaa350ea29e602aa878272ced422c6b","datavalue":{"value":{"entity-type":"item","numeric-id":190513,"id":"Q190513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197982$448FC365-F8A0-4C71-A276-BEE1046D873C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"aa02a2ca4d44c84d8cb934a3c290133e9f2c336f","datavalue":{"value":{"entity-type":"item","numeric-id":210314,"id":"Q210314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197982$A7F09636-DB7F-474E-8248-4C00FEE282FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6ce908d42d46f65570609fc9e66688458e840f38","datavalue":{"value":{"entity-type":"item","numeric-id":835556,"id":"Q835556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197982$BEE9B9F5-ADA1-4430-9487-CCD430757BCD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"db03c62d3fdb76a66177e81b54d14a2f5ae490f1","datavalue":{"value":{"entity-type":"item","numeric-id":237429,"id":"Q237429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197982$638F7945-FBAB-4E80-BA6E-BE7DEEA4AB72","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":"Q1197982$7D5683DC-39A0-4F0C-8149-B1DA1AF17D0E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a60592c400816b7215f068b2c0796c2a4d6449ab","datavalue":{"value":{"entity-type":"item","numeric-id":3741047,"id":"Q3741047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197982$B972A28E-EB7E-424C-BCBB-5F129FF0BBEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a985baf46c569fe978828248253cd375aa5062a","datavalue":{"value":{"entity-type":"item","numeric-id":3832306,"id":"Q3832306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197982$1CEB5495-1C65-4FE4-B0DB-9F8FC4986C88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e65d73ae8ce50631a13a2e25599a048bc2eda73","datavalue":{"value":{"entity-type":"item","numeric-id":4158479,"id":"Q4158479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197982$0C70AC58-8624-4140-84D0-518B377346EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f45afeab2013416479fec88432b03cc9d8594056","datavalue":{"value":{"entity-type":"item","numeric-id":1107984,"id":"Q1107984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197982$01924552-1918-4C8A-8CE7-4FFFA78125A6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ea01f810b35ecb5588856623eddf61eef05f8a48","datavalue":{"value":"https://doi.org/10.1016/0020-0190(92)90172-r","type":"string"},"datatype":"url"},"type":"statement","id":"Q1197982$FE512551-2956-4503-8F85-28856E93B561","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a9dbf6d32648dd0ef99fdc9cec5459cae10f20c7","datavalue":{"value":"W2038534673","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197982$CF335366-A01C-4693-ABD6-B628AE015F66","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f57f11dd46644e19ce4a40bffa00ec53a40144c0","datavalue":{"value":{"entity-type":"item","numeric-id":1421466,"id":"Q1421466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e2f0e384f42cd77da272e0ad966be667dd90e90","datavalue":{"value":{"amount":"+0.9106541","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1197982$7BEECAC4-5EF8-404E-86A9-0925D1F4779D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51f68f2f8a8caa3a73c35dd8b177b09db2b90e86","datavalue":{"value":{"entity-type":"item","numeric-id":1356693,"id":"Q1356693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"885f843a3e7b3ae986ddc58d2213c5078f8f3e2d","datavalue":{"value":{"amount":"+0.9092454","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1197982$D491CC81-BF98-4BD9-A15F-1B1FA06D8386","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a41dd62ef121f6c5b73f0fde277ded78310494f","datavalue":{"value":{"entity-type":"item","numeric-id":1904737,"id":"Q1904737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a80c8b13d705d21b24a5673fdea13c188eb3958e","datavalue":{"value":{"amount":"+0.9002079","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1197982$E46E907B-1E3E-4975-93CB-4F7A910E04B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e750fef67e242f7ee486d64d8ec1cfe94380395a","datavalue":{"value":{"entity-type":"item","numeric-id":4427860,"id":"Q4427860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"726be1aa24faa935ae93cf83a48909a3b731cbba","datavalue":{"value":{"amount":"+0.89978087","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1197982$890BF7BF-4558-429E-9846-325D82DAB195","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f5e63c6c5bf2ac13ade0659db1d5ad2a0e7b30a","datavalue":{"value":{"entity-type":"item","numeric-id":1278297,"id":"Q1278297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3de80c4dec619f34ffea14872082cb22c37a12ca","datavalue":{"value":{"amount":"+0.88796294","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1197982$278F51B6-17A4-42CE-B635-F98368CBD60D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32e6a1d76d1f55fade36d0d2d92aa72f9b2cbdb6","datavalue":{"value":{"entity-type":"item","numeric-id":1177707,"id":"Q1177707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a711025ca6ee91ed68ba5310db7fd115dfbe34fd","datavalue":{"value":{"amount":"+0.88516396","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1197982$AC12E9E2-63C9-4FBE-9A1A-B4F841DA40E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a84dc02dd847fe6ba090695b898bf5d7141a86e","datavalue":{"value":{"entity-type":"item","numeric-id":1383800,"id":"Q1383800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"062989abc6fb40ad256c4a97b294ba5676d1790f","datavalue":{"value":{"amount":"+0.8840231","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1197982$B0EE8B9F-FCAB-4870-BB89-FD368F723DBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"443e8d571a7594545b24b077d9137f23a0fa9967","datavalue":{"value":{"entity-type":"item","numeric-id":2282535,"id":"Q2282535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f16038733523fa7a20722b428948ef1988f6ecd5","datavalue":{"value":{"amount":"+0.8799011","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1197982$3058942B-61BB-41AB-8B7A-77C76372E6E3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Scheduling multiprocessor tasks on three dedicated processors","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Scheduling_multiprocessor_tasks_on_three_dedicated_processors"}}}}}