{"entities":{"Q1310020":{"pageid":1320770,"ns":120,"title":"Item:Q1310020","lastrevid":67132884,"modified":"2026-04-12T15:30:36Z","type":"item","id":"Q1310020","labels":{"en":{"language":"en","value":"An approximation algorithm for the \\(m\\)-machine permutation flow shop scheduling problem with controllable processing times"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 474848"}},"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":"Q1310020$11EF1211-05ED-4173-9076-BBF243711A57","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6b8d527be445e6c3c04e57a3cecde1e3c21956df","datavalue":{"value":{"text":"An approximation algorithm for the \\(m\\)-machine permutation flow shop scheduling problem with controllable processing times","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1310020$8D22D957-777D-460F-B799-253B36E6469A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"52996c25c913db450849c07e38b61fe1da0ff474","datavalue":{"value":"0796.90032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1310020$67A17CE5-A21F-4FD2-B96C-507D951880DC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"72f73cda4ea3c01a27c7a821dda58fe63af41c19","datavalue":{"value":"10.1016/0377-2217(93)90246-J","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1310020$A76F957B-E704-461E-9DB3-E065F2C7A9C1","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":"Q1310020$6E97AC6D-0DF5-4DDC-9CDE-27909EDFA10A","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":"Q1310020$94797C06-CCFA-4460-A3DD-05C9F24F1D66","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"92112234a474f78049341bfb55637019f67e54ac","datavalue":{"value":{"time":"+1993-12-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1310020$581CA9AF-2710-4DE6-949A-EC3ADA805B43","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"921169a1c7b9058ce57112c4a2bc46ed0b819905","datavalue":{"value":"The \\(m\\)-machine permutation flow shop scheduling problem in which job processing times are decision variables is considered. For every job \\(j\\) and every machine \\(i\\) there are given three non-negative numbers \\(a_{ij}\\), \\(u_{ij}\\) \\((u_{ij}\\leq a_{ij})\\) and \\(c_{ij}\\). The processing time of job \\(j\\) on machine \\(i\\) is equal to \\(a_{ij}- x_{ij}\\), where \\(0\\leq x_{ij}\\leq u_{ij}\\) is the decision variable. The aim is to find such \\(x_{ij}\\) \\((1\\leq j\\leq n,\\;1\\leq i\\leq m)\\) and a permutation \\(\\pi\\) (which defines the job processing order) that minimize the objective function \\(C_{\\max}(x,\\pi)+ \\sum^ m_{i=1} \\sum^ n_{j=1} c_{ij} x_{ij}\\). Here \\(C_{\\max}\\) is the maximum completion time (makespan).   This problem is known to be NP-hard even for \\(m=2\\) and identical \\(c_{ij}\\). An approximation algorithm with a worst-case performance ratio equal to 3/2 for \\(m=2\\) is known as well.   In the paper an approximation algorithm is suggested. The worst-case performance ratio of the algorithm is equal to 4/3 for \\(m=2\\) and does not exceed \\((\\rho+ \\sqrt{\\rho(m- 1)})/2+ 1/4+ O(1/\\sqrt{\\rho m})\\) for \\(m\\geq 2\\). Here \\(\\rho\\) is the worst-case performance ratio of an approximate algorithm, which is used for solving the usual (for some fixed \\(x\\)) \\(m\\)- machine permutation flow shop scheduling problem. The first bound is tight and the second bound is tight as well for \\(\\rho=1\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1310020$585B4A68-7B0C-4365-8ADF-CF6D80E6EC73","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b7ffcab9ce53e90c8627cb2c3bb400b94a5f354a","datavalue":{"value":"90B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1310020$EC1819C9-219A-4662-8FC4-AEE0E905AFED","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"90659ef531ceb460a4ffd9ca28e4c8cb32d028ad","datavalue":{"value":"474848","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1310020$4598EE98-9289-456C-A138-87589868D4A9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"14f5692e185b1488dd97e357834d4b024a1d4fa4","datavalue":{"value":"worst-case analysis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1310020$29B2EA77-355A-4C6B-8AA4-EDF415A06986","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf278915d4d4f21655cb6bd3337393847203f8a5","datavalue":{"value":"makespan","type":"string"},"datatype":"string"},"type":"statement","id":"Q1310020$BDAEE901-68FE-45CF-8628-600B83951D56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c0d5bc089afebb0c77ff553bd2df62175af7842","datavalue":{"value":"\\(m\\)-machine permutation flow shop scheduling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1310020$63F80686-FED7-45A1-996E-876BD289E6FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"edae7761f34acf97f2d43de39f62b25834213f9a","datavalue":{"value":"maximum completion time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1310020$76B2D083-BAA8-4568-8E1A-E3BDD40C4073","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c22d33e567cf57c1d49c02a5e07c657275af56c","datavalue":{"value":"worst-case performance ratio","type":"string"},"datatype":"string"},"type":"statement","id":"Q1310020$7D3CC6CF-8803-4AA1-A418-102C22E57AE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"405a4c12b3e0f2cec69c0a7e250d1805253fefb6","datavalue":{"value":"approximate algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1310020$B30E2143-100D-4BF1-A21F-E27FE34EDC84","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":"Q1310020$6F2A93DC-831B-450C-B3F9-92A5CAE57406","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":"Q1310020$9B4C80B0-61E8-4076-AACB-2C30F2ED98FC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"be9c21f68f3468254b8dfec9dffa58ab3c60673f","datavalue":{"value":{"entity-type":"item","numeric-id":1173857,"id":"Q1173857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310020$C5705899-5DF0-470C-B819-2FD057C07952","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98bcae446081e9f29447fc3d35c911dd1b90a71b","datavalue":{"value":{"entity-type":"item","numeric-id":5603740,"id":"Q5603740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310020$61C91B32-59B8-471E-B11E-B9A1C8F49DB1","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":"Q1310020$69FEC948-50DA-48EE-95FE-51FAD87B8053","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b635f06f6c39b03ca513d0a3eb06ec0cc20b065","datavalue":{"value":{"entity-type":"item","numeric-id":1820680,"id":"Q1820680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310020$ED8BB596-1725-4FD2-AE70-10E0C6B192B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24b7a640612f4d1f19b74e04e6d16f4f5ec68d08","datavalue":{"value":{"entity-type":"item","numeric-id":3659516,"id":"Q3659516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310020$215918B2-F1CE-43DA-80B6-666112AC4AE0","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":"Q1310020$9AE0C926-754E-41CC-80E5-E102513CDCD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f3ea8bcb92a4f37d2ed0c6b49c6c88ccfc8d17d","datavalue":{"value":{"entity-type":"item","numeric-id":3714887,"id":"Q3714887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310020$2A9A03EF-1611-4D08-815C-7E0AEBC45601","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":"Q1310020$2656F762-FB9C-4373-A6C8-28B0EAA6ED0B","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":"Q1310020$D01DC0BE-6CC3-4591-B311-321DC4816425","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7ac8e2c5ae9a5037a50820a004eee629907d451","datavalue":{"value":{"entity-type":"item","numeric-id":1104846,"id":"Q1104846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310020$1B710367-C29E-477E-A34E-1631CC2403EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58c3bade0d4bc97a824ab92d8c4969d7103a8948","datavalue":{"value":{"entity-type":"item","numeric-id":908846,"id":"Q908846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310020$83605EFB-0F5B-4F20-B1FC-6FD9CFDECC1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db222e9bf4cbaa68a3d72b37bc7280870a01a6cb","datavalue":{"value":{"entity-type":"item","numeric-id":1141078,"id":"Q1141078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310020$57CD4DF1-1ADF-4C1D-B7E0-E6867FCC18CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ebcfda593431551b368d734289a5defbed35198","datavalue":{"value":{"entity-type":"item","numeric-id":3138949,"id":"Q3138949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310020$57BD2E7A-8F93-488E-9125-5535802DE20F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32b93f988d8f2a266836f50fa98dad88e2a4fb01","datavalue":{"value":{"entity-type":"item","numeric-id":3896830,"id":"Q3896830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310020$E547D72E-5835-4D86-A4AE-34E13F5D8A16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43db55498f087131aba80db602336c37534874f6","datavalue":{"value":{"entity-type":"item","numeric-id":1162923,"id":"Q1162923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1310020$CD0D0F3F-7754-494A-A3EA-B1AE59DCA131","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"273095ab584857313f54e82f3276bed57440fcfd","datavalue":{"value":"https://doi.org/10.1016/0377-2217(93)90246-j","type":"string"},"datatype":"url"},"type":"statement","id":"Q1310020$EABAD192-0D6B-4609-B69B-A081E53E521A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7123e5c6f1e857c89e8e34539433d8de9b92e982","datavalue":{"value":"W2070979829","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1310020$4BE1AF1B-569E-41D8-8379-3B9FE75CBB47","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"715bf19800b18d431725d921e30d701dcf492e6a","datavalue":{"value":{"entity-type":"item","numeric-id":1104846,"id":"Q1104846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97b27f31b33f4fc4598dbc780ebd9723e10f9eca","datavalue":{"value":{"amount":"+0.8668834567070007","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":"Q1310020$317A4A31-7F2A-4CF4-AD6C-4B5A302ABF72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e08aeca7cb49f1fbbaa8aa649038d9211f4d9023","datavalue":{"value":{"entity-type":"item","numeric-id":596465,"id":"Q596465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b7e6fb981d60724547cac351787fb8cd20ee0ddd","datavalue":{"value":{"amount":"+0.8628576397895813","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":"Q1310020$7D03F540-91C3-47DB-8E9D-975B951B0A5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d61e6ab4b26776591b36b77d3e455ff726ecd4bf","datavalue":{"value":{"entity-type":"item","numeric-id":3475121,"id":"Q3475121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"852ee518ffa1ef99a46d49d309fa2419b86d7cf9","datavalue":{"value":{"amount":"+0.848858654499054","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":"Q1310020$B600FB9C-9543-42E5-9C6B-13B745C27EDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1be93b6cb3ea18a96dce8f3e21508b660c60880e","datavalue":{"value":{"entity-type":"item","numeric-id":5895000,"id":"Q5895000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9fab092ac0cd35c8be20df8b46fc7d72a311ab5b","datavalue":{"value":{"amount":"+0.8430265188217163","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":"Q1310020$E1B00398-4555-4A33-BC6B-C9E6F0C3F587","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"934b4321427ca73ef09c8967ddcaaa3bb9d892c1","datavalue":{"value":{"entity-type":"item","numeric-id":3815119,"id":"Q3815119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6dd46a9098689cfdf1b8ab43d9441fbd27e3d393","datavalue":{"value":{"amount":"+0.8419191241264343","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":"Q1310020$595425ED-F1C7-4317-B3AE-4DDCC961C543","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An approximation algorithm for the \\(m\\)-machine permutation flow shop scheduling problem with controllable processing times","badges":[]}}}}}