{"entities":{"Q2366083":{"pageid":2376826,"ns":120,"title":"Item:Q2366083","lastrevid":72613509,"modified":"2026-04-14T06:04:57Z","type":"item","id":"Q2366083","labels":{"en":{"language":"en","value":"The two-machine flow shop problem with arbitrary precedence relations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 223237"}},"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":"Q2366083$22B86031-BF93-4104-931A-5BF1B426D82B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ee6aebd94c23a6494b15ecd261be80476771140d","datavalue":{"value":{"text":"The two-machine flow shop problem with arbitrary precedence relations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2366083$367D5126-5B3F-49CE-81F2-EB70D8F4523F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f4cadc6c2cbf334c989a93b60050cf26a6a8cb8f","datavalue":{"value":"0778.90029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366083$5F64FB5D-2CEE-47C9-85D7-CC8D965141C7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7261e49ebc46bcdc584a29010a9c88f43433133b","datavalue":{"value":"10.1016/0377-2217(93)90180-U","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366083$26C484B0-8A29-40A1-BEC4-0B489947F81E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3d31c680c5ae45d1d6bce705654e3fb8a7a6abc4","datavalue":{"value":{"entity-type":"item","numeric-id":1342005,"id":"Q1342005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366083$AC53770E-54E1-43D6-9EDA-B662EC008135","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ad5be5e828c023ee6464866a069988768852563c","datavalue":{"value":{"entity-type":"item","numeric-id":1342004,"id":"Q1342004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366083$E3536110-8162-415C-8F27-78B397F1E531","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38576f39a6df37711cb397d1408ced7e3814cc6e","datavalue":{"value":{"entity-type":"item","numeric-id":62319,"id":"Q62319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366083$8235AC1C-6ADF-47FE-9A5E-A2E4B0C9FF3D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be4381b75afe2df0dbe37cd1a66e006418c0c5aa","datavalue":{"value":{"time":"+1993-06-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2366083$482F0F0C-A94C-4C5A-9665-353C3DCCF70C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"03e538b4538d741c09a72126cb41525ea748a053","datavalue":{"value":"The 2-machine flow shop scheduling problem with arbitrary precedence constraints is considered. The objective is to minimize the makespan. The problem is known to be NP-hard in the strong sense. A branch-and-bound algorithm is proposed for the solution. Lower bounds are computed by solving relaxed problems in which precedence constraints are reduced to a series-parallel form. The problem with series-parallel precedence constraints is \\(O(n \\log n)\\) solvable. Here \\(n\\) is the number of jobs to be processed. Results of computational experiments with up to 100 jobs are included.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366083$176E4069-94F2-4BE7-90B2-41D4E252D7E7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366083$FC089239-318A-4420-BB0C-92A8C1E59C9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366083$F39CB4B4-8892-4FDB-982A-8956DDEC8667","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"aaec2c1e751b3bf62a47c24d35955b9d4b18d710","datavalue":{"value":"223237","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366083$1F2CB308-2F82-4523-A899-A29DF10EE0FC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366083$DB415C78-8534-4AA4-B64F-B224B36F8545","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"75e95772a33e216abfbc8c10ccbad980e6c36e28","datavalue":{"value":"2-machine flow shop scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366083$5EBDF7DF-3B6B-4A21-B00B-B3A2C6050796","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fbe4779b21482c6f7af163070358f952601735bf","datavalue":{"value":"precedence constraints","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366083$3EE68593-A7CC-4C63-A608-A90760B6A4D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf278915d4d4f21655cb6bd3337393847203f8a5","datavalue":{"value":"makespan","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366083$C22C51FC-F021-4E25-8575-8FB971D5D724","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"32b70193b15cfa9820eaa83513ddb2267d9b694a","datavalue":{"value":"branch-and-bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366083$85FCF087-4638-4F65-9E84-04F349DEDD21","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c54e16c51cf038e39d211f26a20642444a0ea747","datavalue":{"value":{"entity-type":"item","numeric-id":612204,"id":"Q612204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366083$C2EA2B66-DEB9-47FD-83C6-6D09852298C8","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":"Q2366083$3D49370C-73EC-4A4E-ADB9-3794FFC69D58","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"de15692978df304ce0a7e574f0163370d27fb247","datavalue":{"value":{"entity-type":"item","numeric-id":800822,"id":"Q800822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366083$532E19C9-595D-4DB7-B320-BCAC417E6358","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f36232ae77f8c7dd3d32ca83e7370d4ed2a13cc7","datavalue":{"value":{"entity-type":"item","numeric-id":2834736,"id":"Q2834736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366083$236C24FB-0303-465A-939F-9334FCAF8669","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a54363cab19ddaa83ba50c46c8127b159b14d03","datavalue":{"value":{"entity-type":"item","numeric-id":4055377,"id":"Q4055377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366083$6EBDB107-B0CA-488F-97DB-8AFE3B7260D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f0db30bd6d1509029edc253c29203f579e07529","datavalue":{"value":{"entity-type":"item","numeric-id":5563220,"id":"Q5563220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366083$01696C06-B82A-4829-AC09-826149435D63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a2063a1706fa4b383645c3deb5d8386a0bbb475","datavalue":{"value":{"entity-type":"item","numeric-id":3853421,"id":"Q3853421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366083$DFFFDC82-A5E2-420F-B3DF-7BAAB5CDD09F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f89d8d74de150f9f05c3739806ed2a833b9fc3ec","datavalue":{"value":{"entity-type":"item","numeric-id":1142151,"id":"Q1142151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366083$840FC189-3ECE-457E-B9F8-8B94F3B0613E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eddecf9b06ea7288ca58a7666320441adbe28f47","datavalue":{"value":{"entity-type":"item","numeric-id":3879034,"id":"Q3879034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366083$CA8AC8CB-387D-4C34-BCBF-34B6CDFB8314","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79a7b61152ae684a0f06860ba4795f96dd7b5cf9","datavalue":{"value":{"entity-type":"item","numeric-id":3863680,"id":"Q3863680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366083$D0D0E459-482E-4086-8010-4A8588AADF01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4fcfe987d8cbbd43f7b7238b024d7a85de33a069","datavalue":{"value":{"entity-type":"item","numeric-id":3936212,"id":"Q3936212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366083$71E2FC9A-889E-416C-8659-56AF8151D448","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da70704b977996be2da3461190968c592e893c92","datavalue":{"value":{"entity-type":"item","numeric-id":1342006,"id":"Q1342006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71f14c2545bd94ce6f6241a39e0d600a991df272","datavalue":{"value":{"amount":"+0.9062767028808594","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":"Q2366083$6CC0904B-562A-4181-B7F9-26C04AC2DDE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c75d0c656bb76a389a0035b2431aa820d95281e","datavalue":{"value":{"entity-type":"item","numeric-id":800822,"id":"Q800822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6fed683e11ce8d54a525f3f661cc41a326144cf4","datavalue":{"value":{"amount":"+0.8973891139030457","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":"Q2366083$343FFC50-4ECE-4303-B4A2-E130BA3EFDEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec6cab21da0df45871fa4af4c549ff8ffffcd2c7","datavalue":{"value":{"entity-type":"item","numeric-id":1768595,"id":"Q1768595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d44b71852ebeb0b00648f81c6140acbb808de26b","datavalue":{"value":{"amount":"+0.8651897311210632","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":"Q2366083$2D2149EA-5FA6-4FDF-A6CC-BEF31698B343","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd3ebac91e9525671181f20e05c02ac03bd19d2b","datavalue":{"value":{"entity-type":"item","numeric-id":4233218,"id":"Q4233218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1698d96e5e4cb651b4ec7854bfc7b2590f0a867","datavalue":{"value":{"amount":"+0.8521237969398499","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":"Q2366083$1BD2B9E6-6E3F-42C0-B122-D70DD6B7A444","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The two-machine flow shop problem with arbitrary precedence relations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_two-machine_flow_shop_problem_with_arbitrary_precedence_relations"}}}}}