{"entities":{"Q1062616":{"pageid":1073368,"ns":120,"title":"Item:Q1062616","lastrevid":66661314,"modified":"2026-04-12T11:38:12Z","type":"item","id":"Q1062616","labels":{"en":{"language":"en","value":"The poset scheduling problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3914069"}},"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":"Q1062616$ED2B9316-DC05-445C-BC15-A59C48BE9817","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e096e65117983b551d4389b320583b2392dfaf8c","datavalue":{"value":{"text":"The poset scheduling problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1062616$FBB08E95-2F22-4BFD-8E57-03265CFF84B6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8264bc07cbaae13a07ae80d517d7c95105b0e9ee","datavalue":{"value":"0572.90055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062616$C1C1342F-6B3D-45A2-9AA2-AAE500F993F5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1a7c2d9c0b6a606dc3695609e3a84d522f4a0a74","datavalue":{"value":"10.1007/BF00334849","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062616$445780D8-88CA-4F66-AEE5-F803B1DB4CD3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8dbc842d5eaf927385a86766f1454e06a1c019ee","datavalue":{"value":{"entity-type":"item","numeric-id":204137,"id":"Q204137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062616$E8C70911-E40D-4514-BC90-14D7EEE5768E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0b01296838df87730769f910acaeeb4756766580","datavalue":{"value":{"entity-type":"item","numeric-id":400523,"id":"Q400523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062616$60B03228-BBB0-467F-9231-35D36FEE0073","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e2599ed8061d57585b4363072a1afceea2452436","datavalue":{"value":{"entity-type":"item","numeric-id":172073,"id":"Q172073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062616$36421809-643E-44D4-B2E3-A3999C97365D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1062616$3A866423-B51C-490D-B768-4CFCC458E7F1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f61311c23f65ec62d8aef8b0efc2e584f06167cc","datavalue":{"value":"Let P and Q be two finite posets and for each \\(p\\in P\\) and \\(q\\in Q\\) let c(p,q) be a specified (real-valued) cost. The poset scheduling problem is to find a function s:P\\(\\to Q\\) such that \\(\\sum_{p\\in P}c(p,s(p))\\) is minimized, subject to the constraints that \\(p<p'\\) in P implies \\(s(p)<s(p')\\) in Q. We prove that the poset scheduling problem is NP-hard. This problem with a totally ordered poset Q is proved to be transformable to the closed set problem or the minimum cut problem in a network.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062616$8D9CD404-EDEB-4606-BAE7-B0F2F711F7A2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062616$EC1AEB90-5D98-4C03-A298-AA6628DA1370","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062616$CFC9D357-9991-4F42-92AD-2B6108C35950","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fe882a3fe28920702278a0886094ed2f58b2ef0a","datavalue":{"value":"3914069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062616$FB461A4A-9890-4660-94BA-BE6A3105BB2E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062616$5764CCCE-96F8-4CEB-97F6-A29972AF4CAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a55727292095caa67324dfeb59eafc6c116def37","datavalue":{"value":"poset scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062616$FDE627E4-394B-4A66-BC96-A53EBFC5ECA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062616$F7320E2C-BC96-4DA0-A552-F3ED8141D683","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"08565007b2094f9d858e9769b5ea8559d243f05a","datavalue":{"value":"closed set problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062616$27DAF1FE-65EE-42A5-A953-5C6F43EBDE75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e9342ab1f185d9365d24e3322133b0fbd82de41f","datavalue":{"value":"minimum cut problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062616$0422CCF8-067C-434F-AEB1-8C2FE7036995","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":"Q1062616$73FE088E-F099-40C3-8401-59E353AAE7D1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"13acc4e9781e9435ae0be490daf8ddb760a30db2","datavalue":{"value":{"entity-type":"item","numeric-id":1249132,"id":"Q1249132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062616$EFE7D083-8DD2-4B52-BBB4-7858521EA7CB","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":"Q1062616$ED226A25-1280-4C7D-9A4C-F834FDAF0D3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23fe0b762ba59e21ab429837d2d6d47161fd5d6c","datavalue":{"value":{"entity-type":"item","numeric-id":4151722,"id":"Q4151722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062616$8F3A150B-37F3-4F54-9373-DC6B25C4177F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f5704113713d5488691e067256f648833fc5a37","datavalue":{"value":{"entity-type":"item","numeric-id":4108358,"id":"Q4108358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062616$6A426948-1593-439F-98D7-4D3D1E745FE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"542c41dea1d7ed36276c4cad8ddc18eb9f89fee8","datavalue":{"value":{"entity-type":"item","numeric-id":3967364,"id":"Q3967364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062616$76D59FE5-34A5-4D9F-9349-C6E42CDC0E20","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b4e643631807865a8b17ad70d48d9aa01119cb6","datavalue":{"value":{"entity-type":"item","numeric-id":5753733,"id":"Q5753733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"600a0b13a5d4cb07b288b6ae862752b7fb093e65","datavalue":{"value":{"amount":"+0.9057446718215942","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":"Q1062616$186C44F4-8BD0-44E8-A854-58DAC95C3B01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"623105ab3233f1e95f4544c03c02e6d9c952160b","datavalue":{"value":{"entity-type":"item","numeric-id":1081529,"id":"Q1081529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c7a28c905462005614f4d9698854e066e82b171","datavalue":{"value":{"amount":"+0.7813789248466492","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":"Q1062616$1F14D3E2-3974-43BA-B55A-E0AA3C7DCE56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aab9b78b3732ea3b0bfd1530efcc4c8b0b71fe9b","datavalue":{"value":{"entity-type":"item","numeric-id":908839,"id":"Q908839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c362d7abe46870827378ffd2c205c35a92bf1212","datavalue":{"value":{"amount":"+0.7700573801994324","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":"Q1062616$A95054B4-2212-4EC2-9265-8D7354E7CE88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4151adc6694bb0614bffbfab88040cb07f60c86b","datavalue":{"value":{"entity-type":"item","numeric-id":3092238,"id":"Q3092238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d31251299a7702357cb59d1fa9f64471f658b59","datavalue":{"value":{"amount":"+0.7639185786247253","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":"Q1062616$A6D2F9D1-8E67-4FAB-915C-6328B02CB67E","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":"8092a6916dfac28de8030ed04cf9686f8d828b8e","datavalue":{"value":{"amount":"+0.7631883025169373","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":"Q1062616$FE3C454C-7DA1-48C7-98AA-F4EB4CD9B58B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The poset scheduling problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_poset_scheduling_problem"}}}}}