{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T19:25:34Z","timestamp":1743017134008,"version":"3.40.3"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031393433"},{"type":"electronic","value":"9783031393440"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-39344-0_5","type":"book-chapter","created":{"date-parts":[[2023,8,25]],"date-time":"2023-08-25T20:27:10Z","timestamp":1692995230000},"page":"58-70","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the\u00a0NP-Hardness of\u00a0Two Scheduling Problems Under Linear Constraints"],"prefix":"10.1007","author":[{"given":"Kameng","family":"Nip","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,8,26]]},"reference":[{"issue":"7","key":"5_CR1","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/361011.361064","volume":"17","author":"JL Bruno","year":"1974","unstructured":"Bruno, J.L., Coffman, E.G., Jr., Sethi, R.: Scheduling independent tasks to reduce mean finishing time. Commun. ACM 17(7), 382\u2013387 (1974)","journal-title":"Commun. ACM"},{"key":"5_CR2","unstructured":"Conway, R.W., Maxwell, W.L., Miller, L.W.: Theory of Scheduling. Reading (1967)"},{"key":"5_CR3","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.: Flow Shop Scheduling: Theoretical Results, Algorithms, and Applications. Springer, New York (2013). https:\/\/doi.org\/10.1007\/978-1-4614-5152-5"},{"key":"5_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, New York (1979)"},{"key":"5_CR5","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.: The complexity of flowshop and jobshop scheduling. Math. Oper. Res. 1, 117\u2013129 (1976)","journal-title":"Math. Oper. Res."},{"key":"5_CR6","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, R.E.: Sequencing a one state-variable machine: a solvable case of the travelling salesman problem. Oper. Res. 12, 655\u2013679 (1964)","journal-title":"Oper. Res."},{"key":"5_CR7","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/BF01585870","volume":"82","author":"LA Hall","year":"1998","unstructured":"Hall, L.A.: Approximability of flow shop scheduling. Math. Program. 82, 175\u2013190 (1998)","journal-title":"Math. Program."},{"issue":"3","key":"5_CR8","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1287\/opre.44.3.510","volume":"44","author":"NG Hall","year":"1996","unstructured":"Hall, N.G., Sriskandarajah, C.: A survey of machine scheduling problems with blocking and no-wait in process. Oper. Res. 44(3), 510\u2013525 (1996)","journal-title":"Oper. Res."},{"key":"5_CR9","doi-asserted-by":"crossref","unstructured":"Jansen, K., Lassota, A., Maack, M., Pikies, T.: Total completion time minimization for scheduling with incompatibility cliques. In: Proceedings of the International Conference on Automated Planning and Scheduling, vol. 31, no. 1, pp. 192\u2013200 (2021)","DOI":"10.1609\/icaps.v31i1.15962"},{"key":"5_CR10","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 Res. Logist. Q. 1, 61\u201368 (1954)","journal-title":"Naval Res. Logist. Q."},{"issue":"5","key":"5_CR11","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s10951-017-0550-0","volume":"21","author":"D Knop","year":"2018","unstructured":"Knop, D., Kouteck\u00fd, M.: Scheduling meets n-fold integer programming. J. Sched. 21(5), 493\u2013503 (2018)","journal-title":"J. Sched."},{"key":"5_CR12","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","volume":"1","author":"JL Lawler","year":"1977","unstructured":"Lawler, J.L., Johnson, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: The complexity of machine scheduling problems. Ann. Discrete Math. 1, 343\u2013362 (1977)","journal-title":"Ann. Discrete Math."},{"key":"5_CR13","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, D.G., Ye, Y.: Linear and Nonlinear Programming, 4th edn. Springer, Cham (2016)","edition":"4"},{"key":"5_CR14","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.: Some graph optimization problems with weights satisfying linear constraints. J. Comb. Optim. 43, 200\u2013225 (2022)","journal-title":"J. Comb. Optim."},{"key":"5_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1007\/978-3-030-36412-0_32","volume-title":"Combinatorial Optimization and Applications","author":"K Nip","year":"2019","unstructured":"Nip, K., Wang, Z.: Two-machine flow shop scheduling problem under linear constraints. In: Li, Y., Cardei, M., Huang, Y. (eds.) COCOA 2019. LNCS, vol. 11949, pp. 400\u2013411. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-36412-0_32"},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"Nip, K., Wang, Z.: A complexity analysis and algorithms for two-machine shop scheduling problems under linear constraints. J. Sched. (2021)","DOI":"10.1007\/s10951-021-00677-8"},{"key":"5_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1007\/978-3-030-36412-0_33","volume-title":"Combinatorial Optimization and Applications","author":"K Nip","year":"2019","unstructured":"Nip, K., Wang, Z., Shi, T.: Some graph optimization problems with weights satisfying linear constraints. In: Li, Y., Cardei, M., Huang, Y. (eds.) COCOA 2019. LNCS, vol. 11949, pp. 412\u2013424. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-36412-0_33"},{"issue":"2","key":"5_CR18","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.: Scheduling under linear constraints. Eur. J. Oper. Res. 253(2), 290\u2013297 (2016)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"5_CR19","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.: Knapsack with variable weights satisfying linear constraints. J. Global Optim. 69(3), 713\u2013725 (2017). https:\/\/doi.org\/10.1007\/s10898-017-0540-y","journal-title":"J. Global Optim."},{"issue":"1","key":"5_CR20","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.: On solving linear programs with the ordered weighted averaging objective. Eur. J. Oper. Res. 148(1), 80\u201391 (2003)","journal-title":"Eur. J. Oper. Res."},{"key":"5_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-26580-3","volume-title":"Scheduling: Theory, Algorithms, and Systems","author":"M Pinedo","year":"2016","unstructured":"Pinedo, M.: Scheduling: Theory, Algorithms, and Systems. Springer, New York (2016)"},{"issue":"4","key":"5_CR22","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.: Complexity of scheduling shops with no wait in process. Math. Oper. Res. 4(4), 448\u2013457 (1979)","journal-title":"Math. Oper. Res."},{"key":"5_CR23","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"WE Smith","year":"1956","unstructured":"Smith, W.E.: Various optimizers for single-stage production. Naval Res. Logist. Q. 3, 59\u201366 (1956)","journal-title":"Naval Res. Logist. Q."},{"issue":"4","key":"5_CR24","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.: Bin packing under linear constraints. J. Comb. Optim. 34(4), 1198\u20131209 (2017). https:\/\/doi.org\/10.1007\/s10878-017-0140-2","journal-title":"J. Comb. Optim."},{"issue":"1","key":"5_CR25","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1109\/21.87068","volume":"18","author":"RR Yager","year":"1988","unstructured":"Yager, R.R.: On ordered weighted averaging aggregation operators in multicriteria decisionmaking. IEEE Trans. Syst. Man Cybern. 18(1), 183\u2013190 (1988)","journal-title":"IEEE Trans. Syst. Man Cybern."},{"issue":"1","key":"5_CR26","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0165-0114(95)00242-1","volume":"81","author":"RR Yager","year":"1996","unstructured":"Yager, R.R.: Constrained OWA aggregation. Fuzzy Sets Syst. 81(1), 89\u2013101 (1996)","journal-title":"Fuzzy Sets Syst."},{"key":"5_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1007\/978-3-030-04651-4_21","volume-title":"Combinatorial Optimization and Applications","author":"S Zhang","year":"2018","unstructured":"Zhang, S., Nip, K., Wang, Z.: Related machine scheduling with machine speeds satisfying linear constraints. In: Kim, D., Uma, R.N., Zelikovsky, A. (eds.) COCOA 2018. LNCS, vol. 11346, pp. 314\u2013328. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-04651-4_21"},{"issue":"3","key":"5_CR28","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.: Related machine scheduling with machine speeds satisfying linear constraints. J. Comb. Optim. 44(3), 1724\u20131740 (2022)","journal-title":"J. Comb. Optim."}],"container-title":["Lecture Notes in Computer Science","Frontiers of Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-39344-0_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,25]],"date-time":"2023-08-25T20:27:33Z","timestamp":1692995253000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-39344-0_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031393433","9783031393440"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-39344-0_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"26 August 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IJTCS-FAW","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Frontiers in Algorithmics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Macau","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 August 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 August 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"faw2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/conferences.cis.um.edu.mo\/ijtcs2023\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"34","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"21","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"62% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}