{"entities":{"Q580167":{"pageid":581934,"ns":120,"title":"Item:Q580167","lastrevid":62985366,"modified":"2026-04-11T09:29:54Z","type":"item","id":"Q580167","labels":{"en":{"language":"en","value":"Scheduling ordered open shops"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4016583"}},"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":"Q580167$D2EA8E17-C6F0-4414-94C0-2F8D5F08A83C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3f9fb94462a6d41aeb51511ae6ade4916c1f5b4d","datavalue":{"value":{"text":"Scheduling ordered open shops","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q580167$97F80D2E-29B7-4292-87FF-A8CC5EA63747","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"55a15cf13a2e4d6a9d69f10fcbbccd57443c329b","datavalue":{"value":"0625.90045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580167$116DA28D-BAA7-4A41-A477-5726935A045F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8174323f138432b448c7a3cd896d987375a48c02","datavalue":{"value":"10.1016/0305-0548(87)90029-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580167$F2B113E5-6550-4CCF-93E6-2B8052110C95","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":"Q580167$86E205D7-85DE-474A-B953-39D2237BF666","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":"Q580167$4C5F8A9B-CF40-4D59-B566-A774DFB8EF72","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e630590c5ca6e787c3c7b5e291898405495fea2b","datavalue":{"value":{"entity-type":"item","numeric-id":162215,"id":"Q162215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580167$0D9F749B-6217-4D97-BF9B-93E806DA64C6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q580167$E361AE30-6EA5-4C30-9357-CCEA5859B19F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6e18fe1f2ac6d24b0f278d72f83537ea3adfa082","datavalue":{"value":"This paper examines special cases of the open shop problem in an attempt to define the boundary between easy and apparently hard, i.e. NP- complete, problems. The top result is: the minimizing makespan in an ordered three-machine open shop is NP-complete. This implies that many other open shop problems are also NP-complete.    However, the authors show that a slight change in the assumptions of the problem may render a difficult problem easy to solve.","type":"string"},"datatype":"string"},"type":"statement","id":"Q580167$FA0A2038-BBD6-4A18-8954-F6143C8FDF46","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9224c061da78670cd51103388d6e8594567f03bd","datavalue":{"value":{"entity-type":"item","numeric-id":593488,"id":"Q593488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580167$DEEA38B6-73AF-4072-B28F-A7077EF31164","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580167$B1818603-F89A-4B95-A830-E430E9B55C30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580167$5F91CE13-E57D-4DB2-A0FB-E6C7201C10E9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6dc3296e77acfa554294a7bfec81295b1da8c7d5","datavalue":{"value":"4016583","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580167$4460F7E3-4BA0-48CB-9D10-4CC9B1B40281","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8e79c8555910f889c3deb80b1df3833d12429002","datavalue":{"value":"open shop","type":"string"},"datatype":"string"},"type":"statement","id":"Q580167$8ED3C9E1-9355-4F91-BAF3-9D92E4CAD845","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf278915d4d4f21655cb6bd3337393847203f8a5","datavalue":{"value":"makespan","type":"string"},"datatype":"string"},"type":"statement","id":"Q580167$51FB21FD-81ED-4267-B6DC-C3C3FF018D96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q580167$9640F148-72A7-4E46-B7F2-70B3BCF5E0FA","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":"Q580167$39E4EAC1-BD17-46D9-874F-B0C4D61DD7E6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"19dcd130b1b4a64686f90aa0a6c4d4865befd417","datavalue":{"value":"https://doi.org/10.1016/0305-0548(87)90029-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q580167$68DF6BB2-232E-4576-854A-34655C8C579F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c3acd5235f2a04ca9480fbf346c46f0cab12f8a7","datavalue":{"value":"W2040889502","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580167$D91FC6D4-624B-44EC-B47D-F9A591C4220D","rank":"normal"}],"P223":[{"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":"Q580167$47CB9DA4-859D-4729-8173-9885636FAC6A","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":"Q580167$653B00F6-7D29-40BD-9165-6AE20C82F783","rank":"normal"},{"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":"Q580167$BE147B7C-5BD7-4D91-9D84-C483815D4555","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b59cf977c61829bb6eb4a7c9fd42665431f60c9d","datavalue":{"value":{"entity-type":"item","numeric-id":3832309,"id":"Q3832309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580167$338B0B7F-679C-4087-AB78-254A4A6E7364","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"721c20a49adb581290141f70d4b2f58ee7f08475","datavalue":{"value":{"entity-type":"item","numeric-id":1086145,"id":"Q1086145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580167$CFCFA9B7-BB36-48D8-83F8-EDC98920E7EF","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":"Q580167$968665EC-62CF-4A92-879C-212D0C2A93F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f4b214663d0400d84688d3f0c44f1d78987eb5e","datavalue":{"value":{"entity-type":"item","numeric-id":3798473,"id":"Q3798473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580167$14432D88-89CC-472C-9D18-10B6F79FC1F7","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":"Q580167$43AA611C-A68E-4AE2-B783-D021B70344F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d2e1adb4c72a669dbbfe0c28dfcc92166deac63f","datavalue":{"value":{"entity-type":"item","numeric-id":1058969,"id":"Q1058969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580167$1D27CADA-C7A7-44F3-A809-F73E086A7106","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":"Q580167$03D14A74-E4F5-49C6-B560-4A423627EA1B","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":"Q580167$F7BC6848-657D-44B3-871C-D0F2AB078157","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":"Q580167$FABBEB04-521D-41B0-BB33-08B7BC250451","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0b86da6901907b4b60c4d755cbdefb3d87af7f5","datavalue":{"value":{"entity-type":"item","numeric-id":761967,"id":"Q761967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580167$A54038CD-ACF3-44C6-8194-D7BDE5F37CC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5800d93eb4f8caa03263f0b51c3001208ff1e9ad","datavalue":{"value":{"entity-type":"item","numeric-id":3050157,"id":"Q3050157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580167$969C9BA4-1638-4EE7-B04A-09E4A582C58B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46652be8250d197f79acc8f9e9e81219736d5ad5","datavalue":{"value":{"entity-type":"item","numeric-id":3329200,"id":"Q3329200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5985057319904c2affbcc006d1d812ca51cb7c64","datavalue":{"value":{"amount":"+0.8497357964515686","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":"Q580167$EAEE5E75-01B9-47FE-AC9D-BB840870A7ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f1a3aa217dc98100d4d74d6f91031e94c723023","datavalue":{"value":{"entity-type":"item","numeric-id":3304098,"id":"Q3304098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30235a54ebe3419f344d82d54890ca946d41fbc8","datavalue":{"value":{"amount":"+0.8455893993377686","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":"Q580167$E365539A-C442-4B60-B77D-5DA2902C6E68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c46019ddd67bd2c611b59503be9d15a301c79f1","datavalue":{"value":{"entity-type":"item","numeric-id":3142313,"id":"Q3142313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9381799ee99cf97d4edb2baf3f36a9bff33c4871","datavalue":{"value":{"amount":"+0.8354750871658325","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":"Q580167$986B9D2A-65C1-4075-9412-71EC21018DE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c580a71f73ba835202a03612d7483e5ede7f2a53","datavalue":{"value":{"entity-type":"item","numeric-id":1363753,"id":"Q1363753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c84a303b4aa787869dbab2b82a80cfd99bd3b8ad","datavalue":{"value":{"amount":"+0.834557294845581","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":"Q580167$E99B6090-418D-4401-9DB9-7480CE754446","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"edc6f92f7530a58d77fce9b2457728da0d88d3ac","datavalue":{"value":{"entity-type":"item","numeric-id":1086145,"id":"Q1086145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15fb2b59828f2b941d49fdd1c6ba3bd5b03941b5","datavalue":{"value":{"amount":"+0.8336902856826782","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":"Q580167$EC8CA80F-B292-40C9-AD1C-D3B89FCC68A9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Scheduling ordered open shops","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Scheduling_ordered_open_shops"}}}}}