{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T02:10:38Z","timestamp":1740103838346,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T00:00:00Z","timestamp":1615507200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T00:00:00Z","timestamp":1615507200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11801589","11771245"],"award-info":[{"award-number":["11801589","11771245"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11371216"],"award-info":[{"award-number":["11371216"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2023,12]]},"DOI":"10.1007\/s10951-021-00677-8","type":"journal-article","created":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T05:02:32Z","timestamp":1615525352000},"page":"543-558","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A complexity analysis and algorithms for two-machine shop scheduling problems under linear constraints"],"prefix":"10.1007","volume":"26","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8597-3295","authenticated-orcid":false,"given":"Kameng","family":"Nip","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhenbo","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,3,12]]},"reference":[{"issue":"3","key":"677_CR1","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0167-6377(85)90017-3","volume":"4","author":"R Ahuja","year":"1985","unstructured":"Ahuja, R. (1985). Minimax linear programming problem. Operations Research Letters, 4(3), 131\u2013134.","journal-title":"Operations Research Letters"},{"issue":"8","key":"677_CR2","doi-asserted-by":"publisher","first-page":"971","DOI":"10.1016\/S0305-0548(00)00097-6","volume":"29","author":"A Allahverdi","year":"2002","unstructured":"Allahverdi, A., & Al-Anzi, F. S. (2002). Using two-machine flowshop with maximum lateness objective to model multimedia data objects scheduling problem for www applications. Computers & Operations Research, 29(8), 971\u2013994.","journal-title":"Computers & Operations Research"},{"key":"677_CR3","first-page":"177","volume":"15","author":"I B\u00e1r\u00e1ny","year":"1982","unstructured":"B\u00e1r\u00e1ny, I., & Fiala, T. (1982). 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.","journal-title":"Szigma - Matematikai - K\u00f6zgazdas\u00e1gi Foly\u00f3irat"},{"key":"677_CR4","first-page":"1493","volume-title":"Handbook of combinatorial optimization","author":"B Chen","year":"1999","unstructured":"Chen, B., Potts, C. N., & Woeginger, G. J. (1999). A review of machine scheduling: Complexity, algorithms and approximability. In D. Z. Du & P. M. Pardalos (Eds.), Handbook of combinatorial optimization (pp. 1493\u20131641). Boston: Springer."},{"key":"677_CR5","unstructured":"Conway, R. W., Maxwell, W., & Miller, L. (1967). Theory of Scheduling. Reading. MA: Addison-Wesley."},{"key":"677_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7091-3644-7","volume-title":"Linear programming in industry, theory and applications: An introduction","author":"S Dan\u00f8","year":"1960","unstructured":"Dan\u00f8, S. (1960). Linear programming in industry, theory and applications: An introduction. Vienna: Springer."},{"key":"677_CR7","volume-title":"Linear programming and its applications","author":"HA Eiselt","year":"2007","unstructured":"Eiselt, H. A., & Sandblom, C. L. (2007). Linear programming and its applications. Berlin: Springer."},{"key":"677_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-5152-5","volume-title":"Flow shop scheduling: Theoretical results, algorithms, and applications","author":"H Emmons","year":"2013","unstructured":"Emmons, H., & Vairaktarakis, G. (2013). Flow shop scheduling: Theoretical results, algorithms, and applications. New York: Springer."},{"key":"677_CR9","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1287\/moor.1.2.117","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1, 117\u2013129.","journal-title":"Mathematics of Operations Research"},{"issue":"4","key":"677_CR10","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1145\/321978.321985","volume":"23","author":"T Gonzalez","year":"1976","unstructured":"Gonzalez, T., & Sahni, S. (1976). Open shop scheduling to minimize finish time. Journal of the Association for Computing Machinery, 23(4), 665\u2013679.","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"1","key":"677_CR11","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"R Graham","year":"1979","unstructured":"Graham, R., Lawler, E., Lenstra, J., & Kan, A. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5(1), 287\u2013326.","journal-title":"Annals of Discrete Mathematics"},{"key":"677_CR12","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/BF01585870","volume":"82","author":"LA Hall","year":"1998","unstructured":"Hall, L. A. (1998). Approximability of flow shop scheduling. Mathematical Programming, 82, 175\u2013190.","journal-title":"Mathematical Programming"},{"key":"677_CR13","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1002\/nav.3800030307","volume":"3","author":"JR Jackson","year":"1956","unstructured":"Jackson, J. R. (1956). An extension of Johnsons results on job-lot scheduling. Naval Research Logistics Quarterly, 3, 201\u2013203.","journal-title":"Naval Research Logistics Quarterly"},{"key":"677_CR14","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. (2003). Makespan minimization in job shops: A linear time approximation scheme. SIAM Journal on Discrete Mathematics, 16, 288\u2013300.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"677_CR15","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1002\/nav.3800010110","volume":"1","author":"SM Johnson","year":"1954","unstructured":"Johnson, S. M. (1954). Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1, 61\u201368.","journal-title":"Naval Research Logistics Quarterly"},{"issue":"4","key":"677_CR16","doi-asserted-by":"publisher","first-page":"802","DOI":"10.1287\/opre.22.4.802","volume":"22","author":"S Kaplan","year":"1974","unstructured":"Kaplan, S. (1974). Application of programs with maximin objective functions to problems of optimal resource allocation. Operations Research, 22(4), 802\u2013807.","journal-title":"Operations Research"},{"key":"677_CR17","first-page":"121","volume":"4","author":"JK Lenstra","year":"1979","unstructured":"Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Computational complexity of discrete optimization problems. Annals of Operations Research, 4, 121\u2013140.","journal-title":"Annals of Operations Research"},{"key":"677_CR18","first-page":"343","volume":"1","author":"JK Lenstra","year":"1977","unstructured":"Lenstra, J. K., Rinnooy Kan, A. H. G., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Operations Research, 1, 343\u2013362.","journal-title":"Annals of Operations Research"},{"issue":"58","key":"677_CR19","first-page":"20:1","volume":"5","author":"M Mastrolilli","year":"2011","unstructured":"Mastrolilli, M., & Svensson, O. (2011). Hardness of approximating flow and job shop scheduling problems. Journal of the Association for Computing Machinery, 5(58), 20:1\u201320:32.","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"6","key":"677_CR20","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1057\/jors.1995.102","volume":"46","author":"A Nagar","year":"1995","unstructured":"Nagar, A., Heragu, S. S., & Haddock, J. (1995). A branch-and-bound approach for a two-machine flowshop scheduling problem. Journal of the Operational Research Society, 46(6), 721\u2013734.","journal-title":"Journal of the Operational Research Society"},{"key":"677_CR21","doi-asserted-by":"crossref","unstructured":"Nip, K., & Wang, Z. (2019). Two-machine flow shop scheduling problem under linear constraints. In Y. Li, M. Cardei, & Y. Huang (Eds.), COCOA 2019 (The 13th annual international conference on combinatorial optimization and applications), LNCS (Vol. 11949, pp. 400\u2013411). Cham: Springer.","DOI":"10.1007\/978-3-030-36412-0_32"},{"key":"677_CR22","doi-asserted-by":"crossref","unstructured":"Nip, K., Wang, Z., & Shi, T. (2019). Some graph optimization problems with weights satisfying linear constraints. In Y. Li, M. Cardei, & Y. Huang (Eds.), COCOA 2019 (The 13th annual international conference on combinatorial optimization and applications), LNCS (Vol. 11949, pp. 412\u2013424). Cham: Springer.","DOI":"10.1007\/978-3-030-36412-0_33"},{"issue":"2","key":"677_CR23","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1016\/j.ejor.2016.02.028","volume":"253","author":"K Nip","year":"2016","unstructured":"Nip, K., Wang, Z., & Wang, Z. (2016). Scheduling under linear constraints. European Journal of Operational Research, 253(2), 290\u2013297.","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"677_CR24","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1007\/s10898-017-0540-y","volume":"69","author":"K Nip","year":"2017","unstructured":"Nip, K., Wang, Z., & Wang, Z. (2017). Knapsack with variable weights satisfying linear constraints. Journal of Global Optimization, 69(3), 713\u2013725.","journal-title":"Journal of Global Optimization"},{"key":"677_CR25","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-2361-4","volume-title":"Scheduling: Theory, algorithms, and systems","author":"M Pinedo","year":"2012","unstructured":"Pinedo, M. (2012). Scheduling: Theory, algorithms, and systems. New York: Springer."},{"key":"677_CR26","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. (1995). Chernoff\u2013Hoeffding bounds for applications with limited independence. SIAM Journal on Discrete Mathematics, 8, 223\u2013250.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"677_CR27","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/BF01585871","volume":"82","author":"SV Sevastianov","year":"1998","unstructured":"Sevastianov, S. V., & Woeginger, G. J. (1998). Makespan minimization in open shops: A polynomial time approximation scheme. Mathematical Programming, 82, 191\u2013198.","journal-title":"Mathematical Programming"},{"key":"677_CR28","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. (1994). Improved approximation algorithms for shop scheduling problems. SIAM Journal on Computing, 23, 617\u2013632.","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"677_CR29","doi-asserted-by":"publisher","first-page":"1198","DOI":"10.1007\/s10878-017-0140-2","volume":"34","author":"Z Wang","year":"2017","unstructured":"Wang, Z., & Nip, K. (2017). Bin packing under linear constraints. Journal of Combinatorial Optimization, 34(5), 1198\u20131209.","journal-title":"Journal of Combinatorial Optimization"},{"key":"677_CR30","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., et al. (1997). Short shop schedules. Operations Research, 45, 288\u2013294.","journal-title":"Operations Research"},{"key":"677_CR31","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032701","volume-title":"Interior point algorithms: Theory and analysis","author":"Y Ye","year":"1997","unstructured":"Ye, Y. (1997). Interior point algorithms: Theory and analysis. New York: Wiley-Interscience."},{"key":"677_CR32","doi-asserted-by":"crossref","unstructured":"Zhang, S., Nip, K., & Wang, Z. (2018). Related machine scheduling with machine speeds satisfying linear constraints. In: D. Kim (Ed.), COCOA 2018 (The 12th annual international conference on combinatorial optimization and applications), LNCS (Vol. 11346, pp. 314\u2013328). Switzerland: Springer.","DOI":"10.1007\/978-3-030-04651-4_21"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-021-00677-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-021-00677-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-021-00677-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,27]],"date-time":"2023-11-27T08:10:22Z","timestamp":1701072622000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-021-00677-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,12]]},"references-count":32,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["677"],"URL":"https:\/\/doi.org\/10.1007\/s10951-021-00677-8","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"type":"print","value":"1094-6136"},{"type":"electronic","value":"1099-1425"}],"subject":[],"published":{"date-parts":[[2021,3,12]]},"assertion":[{"value":"25 January 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 March 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}