{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T05:27:01Z","timestamp":1747459621525,"version":"3.37.3"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,4,14]],"date-time":"2024-04-14T00:00:00Z","timestamp":1713052800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,4,14]],"date-time":"2024-04-14T00:00:00Z","timestamp":1713052800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100003392","name":"Natural Science Foundation of Fujian Province","doi-asserted-by":"publisher","award":["2021J05011"],"award-info":[{"award-number":["2021J05011"]}],"id":[{"id":"10.13039\/501100003392","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Fundamental Research Funds for the Central Universities of Xiamen University","award":["20720210033"],"award-info":[{"award-number":["20720210033"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2024,5]]},"DOI":"10.1007\/s10878-024-01122-0","type":"journal-article","created":{"date-parts":[[2024,4,14]],"date-time":"2024-04-14T12:01:22Z","timestamp":1713096082000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Computational complexity and algorithms for two scheduling problems under linear constraints"],"prefix":"10.1007","volume":"47","author":[{"given":"Kameng","family":"Nip","sequence":"first","affiliation":[]},{"given":"Peng","family":"Xie","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,4,14]]},"reference":[{"issue":"3","key":"1122_CR1","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/s12553-021-00547-5","volume":"11","author":"ZA Abdalkareem","year":"2021","unstructured":"Abdalkareem ZA, Amir A, Al-Betar MA, Ekhan P, Hammouri AI (2021) Healthcare scheduling in optimization context: a review. Health Technol 11(3):445\u2013469","journal-title":"Health Technol"},{"key":"1122_CR2","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/978-1-4615-2025-2_3","volume-title":"Handbook of Global Optimization","author":"HP Benson","year":"1995","unstructured":"Benson HP (1995) Concave minimization: theory, applications and algorithms. In: Horst R, Pardalos PM (eds) Handbook of Global Optimization. Springer, Boston, pp 43\u2013148"},{"issue":"7","key":"1122_CR3","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/361011.361064","volume":"17","author":"JL Bruno","year":"1974","unstructured":"Bruno JL, Coffman EG Jr, Sethi R (1974) Scheduling independent tasks to reduce mean finishing time. Commun ACM 17(7):382\u2013387","journal-title":"Commun ACM"},{"key":"1122_CR4","unstructured":"Conway RW, Maxwell W, Miller L (1967) Theory of scheduling. Reading"},{"issue":"1","key":"1122_CR5","doi-asserted-by":"publisher","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I Dinur","year":"2005","unstructured":"Dinur I, Safra S (2005) On the hardness of approximating minimum vertex cover. Ann Math 162(1):439\u2013485","journal-title":"Ann Math"},{"key":"1122_CR6","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. Springer Science+Business Media, New York"},{"key":"1122_CR7","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, New York"},{"key":"1122_CR8","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1287\/moor.1.2.117","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey MR, Johnson DS, Sethi R (1976) The complexity of flowshop and jobshop scheduling. Math Oper Res 1:117\u2013129","journal-title":"Math Oper Res"},{"key":"1122_CR9","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1287\/opre.12.5.655","volume":"12","author":"C Gilmore","year":"1964","unstructured":"Gilmore C, Gomory RE (1964) Sequencing a one state-variable machine: a solvable case of the travelling salesman problem. Oper Res 12:655\u2013679","journal-title":"Oper Res"},{"issue":"1","key":"1122_CR10","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. Ann Discrete Math 5(1):287\u2013326","journal-title":"Ann Discrete Math"},{"key":"1122_CR11","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/BF01585870","volume":"82","author":"LA Hall","year":"1998","unstructured":"Hall LA (1998) Approximability of flow shop scheduling. Math Program 82:175\u2013190","journal-title":"Math Program"},{"issue":"3","key":"1122_CR12","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1287\/opre.44.3.510","volume":"44","author":"NG Hall","year":"1996","unstructured":"Hall NG, Sriskandarajah C (1996) A survey of machine scheduling problems with blocking and no-wait in process. Oper Res 44(3):510\u2013525","journal-title":"Oper Res"},{"key":"1122_CR13","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1002\/nav.3800010110","volume":"1","author":"SM Johnson","year":"1954","unstructured":"Johnson SM (1954) Optimal two- and three-stage production schedules with setup times included. Naval Res Logist Q 1:61\u201368","journal-title":"Naval Res Logist Q"},{"issue":"3","key":"1122_CR14","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S Khot","year":"2008","unstructured":"Khot S, Regev O (2008) Vertex cover might be hard to approximate to within $$2-\\epsilon $$. J Comput Syst Sci 74(3):335\u2013349","journal-title":"J Comput Syst Sci"},{"key":"1122_CR15","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","volume":"1","author":"J Lawler","year":"1977","unstructured":"Lawler J, Johnson E, Lenstra J, Rinnooy Kan A, Shmoys D (1977) The complexity of machine scheduling problems. Ann Discrete Math 1:343\u2013362","journal-title":"Ann Discrete Math"},{"key":"1122_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-18842-3","volume-title":"Linear and nonlinear programming","author":"DG Luenberger","year":"2016","unstructured":"Luenberger DG, Ye Y (2016) Linear and nonlinear programming, 4th edn. Springer, Berlin","edition":"4"},{"key":"1122_CR17","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/s10878-021-00754-w","volume":"43","author":"K Nip","year":"2022","unstructured":"Nip K, Shi T, Wang Z (2022) Some graph optimization problems with weights satisfying linear constraints. J Comb Optim 43:200\u2013225","journal-title":"J Comb Optim"},{"key":"1122_CR18","doi-asserted-by":"crossref","unstructured":"Nip K, Wang Z (2019) Two-machine flow shop scheduling problem under linear constraints. In: Li Y, Cardei M, Huang Y (eds) Combinatorial optimization and applications (COCOA19). pp 400\u2013411","DOI":"10.1007\/978-3-030-36412-0_32"},{"key":"1122_CR19","doi-asserted-by":"crossref","unstructured":"Nip K, Wang Z (2021) A complexity analysis and algorithms for two-machine shop scheduling problems under linear constraints. J Sched","DOI":"10.1007\/s10951-021-00677-8"},{"key":"1122_CR20","doi-asserted-by":"crossref","unstructured":"Nip K, Wang Z, Shi T (2019) Some graph optimization problems with weights satisfying linear constraints. In: Li Y, Cardei M, Huang Y (eds) COCOA 2019 (The 13th annual international conference on combinatorial optimization and applications), LNCS, vol 11949. Springer, pp 412\u2013424","DOI":"10.1007\/978-3-030-36412-0_33"},{"issue":"2","key":"1122_CR21","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. Eur J Oper Res 253(2):290\u2013297","journal-title":"Eur J Oper Res"},{"issue":"3","key":"1122_CR22","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. J Glob Optim 69(3):713\u2013725","journal-title":"J Glob Optim"},{"issue":"1","key":"1122_CR23","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/S0377-2217(02)00399-5","volume":"148","author":"W Ogryczak","year":"2003","unstructured":"Ogryczak W, \u015aliwi\u0144ski T (2003) On solving linear programs with the ordered weighted averaging objective. Eur J Oper Res 148(1):80\u201391","journal-title":"Eur J Oper Res"},{"key":"1122_CR24","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/978-3-642-13935-2_10","volume-title":"Fuzzy optimization: recent advances and applications","author":"W Ogryczak","year":"2010","unstructured":"Ogryczak W, \u015aliwi\u0144ski T (2010) On solving optimization problems with ordered average criteria and constraints. In: Lodwick WA, Kacprzyk J (eds) Fuzzy optimization: recent advances and applications. Springer, Berlin, pp 209\u2013230"},{"key":"1122_CR25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-05921-6","volume-title":"Scheduling: theory, algorithms, and systems","author":"M Pinedo","year":"2022","unstructured":"Pinedo M (2022) Scheduling: theory, algorithms, and systems, 6th edn. Springer, New York","edition":"6"},{"issue":"4","key":"1122_CR26","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1287\/moor.4.4.448","volume":"4","author":"S Sahni","year":"1979","unstructured":"Sahni S, Cho Y (1979) Complexity of scheduling shops with no wait in process. Math Oper Res 4(4):448\u2013457","journal-title":"Math Oper Res"},{"key":"1122_CR27","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"W Smith","year":"1956","unstructured":"Smith W (1956) Various optimizers for single-stage production. Naval Res Logist Q 3:59\u201366","journal-title":"Naval Res Logist Q"},{"key":"1122_CR28","volume-title":"Approximation algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani VV (2001) Approximation algorithms. Springer, Berlin"},{"issue":"5","key":"1122_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. J Comb Optim 34(5):1198\u20131209","journal-title":"J Comb Optim"},{"key":"1122_CR30","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The design of approximation algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson DP, Shmoys DB (2011) The design of approximation algorithms. Cambridge University Press, New York"},{"issue":"1","key":"1122_CR31","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1109\/21.87068","volume":"18","author":"RR Yager","year":"1988","unstructured":"Yager RR (1988) On ordered weighted averaging aggregation operators in multicriteria decision making. IEEE Trans Syst Man Cybern 18(1):183\u2013190","journal-title":"IEEE Trans Syst Man Cybern"},{"issue":"1","key":"1122_CR32","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0165-0114(95)00242-1","volume":"81","author":"RR Yager","year":"1996","unstructured":"Yager RR (1996) Constrained OWA aggregation. Fuzzy Sets Syst 81(1):89\u2013101","journal-title":"Fuzzy Sets Syst"},{"key":"1122_CR33","doi-asserted-by":"crossref","unstructured":"Zhang S, Nip K, Wang Z (2018) Related machine scheduling with machine speeds satisfying linear constraints. In: Kim D (eds) COCOA 2018 (The 12th annual international conference on combinatorial optimization and applications), LNCS, vol 11346. Springer, Switzerland, pp 314\u2013328","DOI":"10.1007\/978-3-030-04651-4_21"},{"issue":"3","key":"1122_CR34","doi-asserted-by":"publisher","first-page":"1724","DOI":"10.1007\/s10878-020-00523-1","volume":"44","author":"S Zhang","year":"2022","unstructured":"Zhang S, Nip K, Wang Z (2022) Related machine scheduling with machine speeds satisfying linear constraints. J Comb Optim 44(3):1724\u20131740","journal-title":"J Comb Optim"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01122-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01122-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01122-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,17]],"date-time":"2024-05-17T13:09:32Z","timestamp":1715951372000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01122-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,14]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["1122"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01122-0","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2024,4,14]]},"assertion":[{"value":"6 March 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 April 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have not disclosed any competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"55"}}