{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,22]],"date-time":"2026-02-22T10:54:06Z","timestamp":1771757646643,"version":"3.50.1"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2011,3,24]],"date-time":"2011-03-24T00:00:00Z","timestamp":1300924800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2011,10]]},"DOI":"10.1007\/s10951-011-0231-3","type":"journal-article","created":{"date-parts":[[2011,3,23]],"date-time":"2011-03-23T16:41:29Z","timestamp":1300898489000},"page":"435-444","source":"Crossref","is-referenced-by-count":54,"title":["Parallel machine problems with equal processing times: a survey"],"prefix":"10.1007","volume":"14","author":[{"given":"Svetlana A.","family":"Kravchenko","sequence":"first","affiliation":[]},{"given":"Frank","family":"Werner","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,3,24]]},"reference":[{"issue":"6","key":"231_CR1","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1002\/(SICI)1099-1425(199911\/12)2:6<245::AID-JOS28>3.0.CO;2-5","volume":"2","author":"P. Baptiste","year":"1999","unstructured":"Baptiste,\u00a0P. (1999). Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times. Journal of Scheduling, 2(6), 245\u2013252.","journal-title":"Journal of Scheduling"},{"key":"231_CR2","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0166-218X(99)00238-3","volume":"103","author":"P. Baptiste","year":"2000","unstructured":"Baptiste,\u00a0P. (2000). Scheduling equal-length jobs on identical parallel machines. Discrete Applied Mathematics, 103, 21\u201332.","journal-title":"Discrete Applied Mathematics"},{"key":"231_CR3","first-page":"78","volume-title":"Handbook of scheduling: algorithms, models, and performance analysis","author":"P. Baptiste","year":"2004","unstructured":"Baptiste,\u00a0P., & Brucker,\u00a0P. (2004). Scheduling equal processing time jobs: a survey. In Y. T. Leung (Ed.), Handbook of scheduling: algorithms, models, and performance analysis (pp. 78\u201396). Boca Raton: CRC Press."},{"key":"231_CR4","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/s10288-003-0024-4","volume":"2","author":"P. Baptiste","year":"2004","unstructured":"Baptiste,\u00a0P., Brucker,\u00a0P., Knust,\u00a0S., & Timkovsky, V. G. (2004a). Ten notes on equal-processing-time scheduling. 4OR, 2, 111\u2013127.","journal-title":"4OR"},{"key":"231_CR5","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1016\/j.orl.2003.09.004","volume":"32","author":"P. Baptiste","year":"2004","unstructured":"Baptiste,\u00a0P., Chrobak,\u00a0M., D\u00fcrr,\u00a0C., Jawor,\u00a0W., & Vakhania,\u00a0N. (2004b). Preemptive scheduling of equal-length jobs to maximize weighted throughput. Operations Research Letters, 32, 258\u2013264.","journal-title":"Operations Research Letters"},{"key":"231_CR6","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/s10951-006-0006-4","volume":"10","author":"P. Baptiste","year":"2007","unstructured":"Baptiste,\u00a0P., Brucker,\u00a0P., Chrobak,\u00a0M., D\u00fcrr,\u00a0C., Kravchenko, S. A., & Sourd,\u00a0F. (2007). The complexity of mean flow time scheduling problems with release times. Journal of Scheduling, 10, 139\u2013146.","journal-title":"Journal of Scheduling"},{"key":"231_CR7","unstructured":"Brucker,\u00a0P., & Knust,\u00a0S. (2010). Complexity results for scheduling problems. http:\/\/www.mathematik.uni-osnabrueck.de\/research\/OR\/class\/ ."},{"key":"231_CR8","unstructured":"Brucker,\u00a0P., & Kravchenko, S. A. (2005). Scheduling jobs with release times on parallel machines to minimize total tardiness (Preprint Heft 258). Universit\u00e4t Osnabr\u00fcck, 13\u00a0pp."},{"issue":"2","key":"231_CR9","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/s10852-005-9011-4","volume":"5","author":"P. Brucker","year":"2006","unstructured":"Brucker,\u00a0P., & Kravchenko, S. A. (2006). Scheduling equal processing time jobs to minimize the weighted number of late jobs. Journal of Mathematical Modelling and Algorithms, 5(2), 143\u2013165.","journal-title":"Journal of Mathematical Modelling and Algorithms"},{"key":"231_CR10","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/s10951-008-0063-y","volume":"11","author":"P. Brucker","year":"2008","unstructured":"Brucker,\u00a0P., & Kravchenko, S. A. (2008). Scheduling jobs with equal processing times and time windows on identical parallel machines. Journal of Scheduling, 11, 229\u2013237.","journal-title":"Journal of Scheduling"},{"key":"231_CR11","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1287\/moor.2.3.275","volume":"2","author":"P. Brucker","year":"1977","unstructured":"Brucker,\u00a0P., Garey, M. R., & Johnson, D. S. (1977). Scheduling equal-length tasks under tree-like precedence constraints to minimize maximum lateness. Mathematics of Operations Research, 2, 275\u2013284.","journal-title":"Mathematics of Operations Research"},{"key":"231_CR12","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/j.ejor.2010.10.033","volume":"210","author":"K. Chakhlevitch","year":"2011","unstructured":"Chakhlevitch,\u00a0K., Glass, C. A., & Kellerer,\u00a0H. (2011). Batch machine production with perishability time windows and limited batch size. European Journal of Operational Research, 210, 39\u201347.","journal-title":"European Journal of Operational Research"},{"key":"231_CR13","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/s10951-006-5595-4","volume":"9","author":"M. Chrobak","year":"2006","unstructured":"Chrobak,\u00a0M., D\u00fcrr,\u00a0C., Jawor,\u00a0W., Kowalik,\u00a0\u0141., & Kurowski,\u00a0M. (2006). A note on scheduling equal-length jobs to maximize throughput. Journal of Scheduling, 9, 71\u201373.","journal-title":"Journal of Scheduling"},{"key":"231_CR14","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1111\/j.1467-9574.1990.tb01276.x","volume":"44","author":"M. I. Dessouky","year":"1990","unstructured":"Dessouky, M. I., Lageweg, B. J., Lenstra, J. K., & van\u00a0de Velde, S. L. (1990). Scheduling identical jobs on uniform parallel machines. Statistica Neerlandica, 44, 115\u2013123.","journal-title":"Statistica Neerlandica"},{"key":"231_CR15","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/978-3-540-75520-3_39","volume":"4698","author":"J. Ding","year":"2007","unstructured":"Ding,\u00a0J., Ebenlendr,\u00a0T., Sgall,\u00a0J., & Zhang,\u00a0G. (2007). Online-scheduling of equal-length jobs on parallel machines. Lecture Notes in Computer Science, 4698, 427\u2013438.","journal-title":"Lecture Notes in Computer Science"},{"key":"231_CR16","unstructured":"D\u00fcrr,\u00a0C. (2010). The scheduling zoo. http:\/\/www.lix.polytechnique.fr\/~durr\/query\/ ."},{"key":"231_CR17","first-page":"315","volume-title":"Proc. of the 14th annual European symposium on algorithms (ESA)","author":"C. D\u00fcrr","year":"2006","unstructured":"D\u00fcrr,\u00a0C., & Hurrand,\u00a0M. (2006). Finding total unimodularity in optimization problems solved by linear programs. In Proc. of the 14th annual European symposium on algorithms (ESA) (pp. 315\u2013326)."},{"key":"231_CR18","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/BF00288935","volume":"4","author":"G. Fayolle","year":"1974","unstructured":"Fayolle,\u00a0G., Gelenbe,\u00a0E., Labetoulle,\u00a0J., & Bastin,\u00a0D. (1974). The stability problem of broadcast packet switching computer networks. Acta Informatica, 4, 49\u201353.","journal-title":"Acta Informatica"},{"key":"231_CR19","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1137\/0117070","volume":"17","author":"M. Fujii","year":"1969","unstructured":"Fujii,\u00a0M., Kasami,\u00a0T., & Ninomiya,\u00a0K. (1969). Optimal sequencing of two equivalent processors. SIAM Journal on Applied Mathematics, 17, 234\u2013248.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"231_CR20","first-page":"256","volume":"10","author":"M. R. Garey","year":"1981","unstructured":"Garey, M. R., Johnson, D. S., Simons, B. B., & Tarjan, R. E. (1981). Scheduling unit-time tasks with arbitrary release times and deadlines. Journal of Computers, 10, 256\u2013269.","journal-title":"Journal of Computers"},{"key":"231_CR21","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1016\/j.cor.2004.07.010","volume":"33","author":"C. A. Glass","year":"2006","unstructured":"Glass, C. A., & Mills, H. R. (2006). Scheduling unit length jobs with parallel nested machine processing set restrictions. Computers & Operations Research, 33, 620\u2013638.","journal-title":"Computers & Operations Research"},{"key":"231_CR22","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/j.tcs.2008.03.026","volume":"401","author":"Y. Huo","year":"2008","unstructured":"Huo,\u00a0Y., Leung, J. Y.-T., & Wang,\u00a0X. (2008). Online scheduling of equal-processing-time task systems. Theoretical Computer Science, 401, 85\u201395.","journal-title":"Theoretical Computer Science"},{"key":"231_CR23","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/S0166-218X(99)00202-4","volume":"100","author":"S. A. Kravchenko","year":"2000","unstructured":"Kravchenko, S. A. (2000). On the complexity of minimizing the number of late jobs in unit time open shop. Discrete Applied Mathematics, 100, 127\u2013132.","journal-title":"Discrete Applied Mathematics"},{"key":"231_CR24","unstructured":"Kravchenko, S. A., & Werner,\u00a0F. (2007). On a parallel machine scheduling problem with equal processing times (Preprint 26\/07). Otto-von-Guericke-Universit\u00e4t Magdeburg, FMA, 9\u00a0pp."},{"key":"231_CR25","unstructured":"Kravchenko, S. A., & Werner,\u00a0F. (2009a). Minimizing a separable convex function on parallel machines with preemptions (Preprint 22\/09). Otto-von-Guericke-Universit\u00e4t Magdeburg, FMA, 20\u00a0pp."},{"key":"231_CR26","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1016\/j.ejor.2008.10.008","volume":"199","author":"S. A. Kravchenko","year":"2009","unstructured":"Kravchenko, S. A., & Werner,\u00a0F. (2009b). Minimizing the number of machines for scheduling jobs with equal processing times. European Journal of Operational Research, 199, 595\u2013600.","journal-title":"European Journal of Operational Research"},{"key":"231_CR27","doi-asserted-by":"crossref","first-page":"848","DOI":"10.1016\/j.dam.2008.09.003","volume":"157","author":"S. A. Kravchenko","year":"2009","unstructured":"Kravchenko, S. A., & Werner,\u00a0F. (2009c). On a parallel machine scheduling problem with equal processing times. Discrete Applied Mathematics, 157, 848\u2013852.","journal-title":"Discrete Applied Mathematics"},{"issue":"10","key":"231_CR28","doi-asserted-by":"crossref","first-page":"2816","DOI":"10.1016\/j.cor.2008.12.010","volume":"36","author":"S. A. Kravchenko","year":"2009","unstructured":"Kravchenko, S. A., & Werner,\u00a0F. (2009d). Preemptive scheduling on uniform machines to minimize mean flow time. Computers & Operations Research, 36(10), 2816\u20132821.","journal-title":"Computers & Operations Research"},{"key":"231_CR29","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/B978-0-12-566780-7.50020-9","volume-title":"Progress in combinatorial optimization","author":"J. Labetuolle","year":"1984","unstructured":"Labetuolle,\u00a0J., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1984). Preemptive scheduling of uniform machines subject to release dates. In H. R. Pulleyblank (Ed.), Progress in combinatorial optimization (pp. 245\u2013261). New York: Academic Press."},{"key":"231_CR30","first-page":"202","volume-title":"Mathematical programming: the state of the art","author":"E. L. Lawler","year":"1982","unstructured":"Lawler, E. L. (1982). Recent results in the theory of machine scheduling. In A. Bachem (Ed.), Mathematical programming: the state of the art (pp. 202\u2013234). Berlin: Springer."},{"issue":"2","key":"231_CR31","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/0895-7177(94)90209-7","volume":"20","author":"E. L. Lawler","year":"1994","unstructured":"Lawler, E. L. (1994). Knapsack-like scheduling problems, the Moore\u2013Hodgson algorithm and the \u2018tower of set\u2019 property. Mathematical and Computer Modelling, 20(2), 91\u2013106.","journal-title":"Mathematical and Computer Modelling"},{"issue":"4","key":"231_CR32","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1145\/322092.322101","volume":"25","author":"E. L. Lawler","year":"1978","unstructured":"Lawler, E. L., & Labetoulle,\u00a0J. (1978). On preemptive scheduling of unrelated parallel processors by linear programming. Journal of the Association for Computing Machinery, 25(4), 612\u2013619.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"231_CR33","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1287\/opre.26.1.22","volume":"26","author":"J. K. Lenstra","year":"1978","unstructured":"Lenstra, J. K., & Rinnooy Kan, A. H. G. (1978). Complexity of scheduling under precedence constraints. Operations Research, 26, 22\u201335.","journal-title":"Operations Research"},{"key":"231_CR34","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","volume":"1","author":"J. K. Lenstra","year":"1977","unstructured":"Lenstra, J. K., Rinnooy Kan, A. G. H., & Brucker,\u00a0P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 343\u2013362.","journal-title":"Annals of Discrete Mathematics"},{"key":"231_CR35","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0020-0190(90)90229-Q","volume":"34","author":"J. Y.-T. Leung","year":"1990","unstructured":"Leung, J. Y.-T., & Young, G. H. (1990). Preemptive scheduling to minimize mean weighted flow time. Information Processing Letters, 34, 47\u201350.","journal-title":"Information Processing Letters"},{"key":"231_CR36","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1016\/j.cor.2007.07.007","volume":"36","author":"L. L. Liu","year":"2009","unstructured":"Liu, L. L., Ng, C. T., & Cheng, T. C. E. (2009). Bicriterion scheduling with equal processing times on a batch processing machine. Computers & Operations Research, 36, 110\u2013118.","journal-title":"Computers & Operations Research"},{"key":"231_CR37","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1016\/j.ejor.2004.04.009","volume":"165","author":"S. V. Sevastianov","year":"2005","unstructured":"Sevastianov, S. V. (2005). An introduction to multi-parameter complexity analysis of discrete problems. European Journal of Operational Research, 165, 387\u2013397.","journal-title":"European Journal of Operational Research"},{"key":"231_CR38","first-page":"246","volume-title":"Proc. IEEE 19th annual symposium on foundations of computer science (FOCS\u201978)","author":"B. Simons","year":"1978","unstructured":"Simons,\u00a0B. (1978). A fast algorithm for single processor scheduling. In Proc. IEEE 19th annual symposium on foundations of computer science (FOCS\u201978) (pp. 246\u2013252)."},{"key":"231_CR39","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1137\/0212018","volume":"12","author":"B. Simons","year":"1983","unstructured":"Simons,\u00a0B. (1983). Multiprocessor scheduling of unit-time jobs with arbitrary release times and deadlines. SIAM Journal on Computing, 12, 7\u20139.","journal-title":"SIAM Journal on Computing"},{"key":"231_CR40","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1287\/opre.32.1.80","volume":"32","author":"B. B. Simons","year":"1984","unstructured":"Simons, B. B., & Sipser,\u00a0M. (1984). On scheduling unit-length jobs with multiple release time\/deadline intervals. Operations Research, 32, 80\u201388.","journal-title":"Operations Research"},{"key":"231_CR41","doi-asserted-by":"crossref","first-page":"690","DOI":"10.1137\/0218048","volume":"18","author":"B. B. Simons","year":"1989","unstructured":"Simons, B. B., & Warmuth, M. K. (1989). A fast algorithm for multiprocessor scheduling of unit-length jobs. SIAM Journal on Computing, 18, 690\u2013710.","journal-title":"SIAM Journal on Computing"},{"key":"231_CR42","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/s10951-006-7039-6","volume":"9","author":"Z. Tian","year":"2006","unstructured":"Tian,\u00a0Z., Ng, C. T., & Cheng, T. C. E. (2006). An O(n 2) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness. Journal of Scheduling, 9, 343\u2013364.","journal-title":"Journal of Scheduling"},{"key":"231_CR43","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1016\/S0022-0000(75)80008-0","volume":"10","author":"J. D. Ullman","year":"1975","unstructured":"Ullman, J. D. (1975). NP-complete scheduling problems. Journal of Computer and System Sciences, 10, 384\u2013393.","journal-title":"Journal of Computer and System Sciences"},{"key":"231_CR44","volume-title":"Computer and job\/shop scheduling theory","author":"J. D. Ullman","year":"1976","unstructured":"Ullman, J. D. (1976). Complexity of sequencing problems. In J. L. Bruno, E. G. Coffman Jr., R. L. Graham, W. H. Kohler, R. Sethi, K. Steiglitz, & J. D. Ullman (Eds.), Computer and job\/shop scheduling theory. New York: Wiley."},{"key":"231_CR45","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/S0196-6774(03)00072-5","volume":"48","author":"N. Vakhania","year":"2003","unstructured":"Vakhania,\u00a0N. (2003). A better algorithm for sequencing with release and delivery times on identical machines. Journal of Algorithms, 48, 273\u2013293.","journal-title":"Journal of Algorithms"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-011-0231-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-011-0231-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-011-0231-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,2]],"date-time":"2019-06-02T09:39:46Z","timestamp":1559468386000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-011-0231-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3,24]]},"references-count":45,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2011,10]]}},"alternative-id":["231"],"URL":"https:\/\/doi.org\/10.1007\/s10951-011-0231-3","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,3,24]]}}}