{"entities":{"Q1058969":{"pageid":1060817,"ns":120,"title":"Item:Q1058969","lastrevid":69533268,"modified":"2026-04-13T07:38:59Z","type":"item","id":"Q1058969","labels":{"en":{"language":"en","value":"On the complexity of preemptive open-shop scheduling problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3902376"}},"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":"Q1058969$38610FDA-1E93-44CA-9106-C849EB7F5CC3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b7dcba5f6e886d83cd4fd485b57f0704efefc1a6","datavalue":{"value":{"text":"On the complexity of preemptive open-shop scheduling problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1058969$21A9BB57-0C93-4D7C-970D-081516ED9EF6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f7ed2e877ddd6c72fcbadd0919809754137b2552","datavalue":{"value":"0565.90027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058969$9A89FF2A-91ED-4B87-9AA4-D0EF0236E7CC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d49cff6579ded7ee2be65dc07905aa20c0888ed7","datavalue":{"value":"10.1016/0167-6377(85)90035-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058969$FE223B65-6414-466D-B3CD-DFB1B2CC799F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1540f23842c475773327ccac0e0d18febebfe139","datavalue":{"value":{"entity-type":"item","numeric-id":580165,"id":"Q580165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058969$B3BC9E8C-38C3-4AA4-9AB5-2FE3080F3342","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a77f3e7f653a008ecd18602892eb1d08f55640f4","datavalue":{"value":{"entity-type":"item","numeric-id":840595,"id":"Q840595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058969$8B7AABED-7E8F-4EA4-8244-C9FF781A79EB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058969$CF8736D9-D1D5-4E23-A57F-CC5B3A249A4A","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":"Q1058969$E87E6B23-8542-4228-84B9-1C7EE8A0166B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"800fca78715725c3fcf6a00ac1035cacbb37913b","datavalue":{"value":"The problem of preemptively scheduling a set of n independent jobs on an m-machine open shop is studied, and two results are obtained. The first indicates that constructing optimal flow-time schedules is NP-hard for m larger than two. The second result shows that the problem remains NP-hard for the two-processor case when all jobs must be completed by their respective deadlines.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1058969$4AF7A709-C6DF-4B97-8846-6A27F7BC5E3C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058969$22697DFC-767E-4550-9B9E-8F98EEDEC634","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4b9ef5ff6b114f0634864ff7835b426ac3cbc929","datavalue":{"value":"3902376","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058969$AE54962B-1372-4EDD-B484-51668A7F2507","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"71b94e447449cc11506112fdb709d87d7bef7df5","datavalue":{"value":"preemptive open-shop scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1058969$96100F18-EF73-48A0-B240-19BA46B49367","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"71593a60ca7eac9c8339abb377a42bf55d20ac36","datavalue":{"value":"m-machine open shop","type":"string"},"datatype":"string"},"type":"statement","id":"Q1058969$7434D332-AA1E-4D24-B764-2A542C5B8CBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53abed182300a3d9055ff7bab5d55394e690fb9c","datavalue":{"value":"optimal flow-time schedules","type":"string"},"datatype":"string"},"type":"statement","id":"Q1058969$2AB2D1AB-5160-4D90-9F24-20543616C211","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q1058969$913D8778-F5CC-457B-8A58-B521CA800B55","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":"Q1058969$665B7439-2158-4558-99C7-68F09A21DBA2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bd2b5e0a3683fd4aa41aebe4780e7211e333c715","datavalue":{"value":"https://doi.org/10.1016/0167-6377(85)90035-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1058969$971C7FD2-FC0D-425D-8C98-59E85E3B63D4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1d6d2bfc259abc10592db56090b7f2b2a30b1464","datavalue":{"value":"W2063571792","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058969$CB37A15C-D923-49EE-9BDF-77C3BF17351E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bdb27d2bbe345b9cd8347ca62925f13d80b4745","datavalue":{"value":{"entity-type":"item","numeric-id":3954823,"id":"Q3954823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058969$24F6317F-E718-4852-801B-4C0D62558010","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bccc28aafe5c2e12dd3b39c69bb971c1534974d1","datavalue":{"value":{"entity-type":"item","numeric-id":3904361,"id":"Q3904361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058969$B98064B2-93F3-4FA7-B629-DACA200DA22E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4e94d57ac57cbb24f2c785dcb5e6a4c0d540d7c","datavalue":{"value":{"entity-type":"item","numeric-id":4744043,"id":"Q4744043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058969$0696B64C-9CE4-4657-A4E3-CBC08EE45074","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":"Q1058969$DCC81170-D88A-4BCF-8E3D-BDD65E05CBC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7ca7d44fdaea296612ecc619003afdf11898687","datavalue":{"value":{"entity-type":"item","numeric-id":3856092,"id":"Q3856092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058969$A78F4704-48E4-498A-838E-E8C9A221E55C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85b5d33facb76d24d8a6721d50795d6c3a0600ca","datavalue":{"value":{"entity-type":"item","numeric-id":3965898,"id":"Q3965898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058969$B57F5F64-8AFE-466A-9B20-F2270C080DBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dfbd785c98ffff9164411c97d0cfacab892ef9ed","datavalue":{"value":{"entity-type":"item","numeric-id":4111095,"id":"Q4111095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058969$387C3EDD-9D17-4EF5-B1D2-DF1D5FCEAC35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"206aac1fed08722358479159401448a8a87bf332","datavalue":{"value":{"entity-type":"item","numeric-id":4198327,"id":"Q4198327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058969$577F6195-E783-4C6A-9F80-F52DD3B217EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e6b5dc95be20abeaf6681ab1498d485ff0684a4","datavalue":{"value":{"entity-type":"item","numeric-id":3899811,"id":"Q3899811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058969$1EC57CBC-4279-4AA2-8597-D4EFA765AD1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7545c2c6e88c3944085675074d5ba9e07e0c5835","datavalue":{"value":{"entity-type":"item","numeric-id":3960459,"id":"Q3960459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058969$50ECF68C-9FBA-4A3E-8CDD-9FEB2DB0A4C6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37a82267fa281022e54940b34a9d5e54b9146664","datavalue":{"value":{"entity-type":"item","numeric-id":1333531,"id":"Q1333531"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56ff92c59a6aa9c59e2f3dca9633f5da279603f3","datavalue":{"value":{"amount":"+0.9304441213607788","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":"Q1058969$8BD2D2A2-E67F-4354-9ED6-7F465E5B9514","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15cd741d2b99ac860be7a536f34edfc66ca23bef","datavalue":{"value":{"entity-type":"item","numeric-id":1911243,"id":"Q1911243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f081b117b3dc2a475fe553d4db67417defdfb2d","datavalue":{"value":{"amount":"+0.9301491379737854","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":"Q1058969$F55F0D34-3B1D-4DF0-89B0-8A66B7E340CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3857fdf3fc6396b68dcbbb385aaeb0c38b6eb95e","datavalue":{"value":{"entity-type":"item","numeric-id":1280122,"id":"Q1280122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35f7b77b51dc10c99818cfc8be9d70e79fcf3603","datavalue":{"value":{"amount":"+0.8924434781074524","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":"Q1058969$1DC87D40-BFC4-445A-8153-BB5727D25A08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c75cbaa5aa1f621f395f7ab88e6700a92aaad46","datavalue":{"value":{"entity-type":"item","numeric-id":4033755,"id":"Q4033755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b33a5e884c39c026a1d28c120277a06f989b99d","datavalue":{"value":{"amount":"+0.880300760269165","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":"Q1058969$2F200B7B-BF2D-4557-804A-6B4E01A96AD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"298c551c05ba2fc3637f744a290d60b0858ab5e0","datavalue":{"value":{"entity-type":"item","numeric-id":902062,"id":"Q902062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b33a5e884c39c026a1d28c120277a06f989b99d","datavalue":{"value":{"amount":"+0.880300760269165","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":"Q1058969$42DDFE1A-6CBB-4BD0-A785-35C64A82D061","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of preemptive open-shop scheduling problems","badges":[]}}}}}