{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T19:34:37Z","timestamp":1725824077552},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319213972"},{"type":"electronic","value":"9783319213989"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-21398-9_8","type":"book-chapter","created":{"date-parts":[[2015,6,23]],"date-time":"2015-06-23T15:12:41Z","timestamp":1435072361000},"page":"97-108","source":"Crossref","is-referenced-by-count":3,"title":["Combinations of Some Shop Scheduling Problems and the Shortest Path Problem: Complexity and Approximation Algorithms"],"prefix":"10.1007","author":[{"given":"Kameng","family":"Nip","sequence":"first","affiliation":[]},{"given":"Zhenbo","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Wenxun","family":"Xing","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,24]]},"reference":[{"key":"8_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1007\/11809678_45","volume-title":"Computing and Combinatorics","author":"H Aissi","year":"2006","unstructured":"Aissi, H., Bazgan, C., Vanderpooten, D.: Approximating min-max (regret) versions of some polynomial problems. In: Chen, D.Z., Lee, D.T. (eds.) COCOON 2006. LNCS, vol. 4112, pp. 428\u2013438. Springer, Heidelberg (2006)"},{"key":"8_CR2","first-page":"177","volume":"15","author":"I B\u00e1r\u00e1ny","year":"1982","unstructured":"B\u00e1r\u00e1ny, I., Fiala, T.: T\u00f6bbg\u00e9pes \u00fctemez\u00e9si probl\u00e9m\u00e1k k\u00f6zel optim\u00e1lis megold\u00e1sa (in Hungarian). Szigma - Matematikai - K\u00f6zgazdas\u00e1gi Foly\u00f3irat 15, 177\u2013191 (1982)","journal-title":"Szigma - Matematikai - K\u00f6zgazdas\u00e1gi Foly\u00f3irat"},{"key":"8_CR3","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik 1, 269\u2013271 (1959)","journal-title":"Numerische Mathematik"},{"key":"8_CR4","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco (1979)"},{"key":"8_CR5","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1145\/321978.321985","volume":"23","author":"T Gonzalez","year":"1976","unstructured":"Gonzalez, T., Sahni, S.: Open shop scheduling to minimize finish time. Journal of the Association for Computing Machinery 23, 665\u2013679 (1976)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"8_CR6","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1002\/nav.3800030307","volume":"3","author":"JR Jackson","year":"1956","unstructured":"Jackson, J.R.: An extension of Johnson\u2019s results on job-lot scheduling. Naval Research Logistics Quarterly 3, 201\u2013203 (1956)","journal-title":"Naval Research Logistics Quarterly"},{"key":"8_CR7","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1137\/S0895480199363908","volume":"16","author":"K Jansen","year":"2003","unstructured":"Jansen, K., Solis-Oba, R., Sviridenko, M.: Makespan minimization in job shops: A linear time approximation scheme. SIAM Journal on Discrete Mathematics 16, 288\u2013300 (2003)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"8_CR8","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1002\/nav.3800010110","volume":"1","author":"SM Johnson","year":"1954","unstructured":"Johnson, S.M.: Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly 1, 61\u201368 (1954)","journal-title":"Naval Research Logistics Quarterly"},{"key":"8_CR9","first-page":"343","volume":"1","author":"JK Lenstra","year":"1977","unstructured":"Lenstra, J.K., Kan, A.R., Brucker, P.: Complexity of machine scheduling problems. Annals of Operations Research 1, 343\u2013362 (1977)","journal-title":"Annals of Operations Research"},{"key":"8_CR10","first-page":"121","volume":"4","author":"JK Lenstra","year":"1979","unstructured":"Lenstra, J.K., Rinnooy Kan, A.: Computational complexity of discrete optimization. Annals of Operations Research 4, 121\u2013140 (1979)","journal-title":"Annals of Operations Research"},{"key":"8_CR11","doi-asserted-by":"publisher","first-page":"20:1","DOI":"10.1145\/2027216.2027218","volume":"58","author":"M Mastrolilli","year":"2011","unstructured":"Mastrolilli, M., Svensson, O.: Hardness of approximating flow and job shop scheduling problems. Journal of the Association for Computing Machinery 58, 20:1\u201320:32 (2011)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"8_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"680","DOI":"10.1007\/978-3-642-38768-5_60","volume-title":"Computing and Combinatorics","author":"K Nip","year":"2013","unstructured":"Nip, K., Wang, Z.: Combination of two-machine flow shop scheduling and shortest path problems. In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol. 7936, pp. 680\u2013687. Springer, Heidelberg (2013)"},{"key":"8_CR13","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1007\/s10878-013-9670-4","volume":"29","author":"K Nip","year":"2015","unstructured":"Nip, K., Wang, Z., Talla Nobibon, F., Leus, R.: A Combination of Flow Shop Scheduling and the Shortest Path Problem. Journal of Combinatorial Optimization 29, 36\u201352 (2015)","journal-title":"Journal of Combinatorial Optimization"},{"key":"8_CR14","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1137\/S089548019223872X","volume":"8","author":"JP Schmidt","year":"1995","unstructured":"Schmidt, J.P., Siegel, A., Srinivasan, A.: Chernoff-hoeffding bounds for applications with limited independence. SIAM Journal on Discrete Mathematics 8, 223\u2013250 (1995)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"8_CR15","first-page":"191","volume":"82","author":"SV Sevastianov","year":"1998","unstructured":"Sevastianov, S.V., Woeginger, G.J.: Makespan minimization in open shops: A polynomial time approximation scheme. Mathematical Programming 82, 191\u2013198 (1998)","journal-title":"Mathematical Programming"},{"key":"8_CR16","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1137\/S009753979222676X","volume":"23","author":"DB Shmoys","year":"1994","unstructured":"Shmoys, D.B., Stein, C., Wein, J.: Improved approximation algorithms for shop scheduling problems. SIAM Journal on Computing 23, 617\u2013632 (1994)","journal-title":"SIAM Journal on Computing"},{"key":"8_CR17","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1016\/j.tcs.2012.06.003","volume":"460","author":"Z Wang","year":"2012","unstructured":"Wang, Z., Cui, Z.: Combination of parallel machine scheduling and vertex cover. Theoretical Computer Science 460, 10\u201315 (2012)","journal-title":"Theoretical Computer Science"},{"key":"8_CR18","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1287\/opre.45.2.288","volume":"45","author":"DP Williamson","year":"1997","unstructured":"Williamson, D.P., Hall, L.A., Hoogeveen, J.A., Hurkens, C.A.J., Lenstra, J.K., Sevast\u2019janov, S.V., Shmoys, D.B.: Short shop schedules. Operations Research 45, 288\u2013294 (1997)","journal-title":"Operations Research"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21398-9_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T08:05:37Z","timestamp":1559203537000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-21398-9_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319213972","9783319213989"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21398-9_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}