{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T22:43:53Z","timestamp":1777416233805,"version":"3.51.4"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2005,5,1]],"date-time":"2005-05-01T00:00:00Z","timestamp":1114905600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2005,5]]},"DOI":"10.1007\/s10878-005-1414-7","type":"journal-article","created":{"date-parts":[[2005,6,28]],"date-time":"2005-06-28T20:57:18Z","timestamp":1119992238000},"page":"313-323","source":"Crossref","is-referenced-by-count":29,"title":["A Framework for the Complexity of High-Multiplicity Scheduling Problems"],"prefix":"10.1007","volume":"9","author":[{"given":"N.","family":"Brauner","sequence":"first","affiliation":[]},{"given":"Y.","family":"Crama","sequence":"additional","affiliation":[]},{"given":"A.","family":"Grigoriev","sequence":"additional","affiliation":[]},{"given":"J.","family":"van de Klundert","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"1414_CR1","doi-asserted-by":"crossref","first-page":"518","DOI":"10.1287\/moor.27.3.518.314","volume":"27","author":"A. Bar-Noy","year":"2002","unstructured":"A. Bar-Noy, R. Bhatia, J.S. Naor, and B. Schiber, \u201cMinimizing service and operation costs of periodic scheduling,\u201d Mathematics of Operations Research, vol. 27, pp. 518\u2013544, 2002.","journal-title":"Mathematics of Operations Research"},{"key":"1414_CR2","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/S0166-218X(03)00222-1","volume":"134","author":"N. Brauner","year":"2004","unstructured":"N. Brauner and Y. Crama, \u201cThe maximum deviation just-in-time scheduling problem,\u201d Discrete Applied Mathematics, vol. 134, pp. 25\u201350, 2004.","journal-title":"Discrete Applied Mathematics"},{"key":"1414_CR3","unstructured":"N. Brauner, Y. Crama, A. Grigoriev, and J. van de Klundert, \u201cOn the complexity of high-multiplicity scheduling problems,\u201d University of Li\u00e8ge, Li\u00e8ge, Belgium, Working paper GEMME 0110, 2001."},{"key":"1414_CR4","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1023\/A:1024008726557","volume":"6","author":"N. Brauner","year":"2003","unstructured":"N. Brauner, G. Finke, and W. Kubiak, \u201cComplexity of one-cycle robotic flow-shops,\u201d Journal of Scheduling, vol. 6, pp. 355\u2013371, 2003.","journal-title":"Journal of Scheduling"},{"key":"1414_CR5","doi-asserted-by":"crossref","first-page":"788","DOI":"10.1287\/opre.48.5.788.12405","volume":"48","author":"J.J. Clifford","year":"2000","unstructured":"J.J. Clifford and M. E. Posner, \u201cHigh multiplicity in earliness-tardiness scheduling,\u201d Operations Research, vol. 48, pp. 788\u2013800, 2000.","journal-title":"Operations Research"},{"key":"1414_CR6","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/PL00011403","volume":"89","author":"J.J. Clifford","year":"2001","unstructured":"J.J. Clifford and M.E. Posner, \u201cParallel machine scheduling with high multiplicity,\u201d Mathematical Programming, vol. 89, pp. 359\u2013383, 2001.","journal-title":"Mathematical Programming"},{"key":"1414_CR7","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1137\/0213007","volume":"13","author":"S.S. Cosmadakis","year":"1984","unstructured":"S.S. Cosmadakis and C.H. Papadimitriou, \u201cThe traveling salesman problem with many visits to few cities,\u201d SIAM Journal on Computing, vol. 13, pp. 99\u2013108, 1984.","journal-title":"SIAM Journal on Computing"},{"key":"1414_CR8","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1287\/moor.8.3.381","volume":"8","author":"M.E. Dyer","year":"1983","unstructured":"M.E. Dyer, \u201cThe complexity of vertex enumeration methods,\u201d Mathematics of Operations Research, vol. 8, pp. 381\u2013402, 1983.","journal-title":"Mathematics of Operations Research"},{"key":"1414_CR9","unstructured":"M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman: San Francisco, CA, 1979."},{"key":"1414_CR10","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/0166-218X(93)90034-L","volume":"41","author":"F. Granot","year":"1993","unstructured":"F. Granot and J. Skorin-Kapov, \u201cOn polynomial solvability of the high multiplicity total weighted tardiness problem,\u201d Discrete Applied Mathematics, vol. 41, pp. 139\u2013146, 1993.","journal-title":"Discrete Applied Mathematics"},{"key":"1414_CR11","unstructured":"A. Grigoriev, \u201cHigh Multiplicity Scheduling Problems,\u201d Maastricht University, The Netherlands, Doctoral thesis, 2003."},{"key":"1414_CR12","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0166-218X(90)90093-R","volume":"28","author":"D.S. Hochbaum","year":"1990","unstructured":"D.S. Hochbaum and R. Shamir, \u201cMinimizing the number of tardy job units under release time constraints,\u201d Discrete Applied Mathematics, vol. 28, pp. 45\u201357, 1990.","journal-title":"Discrete Applied Mathematics"},{"key":"1414_CR13","doi-asserted-by":"crossref","first-page":"648","DOI":"10.1287\/opre.39.4.648","volume":"39","author":"D.S. Hochbaum","year":"1991","unstructured":"D.S. Hochbaum and R. Shamir, \u201cStrongly polynomial algorithms for the high multiplicity scheduling problem,\u201d Operations Research, vol. 39, pp. 648\u2013653, 1991.","journal-title":"Operations Research"},{"key":"1414_CR14","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/BF01581207","volume":"55","author":"D.S. Hochbaum","year":"1992","unstructured":"D.S. Hochbaum, R. Shamir, and J.G. Shanthikumar, \u201cA polynomial algorithm for an integer quadratic nonseparable transportation problem,\u201d Mathematical Programming, vol. 55, pp. 359\u2013376, 1992.","journal-title":"Mathematical Programming"},{"key":"1414_CR15","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/S0166-218X(00)00316-4","volume":"112","author":"J. Hurink","year":"2001","unstructured":"J. Hurink and S. Knust, \u201cMakespan minimization for flow-shop problems with transportation times and a single robot,\u201d Discrete Applied Mathematics, vol. 112, pp. 199\u2013216, 2001.","journal-title":"Discrete Applied Mathematics"},{"key":"1414_CR16","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"D.S. Johnson","year":"1988","unstructured":"D.S. Johnson, M. Yannakakis, and C.H. Papadimitriou, \u201cOn generating all maximal independent sets,\u201d Information Processing Letters, vol. 27, pp. 119\u2013123, 1988.","journal-title":"Information Processing Letters"},{"key":"1414_CR17","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1287\/mnsc.37.1.121","volume":"37","author":"W. Kubiak","year":"1991","unstructured":"W. Kubiak and S.P. Sethi, \u201cA note on \u201cLevel schedules for mixed-model assembly lines in just-in-time production systems,\u201d Management Science, vol. 37, pp. 121\u2013122, 1991.","journal-title":"Management Science"},{"key":"1414_CR18","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/BF01328809","volume":"6","author":"W. Kubiak","year":"1994","unstructured":"W. Kubiak and S.P. Sethi, \u201cOptimal just-in-time schedules for flexible transfer lines,\u201d International Journal of Flexible Manufacturing Systems, vol. 6, pp. 137\u2013154, 1994.","journal-title":"International Journal of Flexible Manufacturing Systems"},{"key":"1414_CR19","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1137\/0209042","volume":"9","author":"E.L. Lawler","year":"1980","unstructured":"E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Kan, \u201cGenerating all maximal independent sets: NP-hardness and polynomial-time algorithms,\u201d SIAM Journal on Computing, vol. 9, pp. 558\u2013565, 1980.","journal-title":"SIAM Journal on Computing"},{"key":"1414_CR20","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1287\/moor.26.1.31.10590","volume":"26","author":"S.T. McCormick","year":"2001","unstructured":"S.T. McCormick, S.R. Smallwood, and F.C.R. Spieksma, \u201cA polynomial algorithm for multiprocessor scheduling with two job lengths,\u201d Mathematics of Operations Research, vol. 26, pp. 31\u201349, 2001.","journal-title":"Mathematics of Operations Research"},{"key":"1414_CR21","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1287\/mnsc.35.2.192","volume":"35","author":"J. Miltenburg","year":"1989","unstructured":"J. Miltenburg, \u201cLevel schedules for mixed-model assembly lines in just-in-time production systems,\u201d Management Science, vol. 35, pp. 192\u2013207, 1989.","journal-title":"Management Science"},{"key":"1414_CR22","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/s001860200242","volume":"57","author":"A. Munier","year":"2003","unstructured":"A. Munier and F. Sourd, \u201cScheduling chains on a single machine with non-negative time-lags,\u201d Mathematical Methods of Operations Research, vol. 57, pp. 111\u2013123, 2003.","journal-title":"Mathematical Methods of Operations Research"},{"key":"1414_CR23","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"C.H. Papadimitriou","year":"1982","unstructured":"C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice Hall: Englewood Cliffs, N.J., 1982."},{"key":"1414_CR24","volume-title":"Scheduling: Theory, Algorithms and Systems","author":"M. Pinedo","year":"1995","unstructured":"M. Pinedo, Scheduling: Theory, Algorithms and Systems, Prentice Hall: Englewood Cliffs, N.J., 1995."},{"key":"1414_CR25","unstructured":"M.E. Posner, \u201cThe complexity of earliness and tardiness scheduling problems under id-encoding,\u201d New York University, New York, U.S.A, Working Paper 85\u201370, 1985."},{"key":"1414_CR26","doi-asserted-by":"crossref","first-page":"1347","DOI":"10.1287\/opre.28.6.1347","volume":"28","author":"H.N. Psaraftis","year":"1980","unstructured":"H.N. Psaraftis, \u201cA dynamic programming approach for sequencing groups of identical jobs,\u201d Operations Research, vol. 28, pp. 1347\u20131359, 1980.","journal-title":"Operations Research"},{"key":"1414_CR27","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1287\/opre.14.3.532","volume":"14","author":"M. Rothkopf","year":"1966","unstructured":"M. Rothkopf, \u201cThe travelling salesman problem: On the reduction of certain large problems to smaller ones,\u201d Operations Research, vol. 14, pp. 532\u2013533, 1966.","journal-title":"Operations Research"},{"key":"1414_CR28","doi-asserted-by":"crossref","first-page":"728","DOI":"10.1287\/mnsc.39.6.728","volume":"39","author":"G. Steiner","year":"1993","unstructured":"G. Steiner and J.S. Yeomans, \u201cLevel schedules for mixed-model, just-in-time processes,\u201d Management Science, vol. 39, pp. 728\u2013735, 1993.","journal-title":"Management Science"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-005-1414-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-005-1414-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-005-1414-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:18:08Z","timestamp":1559276288000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-005-1414-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,5]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2005,5]]}},"alternative-id":["1414"],"URL":"https:\/\/doi.org\/10.1007\/s10878-005-1414-7","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,5]]}}}