{"entities":{"Q1111371":{"pageid":1122120,"ns":120,"title":"Item:Q1111371","lastrevid":66688554,"modified":"2026-04-12T11:59:36Z","type":"item","id":"Q1111371","labels":{"en":{"language":"en","value":"Scheduling tree-structured tasks with restricted execution times"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4076608"}},"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":"Q1111371$8EE447A5-9862-4E94-AF45-724650657F57","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"921cc28b0f4b5b7e2d8fd9042c560a809b2e45bb","datavalue":{"value":{"text":"Scheduling tree-structured tasks with restricted execution times","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1111371$BA6CB56C-5EBE-4AB7-A338-0553B7F457D9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"51a00ea805c705f80f314420b0210d323541e01f","datavalue":{"value":"0658.68040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111371$F56CEFD0-B2EA-4EA7-895D-EE7734F95663","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b38199d6ea59d9332a3946f3210e16935f3a897d","datavalue":{"value":"10.1016/0020-0190(88)90206-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111371$6C71E72B-02B2-4F6B-ACA3-1D83001F4A73","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b4af00457c53c070f202253e50a66260bb73f5ba","datavalue":{"value":{"entity-type":"item","numeric-id":210310,"id":"Q210310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111371$DD13C446-81EB-47E4-86BF-8D7CA6404901","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7efaf52410f4d24af29b36d2612dec346adb566b","datavalue":{"value":{"entity-type":"item","numeric-id":601474,"id":"Q601474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111371$CA783BAD-6CD0-4BA6-A34B-7D7E5158BB6B","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":"Q1111371$B88F6593-C023-4508-9D62-8348C461DBA9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1111371$7CF57B98-109C-460F-9B9B-0FD9EAA53C50","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0ca29bebcd1a8466149ca0ff372841081d087eb1","datavalue":{"value":"We show that scheduling a tree-structured task system with two execution times in order to minimize the schedule length is strongly NP-hard for an arbitrary number of processors. If the execution times are powers of some integer \\(r>1\\), then the problem is NP-hard even for two processors.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111371$66F41576-B301-4F3D-B0A5-0DB5A49D9758","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111371$17FB7C8D-A426-4446-AADE-BDF510752D06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111371$CC9BFAEE-A508-4510-B8A1-C8AE200BC289","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"22b2d3e9f7ea3bb99a6d799e663747ee8e0edc7f","datavalue":{"value":"4076608","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111371$B4B2D750-0A44-4492-8739-0EF791668B44","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111371$FEAA3AA8-5D4C-4CA9-AB02-D7D690E4574C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d5e4886aa4290eca104cd0d1da319d8b4d34c4","datavalue":{"value":"NP-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111371$19CC402E-7620-414D-8C0D-69E5E4DB3881","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2484ef43bc9c784b4200ae297f0d99c551e12110","datavalue":{"value":"multiprocessor scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111371$EDCB9EFB-A4F0-4931-B2A9-437A9A6DF501","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ad38154a0d1f0865d2c24f3aff1097300359478","datavalue":{"value":"tree-structured task system","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111371$F078A5B0-A534-41C0-8AD5-63380B949D3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dcd6d8a02d18a63e73ae762c4ebdd03cda0442f1","datavalue":{"value":"schedule length","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111371$0EA1D9F9-A515-4B53-80FE-684F7AEA5EB6","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":"Q1111371$978DFB1B-387B-450C-920B-06221DEFDDA9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b0bebf2a7f7b4192e4685120a0abc662e2280909","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90206-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1111371$48A4D6C6-47D1-46F4-B3AF-7918207A2F2C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0933045533edbcfa63ee74b348f24419075cc8d9","datavalue":{"value":"W2019483472","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111371$8DDE960E-C803-4FC3-A0DB-B3DC55851793","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":"Q1111371$3275324F-03DB-4808-AE09-E967FC317A1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3724e03555dba58b1b3298458f11a6d6a1dca425","datavalue":{"value":{"entity-type":"item","numeric-id":1100914,"id":"Q1100914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111371$B5E67444-AE99-475D-9E82-86520279B76A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6d199017df4d3146f497fbc8db45c8d467a421d","datavalue":{"value":{"entity-type":"item","numeric-id":2556224,"id":"Q2556224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111371$F20DEC48-5264-4707-BBB0-D55C192D6F69","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":"Q1111371$F464ED4C-6BC9-4B8B-B043-3B723692BA93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f17e2e349c19e9c6e76fa0a21796c33eac70800","datavalue":{"value":{"entity-type":"item","numeric-id":3939585,"id":"Q3939585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111371$1ED8B162-24D9-48FE-BB76-4508B4D30682","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"87af12f6ff9a1e1ca8869f3bfb847f32260ea7ae","datavalue":{"value":{"entity-type":"item","numeric-id":4741698,"id":"Q4741698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111371$11980158-B318-47BE-95A9-0A544706EBBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49a089d2d23a33fbf3167ad429a459b6de513dd1","datavalue":{"value":{"entity-type":"item","numeric-id":1220386,"id":"Q1220386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111371$C5A2BA66-5B33-4BC1-A0D4-F9C3FBA5E76C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb61f769c37a0e6892b8e7fc6bb4d4596093b049","datavalue":{"value":{"entity-type":"item","numeric-id":3826356,"id":"Q3826356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c2ae5617694123efddfc502e1cff420f1ca612e","datavalue":{"value":{"amount":"+0.8558230400085449","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":"Q1111371$85CEE32C-1A05-4D69-A2BE-E642840EA0DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54226255698295f938db0f5c470f8584bfba26d9","datavalue":{"value":{"entity-type":"item","numeric-id":2464442,"id":"Q2464442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16e0db07a188c0c28c07eebbaed9d852a9805c50","datavalue":{"value":{"amount":"+0.8362765908241272","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":"Q1111371$7F58478C-1FDB-4401-B4E4-37441E268E3C","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":"3b137ae4b8ccd9714066b6f07d94e1fba0c33c77","datavalue":{"value":{"amount":"+0.8185635209083557","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":"Q1111371$0508408A-947F-482B-AF86-ECA141678E2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0caee8c758baab73d079329b3c2a1c5c465d6c8","datavalue":{"value":{"entity-type":"item","numeric-id":4864438,"id":"Q4864438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ac7223725d0a995d3021f5710c3e3ddf47869f5","datavalue":{"value":{"amount":"+0.8045656085014343","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":"Q1111371$847A787A-815C-4E0C-8425-873AFF32829A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be2cf257d42208ba046c7964bb898beb76d87dc4","datavalue":{"value":{"entity-type":"item","numeric-id":1767690,"id":"Q1767690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18362cfccd6d315c07fbd31b7f5dc8f5ab299101","datavalue":{"value":{"amount":"+0.802005410194397","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":"Q1111371$9AF00CD7-6969-4F95-B93D-8D246602BAE7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Scheduling tree-structured tasks with restricted execution times","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Scheduling_tree-structured_tasks_with_restricted_execution_times"}}}}}