{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T01:45:35Z","timestamp":1773193535948,"version":"3.50.1"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2011,10,1]],"date-time":"2011-10-01T00:00:00Z","timestamp":1317427200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003475","name":"Hasler Stiftung","doi-asserted-by":"publisher","award":["11099"],"award-info":[{"award-number":["11099"]}],"id":[{"id":"10.13039\/501100003475","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["2.26E+11"],"award-info":[{"award-number":["2.26E+11"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"publisher","award":["200020-122110\/1"],"award-info":[{"award-number":["200020-122110\/1"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2011,10]]},"abstract":"<jats:p>We consider several variants of the job shop problem that is a fundamental and classical problem in scheduling. The currently best approximation algorithms have worse than logarithmic performance guarantee, but the only previously known inapproximability result says that it is NP-hard to approximate job shops within a factor less than 5\/4. Closing this big approximability gap is a well-known and long-standing open problem.<\/jats:p>\n          <jats:p>This article closes many gaps in our understanding of the hardness of this problem and answers several open questions in the literature. It is shown the first nonconstant inapproximability result that almost matches the best-known approximation algorithm for acyclic job shops. The same bounds hold for the general version of flow shops, where jobs are not required to be processed on each machine. Similar inapproximability results are obtained when the objective is to minimize the sum of completion times. It is also shown that the problem with two machines and the preemptive variant with three machines have no PTAS.<\/jats:p>","DOI":"10.1145\/2027216.2027218","type":"journal-article","created":{"date-parts":[[2011,10,27]],"date-time":"2011-10-27T13:17:37Z","timestamp":1319721457000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["Hardness of Approximating Flow and Job Shop Scheduling Problems"],"prefix":"10.1145","volume":"58","author":[{"given":"Monaldo","family":"Mastrolilli","sequence":"first","affiliation":[{"name":"IDSIA, Lugano, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ola","family":"Svensson","sequence":"additional","affiliation":[{"name":"EPFL, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00158-3"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s006070170017"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1060.0189"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020402"},{"key":"e_1_2_1_5_1","first-page":"21","article-title":"A review of machine scheduling: Complexity, algorithms and approximability","volume":"3","author":"Chen B.","year":"1998","unstructured":"Chen , B. , Potts , C. N. , and Woeginger , G. J. 1998 . A review of machine scheduling: Complexity, algorithms and approximability . Hand. Combin. Optimiz. 3 , 21 -- 169 . Chen, B., Potts, C. N., and Woeginger, G. J. 1998. A review of machine scheduling: Complexity, algorithms and approximability. Hand. Combin. Optimiz. 3, 21--169.","journal-title":"Hand. Combin. Optimiz."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335310"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930200018"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24587-2_34"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9086-6"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199326104"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.13.2.157.10520"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199363908"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875607"},{"key":"e_1_2_1_15_1","first-page":"445","article-title":"Sequencing and scheduling: Algorithms and complexity","volume":"4","author":"Lawler E. L.","year":"1993","unstructured":"Lawler , E. L. , Lenstra , J. , Kan , A. R. , and Shmoys , D. 1993 . Sequencing and scheduling: Algorithms and complexity . Handb. Oper. Res. Manage. Sci. 4 , 445 -- 522 . Lawler, E. L., Lenstra, J., Kan, A. R., and Shmoys, D. 1993. Sequencing and scheduling: Algorithms and complexity. Handb. Oper. Res. Manage. Sci. 4, 445--522.","journal-title":"Handb. Oper. Res. Manage. Sci."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215349"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050061"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 13th Conference on Integer Programming and Combinatorial Optimization (IPCO). 154--168","author":"Nagarajan V.","unstructured":"Nagarajan , V. and Sviridenko , M . 2008. Tight bounds for permutation flow shop scheduling . In Proceedings of the 13th Conference on Integer Programming and Combinatorial Optimization (IPCO). 154--168 . Nagarajan, V. and Sviridenko, M. 2008. Tight bounds for permutation flow shop scheduling. In Proceedings of the 13th Conference on Integer Programming and Combinatorial Optimization (IPCO). 154--168."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(91)90014-G"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/jos.96"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1099-1425(199909\/10)2:5<203::AID-JOS26>3.0.CO;2-5"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02684330"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979222676X"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.45.2.288"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2027216.2027218","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2027216.2027218","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:15Z","timestamp":1750278375000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2027216.2027218"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,10]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2011,10]]}},"alternative-id":["10.1145\/2027216.2027218"],"URL":"https:\/\/doi.org\/10.1145\/2027216.2027218","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,10]]},"assertion":[{"value":"2010-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}