{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T10:41:44Z","timestamp":1648723304754},"reference-count":36,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[2002,11,1]],"date-time":"2002-11-01T00:00:00Z","timestamp":1036108800000},"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":["Journal of Algorithms"],"published-print":{"date-parts":[[2002,11]]},"DOI":"10.1016\/s0196-6774(02)00248-1","type":"journal-article","created":{"date-parts":[[2002,12,10]],"date-time":"2002-12-10T23:17:21Z","timestamp":1039562241000},"page":"167-191","source":"Crossref","is-referenced-by-count":4,"title":["Polynomial time approximation schemes for general multiprocessor job shop scheduling"],"prefix":"10.1016","volume":"45","author":[{"given":"Klaus","family":"Jansen","sequence":"first","affiliation":[]},{"given":"Lorant","family":"Porkolab","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S0196-6774(02)00248-1_BIB001","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/s00453-001-0076-9","article-title":"Scheduling independent multiprocessor tasks","volume":"32","author":"Amoura","year":"2002","journal-title":"Algorithmica"},{"key":"10.1016\/S0196-6774(02)00248-1_BIB002","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1007\/BF02057160","article-title":"Scheduling multiprocessor tasks on a dynamic configuration of dedicated processors","volume":"58","author":"Bianco","year":"1995","journal-title":"Ann. Oper. Res."},{"key":"10.1016\/S0196-6774(02)00248-1_BIB003","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/S0304-3975(00)00260-7","article-title":"On-line scheduling of parallel jobs with runtime restrictions","volume":"268","author":"Bischof","year":"2001","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0196-6774(02)00248-1_BIB004","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/0020-0190(92)90172-R","article-title":"Scheduling multiprocessor tasks on the three dedicated processors","volume":"41","author":"Blazewicz","year":"1992","journal-title":"Inform. Process. Lett."},{"issue":"5","key":"10.1016\/S0196-6774(02)00248-1_BIB005","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1109\/TC.1986.1676781","article-title":"Scheduling multiprocessor tasks to minimize schedule length","volume":"C-35","author":"Blazewicz","year":"1986","journal-title":"IEEE Trans. Comput."},{"key":"10.1016\/S0196-6774(02)00248-1_BIB006","series-title":"Scheduling Algorithms","author":"Brucker","year":"1998"},{"key":"10.1016\/S0196-6774(02)00248-1_BIB007","series-title":"Proceedings of the 8th ACM Symposium on Parallel Algorithms and Architectures","first-page":"329","article-title":"Resource scheduling for parallel database and scientific applications","author":"Chakrabarti","year":"1996"},{"key":"10.1016\/S0196-6774(02)00248-1_BIB008","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1002\/(SICI)1520-6750(199902)46:1<57::AID-NAV4>3.0.CO;2-H","article-title":"General multiprocessor tasks scheduling","volume":"46","author":"Chen","year":"1999","journal-title":"Naval Res. Logist."},{"key":"10.1016\/S0196-6774(02)00248-1_BIB009","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0097539798348110","article-title":"A polynomial time approximation scheme for general multiprocessor job scheduling","volume":"31","author":"Chen","year":"2001","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0196-6774(02)00248-1_BIB010","first-page":"381","article-title":"On the complexity of multiprocessor task scheduling","volume":"43","author":"Drozdowski","year":"1995","journal-title":"Bull. Polish Acad. Sci."},{"key":"10.1016\/S0196-6774(02)00248-1_BIB011","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0377-2217(96)00123-3","article-title":"Scheduling multiprocessor tasks\u2014an overview","volume":"94","author":"Drozdowski","year":"1996","journal-title":"European J. Oper. Res."},{"key":"10.1016\/S0196-6774(02)00248-1_BIB012","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1137\/0402042","article-title":"Complexity of scheduling parallel task systems","volume":"2","author":"Du","year":"1989","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"10.1016\/S0196-6774(02)00248-1_BIB013","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1023\/A:1009794729459","article-title":"Optimal online scheduling of parallel jobs with dependencies","volume":"1","author":"Feldmann","year":"1998","journal-title":"J. Combin. Optim."},{"issue":"1","key":"10.1016\/S0196-6774(02)00248-1_BIB014","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0304-3975(94)90152-X","article-title":"Dynamic scheduling on parallel machines","volume":"130","author":"Feldmann","year":"1994","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0196-6774(02)00248-1_BIB015","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/0097-3165(76)90001-7","article-title":"Resource constrained scheduling as generalized bin packing","volume":"21","author":"Garey","year":"1976","journal-title":"J. Combin. Theory Ser. A"},{"key":"10.1016\/S0196-6774(02)00248-1_BIB016","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1287\/moor.1.2.117","article-title":"The complexity of flowshop and jobshop scheduling","volume":"1","author":"Garey","year":"1976","journal-title":"Math. Oper. Res."},{"key":"10.1016\/S0196-6774(02)00248-1_BIB017","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1137\/S0895480199326104","article-title":"Better approximation guarantees for job-shop scheduling","volume":"14","author":"Goldberg","year":"2001","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/S0196-6774(02)00248-1_BIB018","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1287\/moor.21.2.321","article-title":"Coordination complexity of parallel price-directive decomposition","volume":"21","author":"Grigoriadis","year":"1996","journal-title":"Math. Oper. Res."},{"key":"10.1016\/S0196-6774(02)00248-1_BIB019","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BF01585870","article-title":"Approximability of flow shop scheduling","volume":"82","author":"Hall","year":"1998","journal-title":"Math. Programming"},{"key":"10.1016\/S0196-6774(02)00248-1_BIB020","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/0166-218X(94)90012-4","article-title":"Complexity of scheduling multiprocessor tasks with prespecified processor allocations","volume":"55","author":"Hoogeveen","year":"1994","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0196-6774(02)00248-1_BIB021","series-title":"Proceedings of the 4th Latin American Theoretical Informatics","first-page":"68","article-title":"Approximation algorithms for flexible job shop problems","volume":"1776","author":"Jansen","year":"2000"},{"key":"10.1016\/S0196-6774(02)00248-1_BIB022","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1007\/s00453-001-0085-8","article-title":"Linear-time approximation schemes for scheduling malleable parallel tasks","volume":"32","author":"Jansen","year":"2002","journal-title":"Algorithmica"},{"key":"10.1016\/S0196-6774(02)00248-1_BIB023","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1287\/moor.26.2.324.10559","article-title":"Improved approximation schemes for scheduling unrelated parallel machines","volume":"26","author":"Jansen","year":"2001","journal-title":"Math. Oper. Res."},{"key":"10.1016\/S0196-6774(02)00248-1_BIB024","series-title":"Proceedings of the 6th International Workshop on Algorithms and Data Structures","first-page":"110","article-title":"General multiprocessor task scheduling: approximate solution in linear time","volume":"1663","author":"Jansen","year":"1999"},{"key":"10.1016\/S0196-6774(02)00248-1_BIB025","series-title":"Proceedings of the 31st ACM Symposium on the Theory of Computing","first-page":"394","article-title":"Makespan minimization in job shops: a polynomial time approximation scheme","author":"Jansen","year":"1999"},{"key":"10.1016\/S0196-6774(02)00248-1_BIB026","series-title":"Proceedings of the 2nd Workshop on Approximation Algorithms","first-page":"177","article-title":"A linear time approximation scheme for the job shop scheduling problem","volume":"1671","author":"Jansen","year":"1999"},{"key":"10.1016\/S0196-6774(02)00248-1_BIB027","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1287\/moor.25.4.645.12118","article-title":"Approximate strip packing","volume":"25","author":"Kenyon","year":"2000","journal-title":"Math. Oper. Res."},{"key":"10.1016\/S0196-6774(02)00248-1_BIB028","article-title":"Sequencing and scheduling: algorithms and complexity","volume":"4","author":"Lawler","year":"1993"},{"key":"10.1016\/S0196-6774(02)00248-1_BIB029","series-title":"Proceedings of the 9th European Symposium on Algorithms","first-page":"146","article-title":"Approximation algorithms for scheduling malleable tasks under precedence constraints","volume":"2161","author":"Lepere","year":"2001"},{"key":"10.1016\/S0196-6774(02)00248-1_BIB030","series-title":"Proceedings of the 5th ACM\u2013SIAM Symposium on Discrete Algorithms","first-page":"167","article-title":"Scheduling malleable and nonmalleable parallel tasks","author":"Ludwig","year":"1994"},{"key":"10.1016\/S0196-6774(02)00248-1_BIB031","series-title":"Proceedings of the 4th European Symposium of Algorithms","first-page":"39","article-title":"Preemptive weighted completion time scheduling of parallel jobs","volume":"1136","author":"Schwiegelshohn","year":"1996"},{"key":"10.1016\/S0196-6774(02)00248-1_BIB032","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1137\/S009753979222676X","article-title":"Improved approximation algorithms for shop scheduling problems","volume":"23","author":"Shmoys","year":"1994","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0196-6774(02)00248-1_BIB033","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/BF01585871","article-title":"Makespan minimization in open shops: A polynomial time approximation scheme","volume":"82","author":"Sevastianov","year":"1998","journal-title":"Math. Programming"},{"key":"10.1016\/S0196-6774(02)00248-1_BIB034","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1137\/S0097539793255801","article-title":"A strip-packing algorithm with absolute performance bound two","volume":"26","author":"Steinberg","year":"1997","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0196-6774(02)00248-1_BIB035","series-title":"Proceedings of the 4th ACM Symposium on Parallel Algorithms and Architectures","first-page":"323","article-title":"Approximate algorithms for scheduling parallelizable tasks","author":"Turek","year":"1992"},{"key":"10.1016\/S0196-6774(02)00248-1_BIB036","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1287\/opre.45.2.288","article-title":"Short shop schedules","volume":"45","author":"Williamson","year":"1997","journal-title":"Oper. Res."}],"container-title":["Journal of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0196677402002481?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0196677402002481?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,4]],"date-time":"2019-04-04T17:30:28Z","timestamp":1554399028000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0196677402002481"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,11]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2002,11]]}},"alternative-id":["S0196677402002481"],"URL":"https:\/\/doi.org\/10.1016\/s0196-6774(02)00248-1","relation":{},"ISSN":["0196-6774"],"issn-type":[{"value":"0196-6774","type":"print"}],"subject":[],"published":{"date-parts":[[2002,11]]}}}