{"entities":{"Q1183390":{"pageid":1194139,"ns":120,"title":"Item:Q1183390","lastrevid":66442590,"modified":"2026-04-12T10:06:14Z","type":"item","id":"Q1183390","labels":{"en":{"language":"en","value":"Worst-case analysis of Dannenbring's algorithm for flow-shop scheduling"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 33256"}},"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":"Q1183390$1E306299-1B0F-4D60-B10B-5EEA027CE758","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9c4618cd9df3b39ce7411248514d806b5ab69a68","datavalue":{"value":{"text":"Worst-case analysis of Dannenbring's algorithm for flow-shop scheduling","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1183390$096F8582-9C7E-4E05-8A14-A2C63E23801F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"17a14a5f2a7f110233b802be5eab841c86b0a8b3","datavalue":{"value":"0772.90054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183390$FB53D7DE-44D0-4449-95ED-A6A89CA7DB5C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1e1c83987bfbac8ee9e2c87b825a98211bf688b6","datavalue":{"value":"10.1016/0167-6377(91)90025-K","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183390$E4F37255-362E-4594-B810-22CA64571041","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7542e378203ce39231c5f7b719109e246636e043","datavalue":{"value":{"entity-type":"item","numeric-id":689948,"id":"Q689948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183390$EED4E90A-A9A9-4B69-A6C0-29EDE93CDC20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cbc6b16593cc80ffaae9c0a72f393b5b82a848d7","datavalue":{"value":{"entity-type":"item","numeric-id":689949,"id":"Q689949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183390$20190652-3005-4657-832F-55538C87FCE5","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":"Q1183390$F0C83968-0469-4383-98F3-031303255621","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1183390$18D96180-30D9-4012-8519-BB6A8B902619","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5a4cb156fe5f2f127d38937580944c4e1856bb0c","datavalue":{"value":"The permutation flow-shop scheduling problem is considered. As the problem is NP-hard, several heuristic algorithms for solving it have been already given in the literature. Here, a worst case analysis of one of these algorithms proposed by \\textit{D. G. Dannenbring} [Manage. Sci. 23, 1174-1182 (1977; Zbl 0371.90063)] is analyzed and the ratio of \\(m/\\sqrt 2\\) is given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183390$F1794E08-B4CA-401C-BCFA-3CD97D261831","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183390$CB76F310-75A7-42D9-A348-783CB850339B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a5eb613588d5101c3d15c92779cc5d702cb2c54b","datavalue":{"value":"33256","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183390$514AD1E5-E726-4173-85D1-F60BA61EB34A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"55011b3837104f4cf10381e7929350c1927678f9","datavalue":{"value":"Dannenbring's algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183390$28497C63-9816-495B-87FE-EA8322136B5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"89c55a85406058b71369f8498340741c6123067c","datavalue":{"value":"rapid access algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183390$656E0D62-2435-4FDE-B82C-682A75E24802","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183390$90D46E61-E59A-4565-AA14-AC0651CC1E5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f5b627973bc2dd565f33633c38c3c493fcecc5c6","datavalue":{"value":"permutation flow-shop scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183390$CF2B5ACC-C04E-4580-9052-C2AC1AC4637C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183390$1E375DEC-DBE0-4E5F-A45F-547466630F69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b6fb9ac68bddbfa8d11616ed9b4850fa8757e1bd","datavalue":{"value":"heuristic algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183390$B73A6DAA-6A8A-40C1-84CC-6A0A8CB5FB51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e2c617fa26fce196a02401296ade49036a02b19e","datavalue":{"value":"worst case analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183390$178AAE34-0954-49DA-ADC7-95CBD641FD60","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"208fd2cac25388eac9d979aba68dad257ddb3873","datavalue":{"value":{"entity-type":"item","numeric-id":224835,"id":"Q224835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183390$3A44DF7C-FDBE-4E89-AFC9-9CF0198662A8","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":"Q1183390$CD77E77E-1778-4E12-885A-B0C40E59F2B0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"52d3d659b94b7fa8b0dc770a7af41c8447fdd88b","datavalue":{"value":{"entity-type":"item","numeric-id":5590535,"id":"Q5590535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183390$D4F7252A-9F64-477A-B3E5-8B3D68CDE8CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c1564a1969e13b33a9f3e0637ce69a64bd9f6a3","datavalue":{"value":{"entity-type":"item","numeric-id":4147827,"id":"Q4147827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183390$8308728B-2101-4366-A9E3-C5F118516400","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd736dc8c5cd6333c480e672517148932baf7d2f","datavalue":{"value":{"entity-type":"item","numeric-id":1121778,"id":"Q1121778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183390$946C50DD-61EF-4706-B65C-23F861571E16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9a2e96ab140f4274cff13d3447c2ee4c0cb8662","datavalue":{"value":{"entity-type":"item","numeric-id":1342050,"id":"Q1342050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183390$8AC44847-D34F-4E26-8836-6B850820A1F6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b1c4459b6e64478c6445f9c4b0ee3fe28fed5a53","datavalue":{"value":"https://doi.org/10.1016/0167-6377(91)90025-k","type":"string"},"datatype":"url"},"type":"statement","id":"Q1183390$2D116E52-9BD6-47AC-B9CE-62C2F8DD5C57","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6391b9d777f385d30902f6686134bcb41cb25a88","datavalue":{"value":"W1979770131","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183390$29093BC4-E09B-4A04-8FE2-82E3196A1EEB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85ef49939d026d312952694f7d12243aa904d4e6","datavalue":{"value":{"entity-type":"item","numeric-id":1121778,"id":"Q1121778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85178ddccecac98a77b389ad8a1fe2b14708e0dc","datavalue":{"value":{"amount":"+0.8827178478240967","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":"Q1183390$32F3ACBA-E3B6-4AD3-AF13-981ACE6E31C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d41b42f884cf294ea3b307f7f6ee498a17f8772","datavalue":{"value":{"entity-type":"item","numeric-id":1330557,"id":"Q1330557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c16e5272f19e7278540609ad0d462141186c1ea","datavalue":{"value":{"amount":"+0.8671860098838806","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":"Q1183390$4E845C01-E5A6-424F-A2CA-6DF404C6B196","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"987f7e816b93c128e78e100395b650ac212d0321","datavalue":{"value":{"entity-type":"item","numeric-id":1296692,"id":"Q1296692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6001f40438f9a614372208ed6b3bba9a3be3b309","datavalue":{"value":{"amount":"+0.8656712770462036","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":"Q1183390$0E36139E-B06C-4B2C-A67D-29DD6FFCE4A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0199753574e4a5cfee1abd8b515aa428a542561c","datavalue":{"value":{"entity-type":"item","numeric-id":5689787,"id":"Q5689787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61057243a0c9f17142b6c6adbf023c6efe8b48da","datavalue":{"value":{"amount":"+0.8177223205566406","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":"Q1183390$E40B32E9-6255-4235-A114-8B912319ED51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d5c1ef7f14316bbc1d332125d30f114afb084e4","datavalue":{"value":{"entity-type":"item","numeric-id":583096,"id":"Q583096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d3e2470f5934091fe3490ee77a17bc0102b6f608","datavalue":{"value":{"amount":"+0.8094393014907837","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":"Q1183390$959E5B75-C6AD-4BEE-BFB9-4471802ECAD8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Worst-case analysis of Dannenbring's algorithm for flow-shop scheduling","badges":[]}}}}}