{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T10:27:26Z","timestamp":1770460046794,"version":"3.49.0"},"reference-count":71,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,5,8]],"date-time":"2017-05-08T00:00:00Z","timestamp":1494201600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2018,2]]},"DOI":"10.1007\/s10951-017-0519-z","type":"journal-article","created":{"date-parts":[[2017,5,8]],"date-time":"2017-05-08T14:37:50Z","timestamp":1494254270000},"page":"3-16","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":29,"title":["A survey on how the structure of precedence constraints may change the complexity class of scheduling problems"],"prefix":"10.1007","volume":"21","author":[{"given":"D.","family":"Prot","sequence":"first","affiliation":[]},{"given":"O.","family":"Bellenguez-Morineau","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,8]]},"reference":[{"issue":"5","key":"519_CR1","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1007\/s10951-006-8499-4","volume":"9","author":"I Aho","year":"2006","unstructured":"Aho, I., & M\u00e4kinen, E. (2006). On a parallel machine scheduling problem with precedence constraints. Journal of Scheduling, 9(5), 493\u2013495.","journal-title":"Journal of Scheduling"},{"issue":"4","key":"519_CR2","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1007\/s00453-008-9251-6","volume":"53","author":"C Amb\u00fchl","year":"2009","unstructured":"Amb\u00fchl, C., & Mastrolilli, M. (2009). Single machine precedence constrained scheduling is a vertex cover problem. Algorithmica, 53(4), 488\u2013503.","journal-title":"Algorithmica"},{"issue":"4","key":"519_CR3","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1287\/moor.1110.0512","volume":"36","author":"C Amb\u00fchl","year":"2011","unstructured":"Amb\u00fchl, C., Mastrolilli, M., Mutsanas, N., & Svensson, O. (2011). On the approximability of single-machine scheduling with precedence constraints. Mathematics of Operations Research, 36(4), 653\u2013669.","journal-title":"Mathematics of Operations Research"},{"key":"519_CR4","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, P. (1999). Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times. Journal of Scheduling, 2, 245\u2013252.","journal-title":"Journal of Scheduling"},{"key":"519_CR5","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/s10288-003-0024-4","volume":"2","author":"P Baptiste","year":"2004","unstructured":"Baptiste, P., Brucker, P., Knust, S., & Timkovsky, V. G. (2004a). Ten notes on equal-execution-time scheduling. 4OR, 2, 111\u2013127.","journal-title":"4OR"},{"issue":"3","key":"519_CR6","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1016\/j.orl.2003.09.004","volume":"32","author":"P Baptiste","year":"2004","unstructured":"Baptiste, P., Chrobak, M., D\u00fcrr, C., Jawor, W., & Vakhania, N. (2004b). Preemptive scheduling of equal-length jobs to maximize weighted throughput. Operations Research Letters, 32(3), 258\u2013264.","journal-title":"Operations Research Letters"},{"issue":"5","key":"519_CR7","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/S0167-6377(01)00068-2","volume":"28","author":"P Baptiste","year":"2001","unstructured":"Baptiste, P., & Timkovsky, V. G. (2001). On preemption redundancy in scheduling unit processing time jobs on two parallel machines. Operations Research Letters, 28(5), 205\u2013212.","journal-title":"Operations Research Letters"},{"issue":"1","key":"519_CR8","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/s001860300336","volume":"60","author":"P Baptiste","year":"2004","unstructured":"Baptiste, P., & Timkovsky, V. G. (2004). Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time. Mathematical Methods of Operations Research, 60(1), 145\u2013153.","journal-title":"Mathematical Methods of Operations Research"},{"issue":"2","key":"519_CR9","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/BF00814406","volume":"9","author":"GR Brightwell","year":"1992","unstructured":"Brightwell, G. R., & Scheinerman, E. R. (1992). Fractional dimension of partial orders. Order, 9(2), 139\u2013158.","journal-title":"Order"},{"key":"519_CR10","unstructured":"Brucker, P., & Knust, S. (2009). Complexity results for scheduling problems. http:\/\/www2.informatik.uni-osnabrueck.de\/knust\/class\/ ."},{"key":"519_CR11","volume-title":"Scheduling algorithms","author":"P Brucker","year":"2007","unstructured":"Brucker, P. (2007). Scheduling algorithms. New York: Springer."},{"issue":"3","key":"519_CR12","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1287\/moor.2.3.275","volume":"2","author":"P Brucker","year":"1977","unstructured":"Brucker, P., Garey, M. R., & Johnson, D. S. (1977). Scheduling equal-length tasks under treelike precedence constraints to minimize maximum lateness. Mathematics of Operations Research, 2(3), 275\u2013284.","journal-title":"Mathematics of Operations Research"},{"issue":"3","key":"519_CR13","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1007\/s001860200228","volume":"56","author":"P Brucker","year":"2002","unstructured":"Brucker, P., Hurink, J., & Knust, S. (2002). A polynomial algorithm for p| pj= 1, rj, outtree\u2013cj. Mathematical Methods of Operations Research, 56(3), 407\u2013412.","journal-title":"Mathematical Methods of Operations Research"},{"issue":"2","key":"519_CR14","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/PL00020913","volume":"49","author":"P Brucker","year":"1999","unstructured":"Brucker, P., Hurink, J., & Kubiak, W. (1999). Scheduling identical jobs with chain precedence constraints on two uniform machines. Mathematical Methods of Operations Research, 49(2), 211\u2013219.","journal-title":"Mathematical Methods of Operations Research"},{"issue":"1","key":"519_CR15","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1137\/S0895480101394999","volume":"19","author":"M Chardon","year":"2005","unstructured":"Chardon, M., & Moukrim, A. (2005). The Coffman\u2013Graham algorithm optimally solves uet task systems with overinterval orders. SIAM Journal on Discrete Mathematics, 19(1), 109\u2013121.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"519_CR16","doi-asserted-by":"publisher","unstructured":"Chen, B., Coffman, E., Dereniowski, D., & Kubiak, W. (2015). Normal-form preemption sequences for an open problem in scheduling theory. Journal of Scheduling. doi: 10.1007\/s10951-015-0446-9 .","DOI":"10.1007\/s10951-015-0446-9"},{"issue":"1","key":"519_CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00236-011-0146-7","volume":"49","author":"EG Coffman Jr","year":"2012","unstructured":"Coffman, E. G, Jr., Dereniowski, D., & Kubiak, W. (2012). An efficient algorithm for finding ideal schedules. Acta Informatica, 49(1), 1\u201314.","journal-title":"Acta Informatica"},{"issue":"3","key":"519_CR18","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1007\/BF00288685","volume":"1","author":"EG Coffman Jr","year":"1972","unstructured":"Coffman, E. G, Jr., & Graham, R. L. (1972). Optimal scheduling for two-processor systems. Acta Informatica, 1(3), 200\u2013213.","journal-title":"Acta Informatica"},{"issue":"8","key":"519_CR19","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/s00236-003-0119-6","volume":"39","author":"EG Coffman","year":"2003","unstructured":"Coffman, E. G., Sethuraman, J., & Timkovsky, V. G. (2003). Ideal preemptive schedules on two processors. Acta Informatica, 39(8), 597\u2013612. doi: 10.1007\/s00236-003-0119-6 .","journal-title":"Acta Informatica"},{"issue":"4","key":"519_CR20","doi-asserted-by":"crossref","first-page":"1005","DOI":"10.1287\/moor.1050.0158","volume":"30","author":"JR Correa","year":"2005","unstructured":"Correa, J. R., & Schulz, A. S. (2005). Single-machine scheduling with precedence constraints. Mathematics of Operations Research, 30(4), 1005\u20131021.","journal-title":"Mathematics of Operations Research"},{"issue":"1","key":"519_CR21","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B. (1990). The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and Computation, 85(1), 12\u201375.","journal-title":"Information and Computation"},{"issue":"3","key":"519_CR22","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1111\/j.1467-9574.1990.tb01276.x","volume":"44","author":"MI Dessouky","year":"1990","unstructured":"Dessouky, M. I., Lageweg, B. J., Lenstra, J. K., & van de Velde, S. L. (1990). Scheduling identical jobs on uniform parallel machines. Statistica Neerlandica, 44(3), 115\u2013123.","journal-title":"Statistica Neerlandica"},{"issue":"2","key":"519_CR23","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/S0377-2217(98)00234-3","volume":"117","author":"K Djellab","year":"1999","unstructured":"Djellab, K. (1999). Scheduling preemptive jobs with precedence constraints on parallel machines. European Journal of Operational Research, 117(2), 355\u2013367.","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"519_CR24","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1016\/0196-6774(84)90039-7","volume":"5","author":"D Dolev","year":"1984","unstructured":"Dolev, D., & Warmuth, M. K. (1984). Scheduling precedence graphs of bounded height. Journal of Algorithms, 5(1), 48\u201359.","journal-title":"Journal of Algorithms"},{"issue":"4","key":"519_CR25","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1137\/0606066","volume":"6","author":"D Dolev","year":"1985","unstructured":"Dolev, D., & Warmuth, M. K. (1985). Profile scheduling of opposing forests and level orders. SIAM Journal on Algebraic Discrete Methods, 6(4), 665\u2013687.","journal-title":"SIAM Journal on Algebraic Discrete Methods"},{"key":"519_CR26","volume-title":"Parameterized complexity","author":"RG Downey","year":"2012","unstructured":"Downey, R. G., & Fellows, M. R. (2012). Parameterized complexity. New York: Springer."},{"key":"519_CR27","unstructured":"D\u00fcrr, C. (2016). The scheduling zoo. http:\/\/schedulingzoo.lip6.fr ."},{"issue":"2","key":"519_CR28","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/S0304-3975(02)00811-3","volume":"298","author":"MR Fellows","year":"2003","unstructured":"Fellows, M. R., & McCartin, C. (2003). On the parametric complexity of schedules to minimize tardy tasks. Theoretical Computer Science, 298(2), 317\u2013324.","journal-title":"Theoretical Computer Science"},{"key":"519_CR29","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/j.dam.2013.10.038","volume":"168","author":"R Ganian","year":"2014","unstructured":"Ganian, R., Hlin\u011bn\u1ef3, P., Kneis, J., Langer, A., Obdr\u017e\u00e1lek, J., & Rossmanith, P. (2014). Digraph width measures in parameterized algorithmics. Discrete Applied Mathematics, 168, 88\u2013107.","journal-title":"Discrete Applied Mathematics"},{"key":"519_CR30","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. (1979). Computers and intractability: a guide to the theory of NP-completeness. New York: WH Freeman."},{"issue":"1","key":"519_CR31","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1137\/0604011","volume":"4","author":"MR Garey","year":"1983","unstructured":"Garey, M. R., Johnson, D. S., Tarjan, R. E., & Yannakakis, M. (1983). Scheduling opposing forests. SIAM Journal on Algebraic Discrete Methods, 4(1), 72\u201393.","journal-title":"SIAM Journal on Algebraic Discrete Methods"},{"issue":"2","key":"519_CR32","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1145\/322186.322194","volume":"27","author":"TF Gonzalez","year":"1980","unstructured":"Gonzalez, T. F., & Johnson, D. B. (1980). A new algorithm for preemptive scheduling of trees. Journal of the ACM (JACM), 27(2), 287\u2013312.","journal-title":"Journal of the ACM (JACM)"},{"issue":"5","key":"519_CR33","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/s10951-008-0064-x","volume":"11","author":"VS Gordon","year":"2008","unstructured":"Gordon, V. S., Potts, C. N., Strusevich, V. A., & Whitehead, J. D. (2008). Single machine scheduling models with deterioration and learning: Handling precedence constraints via priority generation. Journal of Scheduling, 11(5), 357\u2013370.","journal-title":"Journal of Scheduling"},{"key":"519_CR34","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"RL Graham","year":"1979","unstructured":"Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287\u2013326.","journal-title":"Annals of Discrete Mathematics"},{"issue":"6","key":"519_CR35","doi-asserted-by":"crossref","first-page":"841","DOI":"10.1287\/opre.9.6.841","volume":"9","author":"TC Hu","year":"1961","unstructured":"Hu, T. C. (1961). Parallel sequencing and assembly line problems. Operations Research, 9(6), 841\u2013848.","journal-title":"Operations Research"},{"issue":"2","key":"519_CR36","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/s00186-005-0009-5","volume":"62","author":"Y Huo","year":"2005","unstructured":"Huo, Y., & Leung, J. Y.-T. (2005). Minimizing total completion time for uet tasks with release time and outtree precedence constraints. Mathematical Methods of Operations Research, 62(2), 275\u2013279.","journal-title":"Mathematical Methods of Operations Research"},{"issue":"2","key":"519_CR37","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1145\/1150334.1150340","volume":"2","author":"Y Huo","year":"2006","unstructured":"Huo, Y., & Leung, J. Y.-T. (2006). Minimizing mean flow time for uet tasks. ACM Transactions on Algorithms (TALG), 2(2), 244\u2013262.","journal-title":"ACM Transactions on Algorithms (TALG)"},{"issue":"2","key":"519_CR38","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0890-5401(91)90009-Q","volume":"92","author":"D Jianzhong","year":"1991","unstructured":"Jianzhong, D., Leung, J. Y. T., & Young, G. H. (1991). Scheduling chain-structured tasks to minimize makespan and mean flow time. Information and Computation, 92(2), 219\u2013236.","journal-title":"Information and Computation"},{"issue":"6","key":"519_CR39","first-page":"423","volume":"33","author":"W Kubiak","year":"1989","unstructured":"Kubiak, W. (1989). Optimal scheduling of unit-time tasks on two uniform processors under tree-like precedence constraints. Zeitschrift f\u00fcr Operations Research, 33(6), 423\u2013437.","journal-title":"Zeitschrift f\u00fcr Operations Research"},{"key":"519_CR40","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.disopt.2008.09.001","volume":"6","author":"W Kubiak","year":"2009","unstructured":"Kubiak, W., Rebaine, D., & Potts, C. (2009). Optimality of HLF for scheduling divide-and-conquer UET task graphs on identical parallel processors. Discrete Optimization, 6, 79\u201391.","journal-title":"Discrete Optimization"},{"key":"519_CR41","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/S0167-5060(08)70323-6","volume":"2","author":"EL Lawler","year":"1978","unstructured":"Lawler, E. L. (1978). Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Annals of Discrete Mathematics, 2, 75\u201390.","journal-title":"Annals of Discrete Mathematics"},{"key":"519_CR42","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/978-94-009-7801-0_6","volume-title":"Deterministic and stochastic scheduling, volume 84 of NATO advanced study institutes series","author":"EL Lawler","year":"1982","unstructured":"Lawler, E. L. (1982). Preemptive scheduling of precedence-constrained jobs on parallel machines. In M. A. H. Dempster, J. K. Lenstra, & A. H. G. Rinnooy Kan (Eds.), Deterministic and stochastic scheduling, volume 84 of NATO advanced study institutes series (pp. 101\u2013123). Netherlands: Springer."},{"key":"519_CR43","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1016\/S0927-0507(05)80189-6","volume":"4","author":"EL Lawler","year":"1993","unstructured":"Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D. B. (1993). Sequencing and scheduling. Handbooks in Operations Research and Management Science, 4, 445\u2013522.","journal-title":"Handbooks in Operations Research and Management Science"},{"issue":"1","key":"519_CR44","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1287\/opre.26.1.22","volume":"26","author":"JK Lenstra","year":"1978","unstructured":"Lenstra, J. K., & Rinnooy Kan, A. H. G. (1978). Complexity of scheduling under precedence constraints. Operations Research, 26(1), 22\u201335.","journal-title":"Operations Research"},{"issue":"4","key":"519_CR45","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/0377-2217(80)90111-3","volume":"4","author":"JK Lenstra","year":"1980","unstructured":"Lenstra, J. K., & Rinnooy Kan, A. H. G. (1980). Complexity results for scheduling chains on a single machine. European Journal of Operational Research, 4(4), 270\u2013275.","journal-title":"European Journal of Operational Research"},{"key":"519_CR46","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","volume":"1","author":"JK Lenstra","year":"1977","unstructured":"Lenstra, J. K., Rinnooy Kan, A. H. G., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 343\u2013362.","journal-title":"Annals of Discrete Mathematics"},{"issue":"4","key":"519_CR47","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1287\/ijoc.2.4.346","volume":"2","author":"JY-T Leung","year":"1990","unstructured":"Leung, J. Y.-T., & Young, G. H. (1990). Minimizing total tardiness on a single machine with precedence constraints. ORSA Journal on Computing, 2(4), 346\u2013352.","journal-title":"ORSA Journal on Computing"},{"key":"519_CR48","unstructured":"Levey, E., & Rothvoss, T. (2016) A Lasserre-based $$(1+\\epsilon )$$ ( 1 + \u03f5 ) -approximation for $$Pm | p_j=1,prec | C_{max}$$ P m | p j = 1 , p r e c | C m a x . To appear in STOC\u201916. http:\/\/arxiv.org\/abs\/1509.07808 ."},{"issue":"1","key":"519_CR49","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/j.ejor.2004.08.037","volume":"171","author":"IN Lushchakova","year":"2006","unstructured":"Lushchakova, I. N. (2006). Two machine preemptive scheduling problem with release dates, equal processing times and precedence constraints. European Journal of Operational Research, 171(1), 107\u2013122.","journal-title":"European Journal of Operational Research"},{"issue":"4","key":"519_CR50","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1023\/A:1009827520712","volume":"3","author":"M Middendorf","year":"1999","unstructured":"Middendorf, M., & Timkovsky, V. G. (1999). Transversal graphs for partially ordered sets: Sequencing, merging and scheduling problems. Journal of Combinatorial Optimization, 3(4), 417\u2013435.","journal-title":"Journal of Combinatorial Optimization"},{"key":"519_CR51","doi-asserted-by":"publisher","unstructured":"Mnich, M., & Wiese, A. (2014). Scheduling and fixed-parameter tractability. Mathematical Programming. doi: 10.1007\/s10107-014-0830-9 .","DOI":"10.1007\/s10107-014-0830-9"},{"key":"519_CR52","first-page":"105","volume-title":"Algorithms and order, volume 255 of NATO ASI series","author":"RH M\u00f6hring","year":"1989","unstructured":"M\u00f6hring, R. H. (1989). Computationally tractable classes of ordered sets. In I. Rival (Ed.), Algorithms and order, volume 255 of NATO ASI series (pp. 105\u2013193). Netherlands: Springer."},{"issue":"1","key":"519_CR53","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1287\/opre.30.1.116","volume":"30","author":"CL Monma","year":"1982","unstructured":"Monma, C. L. (1982). Linear-time algorithms for scheduling on parallel processors. Operations Research, 30(1), 116\u2013124.","journal-title":"Operations Research"},{"issue":"3","key":"519_CR54","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1287\/moor.4.3.215","volume":"4","author":"CL Monma","year":"1979","unstructured":"Monma, C. L., & Sidney, J. B. (1979). Sequencing with series-parallel precedence constraints. Mathematics of Operations Research, 4(3), 215\u2013224.","journal-title":"Mathematics of Operations Research"},{"issue":"1","key":"519_CR55","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/S0167-6377(99)00003-6","volume":"24","author":"A Moukrim","year":"1999","unstructured":"Moukrim, A. (1999). Optimal scheduling on parallel machines for a new order class. Operations Research Letters, 24(1), 91\u201395.","journal-title":"Operations Research Letters"},{"issue":"3","key":"519_CR56","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1023\/A:1006025717772","volume":"14","author":"A Moukrim","year":"1997","unstructured":"Moukrim, A., & Quilliot, A. (1997). A relation between multiprocessor scheduling and linear programming. Order, 14(3), 269\u2013278.","journal-title":"Order"},{"issue":"2","key":"519_CR57","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/j.orl.2004.06.002","volume":"33","author":"A Moukrim","year":"2005","unstructured":"Moukrim, A., & Quilliot, A. (2005). Optimal preemptive scheduling on a fixed number of identical parallel machines. Operations Research Letters, 33(2), 143\u2013150.","journal-title":"Operations Research Letters"},{"issue":"2","key":"519_CR58","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1145\/321574.321586","volume":"17","author":"RR Muntz","year":"1970","unstructured":"Muntz, R. R., & Coffman, E. G, Jr. (1970). Preemptive scheduling of real-time tasks on multiprocessor systems. Journal of the ACM (JACM), 17(2), 324\u2013338.","journal-title":"Journal of the ACM (JACM)"},{"issue":"3","key":"519_CR59","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1137\/0208031","volume":"8","author":"CH Papadimitriou","year":"1979","unstructured":"Papadimitriou, C. H., & Yannakakis, M. (1979). Scheduling interval-ordered tasks. SIAM Journal on Computing, 8(3), 405\u2013409.","journal-title":"SIAM Journal on Computing"},{"key":"519_CR60","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4614-2361-4","volume-title":"Scheduling: theory, algorithms, and systems","author":"ML Pinedo","year":"2012","unstructured":"Pinedo, M. L. (2012). Scheduling: theory, algorithms, and systems. New York: Springer."},{"issue":"3","key":"519_CR61","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., & Seymour, P. D. (1986). Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms, 7(3), 309\u2013322.","journal-title":"Journal of Algorithms"},{"issue":"4","key":"519_CR62","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/BF00353653","volume":"5","author":"NW Sauer","year":"1989","unstructured":"Sauer, N. W., & Stone, M. G. (1989). Preemptive scheduling of interval orders is polynomial. Order, 5(4), 345\u2013348.","journal-title":"Order"},{"issue":"2","key":"519_CR63","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1287\/opre.23.2.283","volume":"23","author":"JB Sidney","year":"1975","unstructured":"Sidney, J. B. (1975). Decomposition algorithms for single-machine sequencing with precedence relations and deferral costs. Operations Research, 23(2), 283\u2013298.","journal-title":"Operations Research"},{"issue":"5","key":"519_CR64","doi-asserted-by":"crossref","first-page":"1258","DOI":"10.1137\/100810502","volume":"40","author":"O Svensson","year":"2011","unstructured":"Svensson, O. (2011). Hardness of precedence constrained scheduling on identical machines. SIAM Journal on Computing, 40(5), 1258\u20131274.","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"519_CR65","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/s10951-006-7039-6","volume":"9","author":"Z Tian","year":"2006","unstructured":"Tian, Z., Ng, C. T., & Cheng, T. C. E. (2006). An $${O}(n^2)$$ O ( n 2 ) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness. Journal of Scheduling, 9(4), 343\u2013364.","journal-title":"Journal of Scheduling"},{"issue":"2","key":"519_CR66","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/S0377-2217(02)00767-1","volume":"149","author":"VG Timkovsky","year":"2003","unstructured":"Timkovsky, V. G. (2003). Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity. European Journal of Operational Research, 149(2), 355\u2013376.","journal-title":"European Journal of Operational Research"},{"key":"519_CR67","volume-title":"Computer and job\/shop scheduling theory","author":"JD 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":"519_CR68","unstructured":"Wang, T. (2015) Ordonnancement parall\u00e8le non-pr\u00e9eemptif avec contraintes de pr\u00e9c\u00e9dence. Technical report, Ecole Centrale Nantes. https:\/\/hal.archives-ouvertes.fr\/hal-01202104 ."},{"issue":"8","key":"519_CR69","doi-asserted-by":"crossref","first-page":"2684","DOI":"10.1016\/j.cor.2006.12.026","volume":"35","author":"J-B Wang","year":"2008","unstructured":"Wang, J.-B., Ng, C. T., & Cheng, T. C. E. (2008). Single-machine scheduling with deteriorating jobs under a series\u2013parallel graph constraint. Computers and Operations Research, 35(8), 2684\u20132693.","journal-title":"Computers and Operations Research"},{"issue":"3","key":"519_CR70","doi-asserted-by":"crossref","first-page":"649","DOI":"10.1016\/j.apm.2012.02.055","volume":"37","author":"J-B Wang","year":"2013","unstructured":"Wang, J.-B., & Wang, J.-J. (2013). Single-machine scheduling with precedence constraints and position-dependent processing times. Applied Mathematical Modelling, 37(3), 649\u2013658.","journal-title":"Applied Mathematical Modelling"},{"key":"519_CR71","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511921735","volume-title":"The design of approximation algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson, D. P., & Shmoys, D. B. (2011). The design of approximation algorithms. Cambridge: Cambridge University Press."}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-017-0519-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-017-0519-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-017-0519-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,23]],"date-time":"2023-08-23T13:13:27Z","timestamp":1692796407000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-017-0519-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,8]]},"references-count":71,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["519"],"URL":"https:\/\/doi.org\/10.1007\/s10951-017-0519-z","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,5,8]]}}}