{"entities":{"Q4033755":{"pageid":6063487,"ns":120,"title":"Item:Q4033755","lastrevid":108762575,"modified":"2026-11-10T04:48:08Z","type":"item","id":"Q4033755","labels":{"en":{"language":"en","value":"Minimizing Mean Flow Time in Two-Machine Open Shops and Flow Shops"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 166199"}},"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":"Q4033755$8E19563A-6942-4485-A22C-15045E880E34","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"274b636c13690a6814b6da60c2af34ada709b603","datavalue":{"value":{"text":"Minimizing Mean Flow Time in Two-Machine Open Shops and Flow Shops","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4033755$083F68C7-C876-4579-84C1-EFF26A8A8C4B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c6c3ee33c280a365982a1bd7f450f4fad1914076","datavalue":{"value":"0768.90039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4033755$10D06881-B3D6-4F5C-90BE-4BAA7BE67070","rank":"normal"}],"P16":[{"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":"Q4033755$6632AF13-ED8A-4DD7-83C1-EB7F1DB265D7","rank":"normal"},{"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":"Q4033755$92A11D2B-4661-4A0B-B013-6AB6275BE413","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"9bcfebe9d23b7752651008b0d843e08ec7c57a37","datavalue":{"value":{"entity-type":"item","numeric-id":2709787,"id":"Q2709787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4033755$8B29B675-A75C-4C32-AA16-77D0D382F380","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1772b6c81a5108c06854e0de4518fb90e5a6ebdc","datavalue":{"value":{"time":"+1993-05-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4033755$5BF3B15A-5B9A-4244-B9DD-B21EC0412EE1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4033755$6DFC9B14-F194-4664-9949-E5FF7EFE6355","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4033755$3EE8575A-204D-47CA-B84F-4763714E72A1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e823f995f061ff0741f3451b6baacde2b8a5b5cf","datavalue":{"value":"166199","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4033755$0DA11F4F-CAC8-4BC6-9347-33AB06065974","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4d2f95da562abdf7889e5b63c1db083c008ba51d","datavalue":{"value":"fixed completion time","type":"string"},"datatype":"string"},"type":"statement","id":"Q4033755$6F3B8658-DEDF-473F-8470-FF4A83DEF92B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8e79c8555910f889c3deb80b1df3833d12429002","datavalue":{"value":"open shop","type":"string"},"datatype":"string"},"type":"statement","id":"Q4033755$E9CF386A-475C-4C1E-A17A-04F8F5D84D0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7fbe9dcddbcc2afcb2f5b387c1303e0b82281922","datavalue":{"value":"flow shop","type":"string"},"datatype":"string"},"type":"statement","id":"Q4033755$71AD7DBB-0ABC-47E2-B705-DAD6037CBB86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"98700b8811663b8f1a98d7c04bf46456cd1a409a","datavalue":{"value":"mean job completion time","type":"string"},"datatype":"string"},"type":"statement","id":"Q4033755$DD519985-E225-4DD1-88C7-517B862E0BAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"809522ba2164240b10ff9fa43e8edde29cd07ae6","datavalue":{"value":"job preemption","type":"string"},"datatype":"string"},"type":"statement","id":"Q4033755$A4E1D4EE-55FF-4815-BE6C-EAA55609A401","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3b6d19d4c43b54c850c0e7b873f523866d352b6c","datavalue":{"value":"polynomial algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q4033755$41EB781F-DE28-4B87-9BDD-FDF60AB33B66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c7d5e4886aa4290eca104cd0d1da319d8b4d34c4","datavalue":{"value":"NP-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q4033755$F5F37F16-2581-4D44-B5EE-B97D5DF32743","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":"Q4033755$C148D281-4598-4603-8A19-0E0F35609320","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"85d1e79be09f99898fe61ef8a8e7b6602187a553","datavalue":{"value":"https://doi.org/10.1006/jagm.1993.1002","type":"string"},"datatype":"url"},"type":"statement","id":"Q4033755$D2E4AC8F-E4EC-4A98-96F8-1E3534193E03","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6139f8e27522ca9eccbc2c33b066bff79425f4d6","datavalue":{"value":"W1983676174","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4033755$9C14A39C-8B53-4F43-BDD4-3E6404A3A1AF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e444e701552d959d1526f6870448df543aa8c091","datavalue":{"value":"10.1006/JAGM.1993.1002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4033755$1DCCCA36-8984-49A3-B20B-7502C07AF0A8","rank":"normal"}],"P1643":[{"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":"8600679e540b10d7a6d7b34ba31752784dfaddf5","datavalue":{"value":{"amount":"+0.8932902216911316","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":"Q4033755$CA4F7E87-2957-4401-A427-2C7C68B83C5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"59e3af9aeed41237538dad61dc9f82a99c1de43e","datavalue":{"value":{"entity-type":"item","numeric-id":1058969,"id":"Q1058969"},"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":"Q4033755$2D1AC41D-312F-4741-A7E4-40619B0D919E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3af6eb84f78802cd2aab58ae606cb75d26023265","datavalue":{"value":{"entity-type":"item","numeric-id":1178530,"id":"Q1178530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71cb080f4a913fdf8c7f4cfe74a945be300264ce","datavalue":{"value":{"amount":"+0.8701305389404297","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":"Q4033755$31C4DBC8-A427-4F2D-A31A-2C3163C423EF","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":"4a08c927f510895f8c37eac2de4d20e557fe1cea","datavalue":{"value":{"amount":"+0.8674870729446411","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":"Q4033755$9687048E-DC66-4BF9-A486-5A51F506C493","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2c047011a832c9ffb964c6c463a7ede06b8f306","datavalue":{"value":{"entity-type":"item","numeric-id":4924332,"id":"Q4924332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94928bb92e3c1d32cbc2c88f802503f432bc5619","datavalue":{"value":{"amount":"+0.8667904734611511","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":"Q4033755$E065579C-7FCA-4E22-AADB-DA319A8D688C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1ead111933821a73e447edfd345286c7dba4d32f","datavalue":{"value":"The authors analyse two machine open shop and flow shop scheduling problems. The objective is to minimize the mean job completion time and job preemption is possible. Whereas these two problems on three machines are known to be NP-hard in the strong sense, the complexity status of the two machine problems has been unsolved. In this article, the authors prove that the two machine open shop problem is NP-hard in the ordinary sense and the flow shop problem is NP-hard in the strong sense. Moreover, for a fixed sequence of job completion times, polynomial algorithms are developed to compute the associated optimal schedule. The complexities of these two algorithms are \\(O(n)\\) for the open shop and \\(O(n\\cdot\\log n)\\) for the flow shop problem, respectively; here \\(n\\) denotes the number of jobs. It is interesting that the NP-hardness proof for the two machine flow shop problem provides an alternative proof for the NP-hardness (in the strong sense) of the associated non-preemptive problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q4033755$D25FEA89-1C23-440C-A95C-A4261031C17D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Minimizing Mean Flow Time in Two-Machine Open Shops and Flow Shops","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Minimizing_Mean_Flow_Time_in_Two-Machine_Open_Shops_and_Flow_Shops"}}}}}