{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T15:03:12Z","timestamp":1772550192748,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,10,16]],"date-time":"2021-10-16T00:00:00Z","timestamp":1634342400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,10,16]],"date-time":"2021-10-16T00:00:00Z","timestamp":1634342400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider a number of parallel-machine scheduling problems in which jobs have variable processing times. The actual processing time of each job is described by an arbitrary positive function of the position it holds on a machine. However, the function itself may additionally depend on the job or a machine this job was assigned to. Our aim is to find a schedule that minimizes the objectives of maximum completion time or the total completion time. We present a full set of polynomial solutions for the cases of jobs with no precedence constraints. We also show that the case of single-chained jobs may be not easier in general, but some polynomial results can be obtained, too.<\/jats:p>","DOI":"10.1007\/s10878-021-00821-2","type":"journal-article","created":{"date-parts":[[2021,10,16]],"date-time":"2021-10-16T20:55:28Z","timestamp":1634417728000},"page":"207-222","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Parallel-machine scheduling of jobs with mixed job-, machine- and position-dependent processing times"],"prefix":"10.1007","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8283-7872","authenticated-orcid":false,"given":"Bart\u0142omiej","family":"Przybylski","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,10,16]]},"reference":[{"key":"821_CR1","doi-asserted-by":"publisher","unstructured":"Agnetis A, Billaut JC, Gawiejnowicz S, Pacciarelli D, Soukhal A (2014) Multiagent scheduling. Models and algorithms. Springer. https:\/\/doi.org\/10.1007\/978-3-642-41880-8","DOI":"10.1007\/978-3-642-41880-8"},{"issue":"4","key":"821_CR2","doi-asserted-by":"publisher","first-page":"1642","DOI":"10.1080\/00207543.2017.1355576","volume":"56","author":"A Azzouz","year":"2017","unstructured":"Azzouz A, Ennigrou M, Ben Said L (2017) Scheduling problems under learning effects: classification and cartography. Int J Prod Res 56(4):1642\u20131661. https:\/\/doi.org\/10.1080\/00207543.2017.1355576","journal-title":"Int J Prod Res"},{"key":"821_CR3","doi-asserted-by":"publisher","unstructured":"Bansal N, Srinivasan A, Svensson O (2019) Lift-and-round to improve weighted completion time on unrelated machines. SIAM J Comput STOC16-138\u2013STOC16\u2013159. https:\/\/doi.org\/10.1137\/16M1099583","DOI":"10.1137\/16M1099583"},{"issue":"1","key":"821_CR4","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/S0377-2217(98)00246-X","volume":"115","author":"D Biskup","year":"1999","unstructured":"Biskup D (1999) Single-machine scheduling with learning considerations. Eur J Oper Res 115(1):173\u2013178. https:\/\/doi.org\/10.1016\/S0377-2217(98)00246-X","journal-title":"Eur J Oper Res"},{"key":"821_CR5","doi-asserted-by":"publisher","unstructured":"Brodal GS, Lagogiannis G, Tarjan RE (2012) Strict Fibonacci heaps. In: Proceedings of the forty-fourth annual ACM symposium on theory of computing, association for computing machinery, STOC\u201912, pp 1177\u20131184. https:\/\/doi.org\/10.1145\/2213977.2214082","DOI":"10.1145\/2213977.2214082"},{"key":"821_CR6","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/361011.361064","volume":"17","author":"J Bruno","year":"1974","unstructured":"Bruno J, Coffman E Jr, Sethi R (1974) Scheduling independent tasks to reduce mean finishing time. Commun ACM 17:382\u2013387","journal-title":"Commun ACM"},{"key":"821_CR7","doi-asserted-by":"publisher","unstructured":"Burkard R, DellAmico M, Martello S (2012) Assignment problems. Society for industrial and applied mathematics. https:\/\/doi.org\/10.1137\/1.9781611972238","DOI":"10.1137\/1.9781611972238"},{"key":"821_CR8","unstructured":"Conway R, Maxwell W, Miller L (1967) Theory of scheduling. Addison-Wesley Publishing Company"},{"issue":"1","key":"821_CR9","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/j.cie.2012.10.010","volume":"64","author":"M Debczynski","year":"2013","unstructured":"Debczynski M, Gawiejnowicz S (2013) Scheduling jobs with mixed processing times, arbitrary precedence constraints and maximum cost criterion. Comput Indus Eng 64(1):273\u2013279. https:\/\/doi.org\/10.1016\/j.cie.2012.10.010","journal-title":"Comput Indus Eng"},{"issue":"1","key":"821_CR10","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1080\/00140135708964571","volume":"1","author":"J DeJong","year":"1957","unstructured":"DeJong J (1957) The effects of increasing skill on cycle time and its consequences for time standards. Ergonomics 1(1):51\u201360. https:\/\/doi.org\/10.1080\/00140135708964571","journal-title":"Ergonomics"},{"issue":"3","key":"821_CR11","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M Fredman","year":"1987","unstructured":"Fredman M, Tarjan R (1987) Fibonacci heaps and their uses in improved network optimization algorithms. J ACM 34(3):596\u2013615. https:\/\/doi.org\/10.1145\/28869.28874","journal-title":"J ACM"},{"issue":"6","key":"821_CR12","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0020-0190(96)00021-X","volume":"57","author":"S Gawiejnowicz","year":"1996","unstructured":"Gawiejnowicz S (1996) A note on scheduling on a single processor with speed dependent on a number of executed jobs. Inform Process Lett 57(6):297\u2013300. https:\/\/doi.org\/10.1016\/0020-0190(96)00021-X","journal-title":"Inform Process Lett"},{"key":"821_CR13","doi-asserted-by":"publisher","unstructured":"Gawiejnowicz S (2020) Models and algorithms of time-dependent scheduling. Springer. https:\/\/doi.org\/10.1007\/978-3-662-59362-2","DOI":"10.1007\/978-3-662-59362-2"},{"issue":"4","key":"821_CR14","doi-asserted-by":"publisher","first-page":"1475","DOI":"10.1007\/s11590-012-0535-z","volume":"8","author":"X Huang","year":"2014","unstructured":"Huang X, Wang MZ (2014) Single machine group scheduling with time and position dependent processing times. Optim Lett 8(4):1475\u20131485. https:\/\/doi.org\/10.1007\/s11590-012-0535-z","journal-title":"Optim Lett"},{"key":"821_CR15","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/j.cie.2014.12.009","volume":"80","author":"M Ji","year":"2015","unstructured":"Ji M, Yao D, Yang Q, Cheng T (2015) Machine scheduling with DeJongs learning effect. Comput Indus Eng 80:195\u2013200. https:\/\/doi.org\/10.1016\/j.cie.2014.12.009","journal-title":"Comput Indus Eng"},{"issue":"1\u20133","key":"821_CR16","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"J Lenstra","year":"1990","unstructured":"Lenstra J, Shmoys S, Tardos \u00c9 (1990) Approximation algorithms for scheduling unrelated parallel machines. Math Program 46(1\u20133):259\u2013271","journal-title":"Math Program"},{"issue":"17","key":"821_CR17","doi-asserted-by":"publisher","first-page":"5758","DOI":"10.1080\/00207543.2017.1418986","volume":"56","author":"X Liu","year":"2018","unstructured":"Liu X, Lu S, Pei J, Pardalos PM (2018) A hybrid VNS-HS algorithm for a supply chain scheduling problem with deteriorating jobs. Int J Prod Res 56(17):5758\u20135775. https:\/\/doi.org\/10.1080\/00207543.2017.1418986","journal-title":"Int J Prod Res"},{"key":"821_CR18","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1016\/j.asoc.2018.02.018","volume":"66","author":"S Lu","year":"2018","unstructured":"Lu S, Liu X, Pei J, Thai M, Pardalos P (2018) A hybrid ABC-TS algorithm for the unrelated parallel-batching machines scheduling problem with deteriorating jobs and maintenance activity. Appl Soft Comput 66:168\u2013182. https:\/\/doi.org\/10.1016\/j.asoc.2018.02.018","journal-title":"Appl Soft Comput"},{"key":"821_CR19","doi-asserted-by":"publisher","first-page":"1422","DOI":"10.1057\/palgrave.jors.2602480","volume":"59","author":"G Mosheiov","year":"2008","unstructured":"Mosheiov G (2008) Minimizing total absolute deviation of job completion times: extensions to position-dependent processing times and parallel identical machines. J Oper Res Soc 59:1422\u20131424. https:\/\/doi.org\/10.1057\/palgrave.jors.2602480","journal-title":"J Oper Res Soc"},{"issue":"3","key":"821_CR20","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1016\/S0377-2217(02)00358-2","volume":"147","author":"G Mosheiov","year":"2003","unstructured":"Mosheiov G, Sidney J (2003) Scheduling with general job-dependent learning curves. Eur J Oper Res 147(3):665\u2013670. https:\/\/doi.org\/10.1016\/S0377-2217(02)00358-2","journal-title":"Eur J Oper Res"},{"issue":"2","key":"821_CR21","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1016\/j.cie.2010.04.008","volume":"59","author":"D Oko\u0142owski","year":"2010","unstructured":"Oko\u0142owski D, Gawiejnowicz S (2010) Exact and heuristic algorithms for parallel-machine scheduling with DeJongs learning effect. Comput Indus Eng 59(2):272\u2013279. https:\/\/doi.org\/10.1016\/j.cie.2010.04.008","journal-title":"Comput Indus Eng"},{"issue":"7","key":"821_CR22","doi-asserted-by":"publisher","first-page":"1273","DOI":"10.1007\/s11590-016-1075-8","volume":"11","author":"B Przybylski","year":"2017","unstructured":"Przybylski B (2017) Precedence constrained parallel-machine scheduling of position-dependent jobs. Optimi Lett 11(7):1273\u20131281. https:\/\/doi.org\/10.1007\/s11590-016-1075-8","journal-title":"Optimi Lett"},{"issue":"4","key":"821_CR23","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1137\/S0895480199357078","volume":"15","author":"A Schulz","year":"2002","unstructured":"Schulz A, Skutella M (2002) Scheduling unrelated machines by randomized rounding. SIAM J Disc Math 15(4):450\u2013469. https:\/\/doi.org\/10.1137\/S0895480199357078","journal-title":"SIAM J Disc Math"},{"key":"821_CR24","doi-asserted-by":"publisher","unstructured":"Strusevich V, Rustogi K (2017) Scheduling with time-changing effects and rate-modifying activities. Springer. https:\/\/doi.org\/10.1007\/978-3-319-39574-6","DOI":"10.1007\/978-3-319-39574-6"},{"key":"821_CR25","doi-asserted-by":"publisher","unstructured":"Sun L, Ning L, Huo J (2020) Group scheduling problems with time-dependent and position-dependent DeJongs learning effect. Math Prob Eng 1\u20138. https:\/\/doi.org\/10.1155\/2020\/5161872","DOI":"10.1155\/2020\/5161872"},{"issue":"1","key":"821_CR26","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1057\/jors.2008.146","volume":"61","author":"JB Wang","year":"2010","unstructured":"Wang JB (2010) Single-machine scheduling with a sum-of-actual-processing-time-based learning effect. J Oper Res Soc 61(1):172\u2013177. https:\/\/doi.org\/10.1057\/jors.2008.146","journal-title":"J Oper Res Soc"},{"issue":"3","key":"821_CR27","doi-asserted-by":"publisher","first-page":"649","DOI":"10.1016\/j.apm.2012.02.055","volume":"37","author":"JB Wang","year":"2013","unstructured":"Wang JB, Wang JJ (2013) Single-machine scheduling with precedence constraints and position-dependent processing times. Appl Math Modelll 37(3):649\u2013658. https:\/\/doi.org\/10.1016\/j.apm.2012.02.055","journal-title":"Appl Math Modelll"},{"issue":"9","key":"821_CR28","doi-asserted-by":"publisher","first-page":"1475","DOI":"10.1080\/0305215X.2019.1664498","volume":"52","author":"JB Wang","year":"2020","unstructured":"Wang JB, Gao M, Wang JJ, Liu L, He H (2020) Scheduling with a position-weighted learning effect and job release dates. Eng Optim 52(9):1475\u20131493. https:\/\/doi.org\/10.1080\/0305215X.2019.1664498","journal-title":"Eng Optim"},{"issue":"4","key":"821_CR29","doi-asserted-by":"publisher","first-page":"122","DOI":"10.2514\/8.155","volume":"3","author":"T Wright","year":"1936","unstructured":"Wright T (1936) Factors affecting the cost of airplanes. J Aeron Sci 3(4):122\u2013128. https:\/\/doi.org\/10.2514\/8.155","journal-title":"J Aeron Sci"},{"key":"821_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.cie.2018.01.002","volume":"117","author":"X Zhang","year":"2018","unstructured":"Zhang X, Liao L, Zhang W, Cheng T, Tan Y, Ji M (2018) Single-machine group scheduling with new models of position-dependent processing times. Comput Indus Eng 117:1\u20135. https:\/\/doi.org\/10.1016\/j.cie.2018.01.002","journal-title":"Comput Indus Eng"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00821-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-021-00821-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00821-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,29]],"date-time":"2022-07-29T07:27:05Z","timestamp":1659079625000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-021-00821-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,16]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["821"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00821-2","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,16]]},"assertion":[{"value":"28 September 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 October 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}