{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T17:00:01Z","timestamp":1776790801571,"version":"3.51.2"},"reference-count":84,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[2003,9,1]],"date-time":"2003-09-01T00:00:00Z","timestamp":1062374400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["European Journal of Operational Research"],"published-print":{"date-parts":[[2003,9]]},"DOI":"10.1016\/s0377-2217(02)00767-1","type":"journal-article","created":{"date-parts":[[2003,5,19]],"date-time":"2003-05-19T17:32:55Z","timestamp":1053365575000},"page":"355-376","source":"Crossref","is-referenced-by-count":19,"title":["Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity"],"prefix":"10.1016","volume":"149","author":[{"given":"Vadim G.","family":"Timkovsky","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0377-2217(02)00767-1_BIB1","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/0305-0548(84)90016-9","article-title":"Openshop and flowshop scheduling problems to minimize sum of completion times","volume":"11","author":"Adiri","year":"1984","journal-title":"Computers & Operations Research"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB2","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0166-218X(99)00238-3","article-title":"Scheduling equal-length jobs on identical parallel machines","volume":"103","author":"Baptiste","year":"2000","journal-title":"Discrete Applied Mathematics"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB3","doi-asserted-by":"crossref","unstructured":"P. Baptiste, On minimizing the weighted number of late jobs in unit execution time open-shops, European Journal of Operational Research, this issue","DOI":"10.1016\/S0377-2217(02)00759-2"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB4","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/S0167-6377(01)00068-2","article-title":"On preemption redundancy in scheduling unit processing time jobs on two parallel machines","volume":"28","author":"Baptiste","year":"2001","journal-title":"Operations Research Letters"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB5","unstructured":"H. Br\u00e4sel, Lateinische Rechtecke und Machinenbelegung, Dissertation B, TU, Magdeburg, 1990"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB6","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0377-2217(94)90335-2","article-title":"A polynomial algorithm for the n|m|O|tij=1,tree|Cmax problem","volume":"72","author":"Br\u00e4sel","year":"1994","journal-title":"European Journal of Operational Research"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB7","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0166-218X(93)E0156-S","article-title":"A polynomial time algorithm for an open shop problem with unit processing times and tree constraints","volume":"59","author":"Br\u00e4sel","year":"1995","journal-title":"Discrete Applied Mathematics"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB8","unstructured":"P. Brucker, private communication"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB9","series-title":"Scheduling Algorithms","author":"Brucker","year":"1998"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB10","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1287\/moor.2.3.275","article-title":"Scheduling equal-length tasks under tree-like precedence constraints to minimize maximum lateness","volume":"2","author":"Brucker","year":"1977","journal-title":"Mathematics of Operations Research"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB11","unstructured":"P. Brucker, J. Hurink, S. Knust, A polynomial algorithm for P|pj=1,rj,outtree|\u2211Cj, Technical Report, University of Osnabrueck, Germany, 2001"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB12","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF01415528","article-title":"Open shop problems with unit time operations","volume":"37","author":"Brucker","year":"1993","journal-title":"ZOR\u2013\u2013Methods and Models of Operations Research"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB13","unstructured":"P. Brucker, S. Knust, Operations research: Complexity results of scheduling problems, http:\/\/www.mathematik.uni-osnabrueck.de\/research\/OR\/class\/"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB14","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/s006070050036","article-title":"Complexity results for single-machine problems with positive finish\u2013start time lags","volume":"63","author":"Brucker","year":"1999","journal-title":"Computing"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB15","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/0377-2217(95)00350-9","article-title":"Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems","volume":"90","author":"Brucker","year":"1996","journal-title":"European Journal of Operational Research"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB16","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1145\/361011.361064","article-title":"Scheduling independent tasks to reduce mean finishing time","volume":"17","author":"Bruno","year":"1974","journal-title":"Communications of the ACM"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB17","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1109\/TC.1980.1675569","article-title":"Deterministic scheduling with pipelined processors","volume":"29","author":"Bruno","year":"1980","journal-title":"IEEE Transactions on Computers C"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB18","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1287\/opre.29.3.511","article-title":"Preemptive scheduling of independent jobs with release and due dates on open, flow and job shops","volume":"29","author":"Cho","year":"1981","journal-title":"Operations Research"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB19","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1007\/BF00288685","article-title":"Optimal scheduling for two-processor systems","volume":"1","author":"Coffman","year":"1972","journal-title":"Acta Informatica"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB20","series-title":"Theory of Scheduling","author":"Conway","year":"1967"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB21","unstructured":"G.I. Davida, D.J. Linton, A new algorithm for scheduling of tree structured tasks, in Proc. Conf. Inform. Sci. and Syst., Baltimore, MD, 1976, pp. 543\u2013548"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB22","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1111\/j.1467-9574.1990.tb01276.x","article-title":"Scheduling identical jobs on uniform parallel machines","volume":"44","author":"Dessouky","year":"1990","journal-title":"Statistica Neerlandica"},{"issue":"3","key":"10.1016\/S0377-2217(02)00767-1_BIB23","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1287\/moor.15.3.483","article-title":"Minimizing total tardiness on one machine is NP-hard","volume":"15","author":"Du","year":"1990","journal-title":"Mathematics of Operations Research"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB24","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1006\/jagm.1993.1002","article-title":"Minimizing mean flow time in two-machine open shops and flow shops","volume":"14","author":"Du","year":"1993","journal-title":"Journal of Algorithms"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB25","first-page":"97","article-title":"Minimizing the number of late jobs with release time constraints","volume":"11","author":"Du","year":"1992","journal-title":"Journal of Combinatorial Mathematics and Combinatorial Computing"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB26","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1016\/0304-3975(90)90100-V","article-title":"Minimizing mean flow time with release time constraint","volume":"75","author":"Du","year":"1990","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB27","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0890-5401(91)90009-Q","article-title":"Scheduling chain-structured tasks to minimize makespan and mean flow time","volume":"92","author":"Du","year":"1991","journal-title":"Information and Computation"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB28","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1137\/0206029","article-title":"Two-processor scheduling with start-times and deadlines","volume":"6","author":"Garey","year":"1977","journal-title":"SIAM Journal on Computing"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB29","series-title":"Computers and Intractability: A Guide to the Theory of NP Completeness","author":"Garey","year":"1979"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB30","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/S0377-2217(96)00249-4","article-title":"A two-machine preemptive openshop scheduling problem: An elementary proof of NP-completeness","volume":"103","author":"Gladky","year":"1997","journal-title":"European Journal of Operational Research"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB31","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1145\/322186.322194","article-title":"A new algorithm for preemptive scheduling of trees","volume":"27","author":"Gonzalez","year":"1980","journal-title":"Journal of the ACM"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB32","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1145\/321978.321985","article-title":"Openshop scheduling to minimize finish time","volume":"23","author":"Gonzalez","year":"1976","journal-title":"Journal of the ACM"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB33","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1287\/opre.26.1.36","article-title":"Flow shop and job shop schedules: Complexity and approximation","volume":"26","author":"Gonzalez","year":"1978","journal-title":"Operations Research"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB34","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1002\/nav.3800210113","article-title":"Some simple scheduling algorithms","volume":"21","author":"Horn","year":"1974","journal-title":"Naval Research Logistics Quarterly"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB35","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1145\/321992.321995","article-title":"A level algorithm for preemptive scheduling","volume":"24","author":"Horvath","year":"1977","journal-title":"Journal of the ACM"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB36","doi-asserted-by":"crossref","first-page":"841","DOI":"10.1287\/opre.9.6.841","article-title":"Parallel sequencing and assembly line problems","volume":"9","author":"Hu","year":"1961","journal-title":"Operations Research"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB37","series-title":"Complexity of Computer Computations","first-page":"85","article-title":"Reducibility among combinatorial problems","author":"Karp","year":"1972"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB38","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/S0377-2217(97)00102-1","article-title":"A polynomial time algorithm for a two-machine no-wait job-shop scheduling problem","volume":"106","author":"Kravchenko","year":"1998","journal-title":"European Journal of Operational Research"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB39","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/S0166-218X(99)00202-4","article-title":"On the complexity of minimizing the number of late jobs in unit-time open shop","volume":"100","author":"Kravchenko","year":"1999","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"10.1016\/S0377-2217(02)00767-1_BIB40","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/S0166-218X(99)00165-1","article-title":"Minimizing the number of late jobs for the two-machine unit-time job-shop scheduling problem","volume":"98","author":"Kravchenko","year":"1999","journal-title":"Discrete Applied Mathematics"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB41","first-page":"195","article-title":"Exact and approximate algorithms for scheduling unit time tasks with tree-like precedence constraints","author":"Kubiak","year":"1988","journal-title":"Abstracts EURO IX-TIMS XXVIII Paris"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB42","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0377-2217(89)90225-7","article-title":"A pseudopolynomial algorithm for a two-machine no-wait job shop problem","volume":"43","author":"Kubiak","year":"1989","journal-title":"European Journal of Operational Research"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB43","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/BF02099698","article-title":"An efficient algorithm for a job shop problem","volume":"57","author":"Kubiak","year":"1995","journal-title":"Annals of Operations Research"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB44","first-page":"284","article-title":"A note on the complexity of open shop scheduling problems","volume":"29","author":"Kubiak","year":"1991","journal-title":"INFOR"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB45","doi-asserted-by":"crossref","first-page":"310","DOI":"10.1016\/0377-2217(96)00132-4","article-title":"A polynomial-time algorithm for total completion time minimization in two-machine job-shop with unit-time operations","volume":"94","author":"Kubiak","year":"1996","journal-title":"European Journal of Operational Research"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB46","series-title":"Progress in Combinatorial Optimization","first-page":"245","article-title":"Preemptive scheduling of uniform machines subject to release dates","author":"Labetoulle","year":"1984"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB47","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/S0167-5060(08)70742-8","article-title":"A \u2019pseudopolynomial\u2019 algorithm for sequencing jobs to minimize total tardiness","volume":"1","author":"Lawler","year":"1977","journal-title":"Annals of Discrete Mathematics"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB48","unstructured":"E.L. Lawler, Preemptive scheduling of uniform parallel machines to minimize the weighted number of late jobs, Report BW 105, Centre for Mathematics and Computer Science, Amsterdam, 1979"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB49","series-title":"Deterministic and Stochastic Scheduling","first-page":"101","article-title":"Preemptive scheduling of precedence-constrained jobs on parallel machines","author":"Lawler","year":"1982"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB50","series-title":"Mathematical Programming: The State of the Art, Bonn, 1982","first-page":"202","article-title":"Recent results in theory of machine scheduling","author":"Lawler","year":"1983"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB51","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1145\/322092.322101","article-title":"On preemptive scheduling of unrelated parallel processors by linear programming","volume":"25","author":"Lawler","year":"1978","journal-title":"Journal of the ACM"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB52_1","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1287\/moor.6.1.153","article-title":"Minimizing maximum lateness in a two-machine open shop","volume":"6","author":"Lawler","year":"1981","journal-title":"Mathematics of Operations Research"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB52_2","first-page":"635","volume":"7","year":"1982","journal-title":"Erratum"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB53","first-page":"445","article-title":"Sequencing and scheduling: Algorithms and complexity","volume":"vol. 4","author":"Lawler","year":"1993"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB54","doi-asserted-by":"crossref","first-page":"314","DOI":"10.1287\/opre.37.2.314","article-title":"Preemptive scheduling of two uniform machines to minimize the number of late jobs","volume":"37","author":"Lawler","year":"1989","journal-title":"Operations Research"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB55","unstructured":"J.K. Lenstra, private communication"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB56","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1287\/opre.26.1.22","article-title":"Complexity of scheduling under precedence constraints","volume":"26","author":"Lenstra","year":"1979","journal-title":"Operations Research"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB57","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/S0167-5060(08)70821-5","article-title":"Computational complexity of discrete optimization problems","volume":"1","author":"Lenstra","year":"1979","journal-title":"Annals of Discrete Mathematics"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB58","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/0377-2217(80)90111-3","article-title":"Complexity results for scheduling chains on a single machine","volume":"4","author":"Lenstra","year":"1980","journal-title":"European Journal of Operational Research"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB59","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","article-title":"Complexity of machine scheduling problems","volume":"1","author":"Lenstra","year":"1977","journal-title":"Annals of Discrete Mathematics"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB60","doi-asserted-by":"crossref","first-page":"650","DOI":"10.1137\/0213040","article-title":"On some variance of the bandwidth minimization problem","volume":"13","author":"Leung","year":"1984","journal-title":"SIAM Journal on Computing"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB61","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1287\/ijoc.2.4.346","article-title":"Minimizing total tardiness on a single machine with precedence constraints","volume":"2","author":"Leung","year":"1990","journal-title":"ORSA Journal on Computing"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB62","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0167-6377(85)90035-5","article-title":"On the complexity of preemptive open shop scheduling problems","volume":"4","author":"Liu","year":"1985","journal-title":"Operations Research Letters"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB63","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1287\/opre.36.4.553","article-title":"Scheduling open shops with unit execution times to minimize functions of due dates","volume":"36","author":"Liu","year":"1988","journal-title":"Operations Research"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB64","unstructured":"I. Lushchakova, Two machine open shop scheduling problem with release dates, unit processing times and precedence constraints, in Book of Abstracts, SOR\u201999, Magdeburg, 1999, p. 79"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB65","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1287\/mnsc.16.5.295","article-title":"On sequencing n jobs on one machine to minimize the number of late jobs","volume":"16","author":"Maxwell","year":"1970","journal-title":"Management Science"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB66","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/mnsc.6.1.1","article-title":"Scheduling with deadlines and loss functions","volume":"6","author":"McNaughton","year":"1959","journal-title":"Management Science"},{"issue":"4","key":"10.1016\/S0377-2217(02)00767-1_BIB67","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1023\/A:1009827520712","article-title":"Transversal graphs for partially ordered sets: Sequencing, scheduling and merging problems","volume":"3","author":"Middendorf","year":"1999","journal-title":"Journal of Combinatorial Optimization"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB68","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1287\/opre.30.1.116","article-title":"Linear-time algorithms for scheduling on parallel processors","volume":"30","author":"Monma","year":"1982","journal-title":"Operations Research"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB69","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1287\/mnsc.15.1.102","article-title":"An n job, one machine sequencing algorithm for minimizing the number of late jobs","volume":"15","author":"Moore","year":"1968","journal-title":"Management Science"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB70","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1145\/321574.321586","article-title":"Preemptive scheduling of real time tasks on multiprocessor systems","volume":"17","author":"Muntz","year":"1970","journal-title":"Journal of the ACM"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB71","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/BF00337618","article-title":"Computing the bump number with techniques from two-processor scheduling","volume":"5","author":"Sch\u00e4ffer","year":"1988","journal-title":"Order"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB72","series-title":"Computer and Job-Shop Scheduling Theory","first-page":"51","article-title":"Algorithms for minimal-length schedules","author":"Sethi","year":"1976"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB73","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1137\/0212018","article-title":"Multiprocessor scheduling of unit-time jobs with arbitrary release times and deadlines","volume":"12","author":"Simons","year":"1983","journal-title":"SIAM Journal on Computing"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB74","doi-asserted-by":"crossref","first-page":"690","DOI":"10.1137\/0218048","article-title":"A fast algorithm for multiprocessor scheduling of unit-length jobs","volume":"18","author":"Simons","year":"1989","journal-title":"SIAM Journal on Computing"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB75","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1016\/0377-2217(86)90036-6","article-title":"Some no-wait jobs scheduling problems: Complexity results","volume":"24","author":"Sriskandarajah","year":"1986","journal-title":"European Journal of Operational Research"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB76","series-title":"Scheduling Theory: Multi-Stage Systems","author":"Tanaev","year":"1994"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB77","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/S0167-6377(97)00015-1","article-title":"Minimizing the total completion time in a unit-time open shop with release times","volume":"20","author":"Tautenhahn","year":"1997","journal-title":"Operations Research Letters"},{"issue":"5","key":"10.1016\/S0377-2217(02)00767-1_BIB78","first-page":"46","article-title":"On the complexity of scheduling an arbitrary system","author":"Timkovsky","year":"1985","journal-title":"Soviet Journal of Computer and System Sciences"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB79","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/S0166-218X(96)00106-0","article-title":"A polynomial-time algorithm for the two-machine unit-time release-date job-shop schedule-length problem","volume":"77","author":"Timkovsky","year":"1997","journal-title":"Discrete Applied Mathematics"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB80","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0166-218X(98)00032-8","article-title":"Is a unit-time job shop not easier than identical parallel machines?","volume":"85","author":"Timkovsky","year":"1998","journal-title":"Discrete Applied Mathematics"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB81","unstructured":"V.G. Timkovsky, Scheduling unit-time operation jobs on identical parallel machines and in a flow shop: Complexity and correlation, Technical Report No. 98-03, Department of Computer Science and Systems, McMaster University, Hamilton, Ontario, 1998"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB82","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1016\/S0022-0000(75)80008-0","article-title":"NP-complete scheduling problems","volume":"10","author":"Ullman","year":"1975","journal-title":"Journal of Computer and System Sciences"},{"key":"10.1016\/S0377-2217(02)00767-1_BIB83","series-title":"Computer and Job-Shop Scheduling Theory","first-page":"139","article-title":"Complexity of sequencing problems","author":"Ullman","year":"1976"}],"container-title":["European Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0377221702007671?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0377221702007671?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,3,30]],"date-time":"2019-03-30T02:30:14Z","timestamp":1553913014000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0377221702007671"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,9]]},"references-count":84,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2003,9]]}},"alternative-id":["S0377221702007671"],"URL":"https:\/\/doi.org\/10.1016\/s0377-2217(02)00767-1","relation":{},"ISSN":["0377-2217"],"issn-type":[{"value":"0377-2217","type":"print"}],"subject":[],"published":{"date-parts":[[2003,9]]}}}