{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:26:27Z","timestamp":1759638387842},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540770497"},{"type":"electronic","value":"9783540770503"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-77050-3_8","type":"book-chapter","created":{"date-parts":[[2007,11,26]],"date-time":"2007-11-26T08:39:22Z","timestamp":1196066362000},"page":"96-107","source":"Crossref","is-referenced-by-count":22,"title":["Order Scheduling Models: Hardness and Algorithms"],"prefix":"10.1007","author":[{"given":"Naveen","family":"Garg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amit","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vinayaka","family":"Pandit","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"8_CR1","volume-title":"Proceedings of the 4th IEEE Symposium on High Performance Distributed Computing","author":"D. Abramson","year":"1995","unstructured":"Abramson, D., Sosic, R., Giddy, J., Hall, B.: Nimrod: A tool for performing parameterised simulations using distributed applications. In: Proceedings of the 4th IEEE Symposium on High Performance Distributed Computing, IEEE Computer Society Press, Los Alamitos (1995)"},{"key":"8_CR2","doi-asserted-by":"crossref","unstructured":"Afrati, F., Bampis, E., Chekuri, C., Karger, D., Kenyon, C., Khanna, S., Milis, I., Queyranne, M., Skutella, M., Stein, C., Sviridenko, M.: Approximation schemes for minimizing average weighted completion time with release dates. In: FOCS, pp. 32\u201344 (1999)","DOI":"10.1109\/SFFCS.1999.814574"},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Azar, Y., Leonardi, S., Regev, O.: Minimizing the flow time without migration. In: ACM Symposium on Theory of Computing (STOC), pp. 198\u2013205 (1999)","DOI":"10.1145\/301250.301304"},{"key":"8_CR4","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/s101070100255","volume":"91","author":"N. Brixius","year":"2002","unstructured":"Brixius, N., Linderoth, J., Goux, J.: Solving large quadratic assignment problems on computational grid. Mathematical Programming, Series B\u00a091, 563\u2013588 (2002)","journal-title":"Mathematical Programming, Series B"},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"Chakrabarti, S., Phillips, C., Schulz, A., Shmoys, D., Stein, C., Wein, J.: Improved scheduling algorithms for minsum criteria. In: Proc. of the 23rd Int. Colloquium on Automata, Languages and Programming, pp. 646\u2013657 (1996)","DOI":"10.1007\/3-540-61440-0_166"},{"key":"8_CR6","unstructured":"Chen, Z., Hall, N.: Supply chain scheduling: Assembly systems. Technical report, The Ohio State University (2000)"},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"Gandhi, R., Halldorsson, M., Kortsarz, G., Shachnai, H.: Improved results for data migration and open shop scheduling. In: Proc. of the 31st Int. Colloquium on Automata, Languages, and Programming, pp. 658\u2013669 (2004)","DOI":"10.1007\/978-3-540-27836-8_56"},{"key":"8_CR8","doi-asserted-by":"crossref","unstructured":"Goux, J., Kulkarni, S., Linderoth, J., Yoder, M.: Master-worker: An enabling framework for applications on the computational grids. In: Proceedings of the 9th IEEE Symposium on High Performance Distributed Computing, pp. 43\u201350 (2000)","DOI":"10.1109\/HPDC.2000.868633"},{"key":"8_CR9","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1287\/moor.22.3.513","volume":"22","author":"L. Hall","year":"1997","unstructured":"Hall, L., Schulz, A., Shmoys, D., Wein, J.: Scheduling to minimize average completion time: offline and online algorithms. Mathematics of Operations Research\u00a022, 513\u2013549 (1997)","journal-title":"Mathematics of Operations Research"},{"key":"8_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/3-540-69346-7_27","volume-title":"Integer Programming and Combinatorial Optimization","author":"H. Hoogeveen","year":"1998","unstructured":"Hoogeveen, H., Schuurman, P., Woeginger, G.: Non-approximability results for scheduling problems with minsum criteria. In: Bixby, R.E., Boyd, E.A., R\u00edos-Mercado, R.Z. (eds.) Integer Programming and Combinatorial Optimization. LNCS, vol.\u00a01412, pp. 353\u2013362. Springer, Heidelberg (1998)"},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Leung, J., Li, H., Pindeo, M.: Multidisciplinery scheduling: Theory and Applications. chapter Order Scheduling Models: an overview, 37\u201356 (2005)","DOI":"10.1007\/0-387-27744-7_3"},{"key":"8_CR12","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1023\/A:1021858008222","volume":"24","author":"J. Linderoth","year":"2003","unstructured":"Linderoth, J., Wright, S.: Decomposition algorithms for stochastic programming on a computational grid. Computational Optimization and Applications\u00a024, 207\u2013250 (2003)","journal-title":"Computational Optimization and Applications"},{"key":"8_CR13","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C., Yannakakis, M.: Optimization, approximation, and complexity classes. Journal of Computer and System Sciences\u00a043, 425\u2013440 (1991)","journal-title":"Journal of Computer and System Sciences"},{"key":"8_CR14","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF01581271","volume":"58","author":"M. Queyranne","year":"1993","unstructured":"Queyranne, M.: Structure of a simple scheduling polyhedron. Mathematical Programming\u00a058, 263\u2013285 (1993)","journal-title":"Mathematical Programming"},{"key":"8_CR15","unstructured":"Queyranne, M., Svirdenko, M.: New and improved algorithms for minsum shop scheduling. In: Symposium on Discrete Algorithms, pp. 871\u2013878 (2000)"},{"key":"8_CR16","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: ACM Symposium on Theory of Computing (STOC), pp. 475\u2013484 (1997)","DOI":"10.1145\/258533.258641"},{"key":"8_CR17","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/s10951-006-7042-y","volume":"9","author":"T. Roemer","year":"2006","unstructured":"Roemer, T.: A note on the complexity of the concurrent open shop problem. Journal of scheduling\u00a09, 389\u2013396 (2006)","journal-title":"Journal of scheduling"},{"key":"8_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/3-540-61310-2_23","volume-title":"Integer Programming and Combinatorial Optimization","author":"A. Schulz","year":"1996","unstructured":"Schulz, A.: Scheduling to minimize total weighted completion time: Performance guarantees of lp-based heuristics and lower bounds. In: Cunningham, W.H., Queyranne, M., McCormick, S.T. (eds.) Integer Programming and Combinatorial Optimization. LNCS, vol.\u00a01084, pp. 301\u2013315. Springer, Heidelberg (1996)"},{"key":"8_CR19","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1016\/0377-2217(93)90347-P","volume":"71","author":"E. Wagneur","year":"1993","unstructured":"Wagneur, E., Sriskandarajah, C.: Open shops with jobs overlap. European Journal of Operations Research\u00a071, 366\u2013378 (1993)","journal-title":"European Journal of Operations Research"},{"key":"8_CR20","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1016\/j.omega.2005.09.007","volume":"35","author":"G. Wang","year":"2007","unstructured":"Wang, G., Cheng, T.: Customer order scheduling to minimize total weighted completion time. Omega\u00a035, 623\u2013626 (2007)","journal-title":"Omega"}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77050-3_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:56:00Z","timestamp":1619520960000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77050-3_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540770497","9783540770503"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77050-3_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}