{"entities":{"Q1331888":{"pageid":1342638,"ns":120,"title":"Item:Q1331888","lastrevid":70733277,"modified":"2026-04-13T16:23:57Z","type":"item","id":"Q1331888","labels":{"en":{"language":"en","value":"Analysis of scheduling problems with typed task systems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 626246"}},"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":"Q1331888$BD84CE42-1A50-4DC9-9183-0D41A9DA8E60","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"de2120ab2fe6b5f8c993a4e41c763d1dec25feb4","datavalue":{"value":{"text":"Analysis of scheduling problems with typed task systems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1331888$DACFCB06-E2F8-4A80-A2E4-EA699F5B5DB1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3da1017c64133b575ad80b56b5e23ed8dcf17404","datavalue":{"value":"0822.90083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1331888$68FEC882-FD40-46B8-A828-11D16B21415F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"95f3dbbfeb6f00ff857a94d62d24b2a88ba2eaac","datavalue":{"value":"10.1016/0166-218X(94)90142-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1331888$C56D6BEC-CCA4-449B-9CDA-2A990627E5C5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"38a47e2531a4bf8122b29daae2886484554c2a60","datavalue":{"value":{"entity-type":"item","numeric-id":243609,"id":"Q243609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1331888$F84062B2-DFD6-4760-B080-3C82B07286E7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1331888$78E72DB3-2201-4431-B2CA-425CFC1EF985","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b5c9e4c93221b65868a4d2090be3649841672715","datavalue":{"value":{"time":"+1994-09-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1331888$877C1315-1C41-45B9-9E5E-D5B7ADE9DA28","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cf1ed24775dd6064e1e2dd075fb28345a8e57ed6","datavalue":{"value":"This paper deals with the analysis of a scheduling problem where each task has a type and where only a bounded number of processes of each type is available. It is shown that the typed scheduling problem remains NP- complete for a disjoint set of chains, two types and one processor of each type. If the deadline is a constant number, this problem, given \\(k\\) processors, remains NP-complete for out-trees, in-trees and disjoint union of chains.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1331888$F1AC47E2-1AFF-4B40-954A-9EEAEE22B010","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1331888$EBEB665C-3A3D-4E65-A6B9-ED9C86E992FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1331888$6C4376C2-B57C-440C-BC7A-16554AC49809","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1331888$64C1755D-FB66-4846-9883-4C70B25F0AC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1331888$7B26470C-E08E-44A5-B503-EC5439504B58","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6aba93898f45f32b408e29543eb3671f7ac1f845","datavalue":{"value":"626246","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1331888$B5549420-355F-46D6-934D-30B702218813","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bfacffaf05240d50313998cee74253d41d39a301","datavalue":{"value":"typed task systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1331888$B512EEE4-8200-4A2C-8F19-E4C11AD8C366","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1331888$69E5480C-5473-42AA-9302-50E8932A168D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3a513444161f0a86e46ccdc9f23443f6fe343e95","datavalue":{"value":{"entity-type":"item","numeric-id":275070,"id":"Q275070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1331888$50023677-2CD6-4709-8689-2882442EF4B0","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":"Q1331888$26430E70-60D1-4942-AA97-E4EA3074E9A8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"64383020fa2e3e8c559dd3154b8bd1fa762e3510","datavalue":{"value":{"entity-type":"item","numeric-id":5375487,"id":"Q5375487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1331888$D76EA70E-1103-4C17-A3EC-C85F59E57F23","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":"Q1331888$227CC687-7E54-4AB2-BE04-A47D8C043254","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62d719daed8231b4797f9e1df9486fe0e413784e","datavalue":{"value":{"entity-type":"item","numeric-id":1185984,"id":"Q1185984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1331888$F7A9DE36-DE95-4AB0-81C2-435F2BB73B7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eab28dee024bf7d24f20a12a054e9f818b17b7b5","datavalue":{"value":{"entity-type":"item","numeric-id":4147824,"id":"Q4147824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1331888$BDC0ABF4-CAAA-424E-A6E9-9EC1B8FC9971","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63e9bf34936f98d838af76700dfdf669f4232c23","datavalue":{"value":{"entity-type":"item","numeric-id":3929047,"id":"Q3929047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1331888$5B0C02AE-F110-436E-B12F-CBF417A45508","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c63844c2e38245fdc6612bce29c35b91b812a27","datavalue":{"value":{"entity-type":"item","numeric-id":3854618,"id":"Q3854618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1331888$70C3FF34-FE40-43C0-AA1E-81B6B2BAA661","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":"Q1331888$680B6182-BDBE-4A62-BFF5-CF4A8F66E063","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3560eb7fbf9e7c5d2af6dbd3c8c9c05c631e4a94","datavalue":{"value":"https://doi.org/10.1016/0166-218x(94)90142-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1331888$BB1C7A81-A37B-4AB8-BBA3-80328B4BCAA1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"73affa9ffd48f0b2b754985d3f4e4b574acb1e65","datavalue":{"value":"W1990630852","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1331888$D1D481E5-460D-4C49-8751-AE26E40EB9A8","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"7344c5aace21d313f1644b92cf0eaf18f0905d14","datavalue":{"value":"Q126839747","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1331888$3F4E2778-DE18-477D-BC6A-5B2558943DBA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c2c9c45d9bd555dab5743f876bbe26877383d4d","datavalue":{"value":{"entity-type":"item","numeric-id":3319772,"id":"Q3319772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6feaddb0ff30189835702d246e1cc9fd7bb28d73","datavalue":{"value":{"amount":"+0.8025473356246948","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":"Q1331888$478936A0-740F-4E96-B642-35E6A472642E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a46e87bff4f4b1f5d15bef7de32811b19505489","datavalue":{"value":{"entity-type":"item","numeric-id":4281628,"id":"Q4281628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"558c3f5de0159564af53aac499e503c59a36d14e","datavalue":{"value":{"amount":"+0.7998457551002502","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":"Q1331888$42018E83-4ADA-4E2A-90C0-289904907DEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12afa7990fd05b1a1a306697bd8ccdd76758e9cf","datavalue":{"value":{"entity-type":"item","numeric-id":1910619,"id":"Q1910619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de77e148c4eca7d73ead39996681a434f3e6c0c4","datavalue":{"value":{"amount":"+0.7984899282455444","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":"Q1331888$9B791639-8E74-4BAB-B1AB-49BF6F26FEAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"579685a34d4ecad58816d87267bf1db3c641d4dd","datavalue":{"value":{"entity-type":"item","numeric-id":1019301,"id":"Q1019301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48cbcbcf74e4cd78fcbf20cd0a55dc5de7ffc21b","datavalue":{"value":{"amount":"+0.7946851253509521","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":"Q1331888$7FA645AE-5E7C-45E5-B837-4B33E73A936E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Analysis of scheduling problems with typed task systems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Analysis_of_scheduling_problems_with_typed_task_systems"}}}}}