{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T02:49:56Z","timestamp":1760150996709,"version":"build-2065373602"},"reference-count":28,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2022,2,12]],"date-time":"2022-02-12T00:00:00Z","timestamp":1644624000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We optimize the assignment of transporters to several jobs. Each job consists of processing a large, decomposable volume. A fleet of transporters is given, each of which can only process a limited volume at a time. After processing its share, a transporter must rest for a short time before being able to process another part. This time is only dependent on the assigned job, not on the transporter. Other transporters can take over the processing while a transporter rests. Transporters assigned to the same job wait for their turn in a queue. A transporter can only be assigned to one job. Our goal is to simultaneously minimize the maximum job completion time and the number of assigned transporters by computing the frontier of Pareto optimal solutions. In general, we show that it is NP-hard in the strong sense to compute even a single point on the Pareto frontier. We provide exact methods and heuristics to compute the Pareto frontier for the general problem and compare them computationally.<\/jats:p>","DOI":"10.3390\/a15020060","type":"journal-article","created":{"date-parts":[[2022,2,13]],"date-time":"2022-02-13T20:32:30Z","timestamp":1644784350000},"page":"60","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Allocating Small Transporters to Large Jobs"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8048-3484","authenticated-orcid":false,"given":"Neil","family":"Jami","sequence":"first","affiliation":[{"name":"Fraunhofer Institute for Industrial Mathematics, Fraunhofer-Platz 1, 67663 Kaiserslautern, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5812-707X","authenticated-orcid":false,"given":"Neele","family":"Leith\u00e4user","sequence":"additional","affiliation":[{"name":"Fraunhofer Institute for Industrial Mathematics, Fraunhofer-Platz 1, 67663 Kaiserslautern, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0577-9933","authenticated-orcid":false,"given":"Christian","family":"Wei\u00df","sequence":"additional","affiliation":[{"name":"Fraunhofer Institute for Industrial Mathematics, Fraunhofer-Platz 1, 67663 Kaiserslautern, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,2,12]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/j.biosystemseng.2015.07.002","article-title":"Coverage planning for capacitated field operations, part II: Optimisation","volume":"139","author":"Jensen","year":"2015","journal-title":"Biosyst. Eng."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"105419","DOI":"10.1016\/j.cor.2021.105419","article-title":"A bi-objective mathematical model for integrated planning of sugarcane harvesting and transport operations","volume":"134","author":"Melo","year":"2021","journal-title":"Comput. Oper. Res."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/j.autcon.2016.03.012","article-title":"SmartSite: Intelligent and autonomous environments, machinery, and processes to realize smart road construction projects","volume":"71","author":"Kuenzel","year":"2016","journal-title":"Autom. Constr."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Payr, F., and Schmid, V. (2009, January 10\u201312). Optimizing deliveries of ready-mixed concrete. Proceedings of the 2009 2nd International Symposium on Logistics and Industrial Informatics, Linz, Austria.","DOI":"10.1109\/LINDI.2009.5258569"},{"key":"ref_5","unstructured":"W\u00f6rz, S.K. (2017). Entwicklung Eines Planungssytems zur Optimierung von Agrarlogistik-Prozessen. [Ph.D. Thesis, Technische Universit\u00e4t M\u00fcnchen]."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1016\/j.ejor.2005.01.028","article-title":"Sugar cane transportation in Cuba, a case study","volume":"174","year":"2006","journal-title":"Eur. J. Oper. Res."},{"key":"ref_7","first-page":"32","article-title":"Reducing harvest costs through coordinated sugarcane harvest and transport operations in Louisiana","volume":"28","author":"Salassi","year":"2008","journal-title":"J. Am. Soc. Sugar Cane Technol."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/j.cor.2016.11.017","article-title":"Integrating employee timetabling with scheduling of machines and transporters in a job-shop environment: A mathematical formulation and an Anarchic Society Optimization algorithm","volume":"84","year":"2017","journal-title":"Comput. Oper. Res."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/j.biosystemseng.2014.07.012","article-title":"Advances in agricultural machinery management: A review","volume":"126","author":"Bochtis","year":"2014","journal-title":"Biosyst. Eng."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1016\/j.ijpe.2016.01.010","article-title":"Crop-related harvesting and processing planning: A review","volume":"174","author":"Kusumastuti","year":"2016","journal-title":"Int. J. Prod. Econ."},{"key":"ref_11","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability, Freeman."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"173","DOI":"10.15446\/dyna.v83n195.49490","article-title":"A mixed-integer linear programming model for harvesting, loading and transporting sugarcane: A case study in Peru","volume":"83","author":"Sarache","year":"2016","journal-title":"DYNA"},{"key":"ref_13","unstructured":"Ehrgott, M. (2005). Multicriteria Optimization, Springer Science & Business Media."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/s10107-002-0323-0","article-title":"On the capacitated vehicle routing problem","volume":"94","author":"Ralphs","year":"2003","journal-title":"Math. Program."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1023\/A:1020958815308","article-title":"Divisible load theory: A new paradigm for load scheduling in distributed systems","volume":"6","author":"Bharadwaj","year":"2003","journal-title":"Clust. Comput."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1155\/2014\/460354","article-title":"Comprehensive Review on Divisible Load Theory: Concepts, Strategies, and Approaches","volume":"2014","author":"Ghanbari","year":"2014","journal-title":"Math. Probl. Eng."},{"key":"ref_17","first-page":"297","article-title":"The combinatorics in divisible load scheduling","volume":"30","author":"Drozdowski","year":"2005","journal-title":"Found. Comput. Decis. Sci."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Altmann, J., Vanmechelen, K., and Rana, O.F. (2013). Scheduling Divisible Loads to Optimize the Computation Time and Cost. Economics of Grids, Clouds, Systems, and Services, Springer International Publishing.","DOI":"10.1007\/978-3-319-02414-1"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1007\/s10951-019-00626-6","article-title":"Scheduling divisible loads with time and cost constraints","volume":"24","author":"Drozdowski","year":"2019","journal-title":"J. Sched."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1002\/nav.3800220110","article-title":"The knapsack problem: A survey","volume":"22","author":"Salkin","year":"1975","journal-title":"Nav. Res. Logist. Q."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Hiley, A., and Julstrom, B.A. (2006, January 8\u201312). The quadratic multiple knapsack problem and three heuristic approaches to it. Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, Seattle, WA, USA.","DOI":"10.1145\/1143997.1144096"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"658","DOI":"10.1016\/j.ejor.2007.06.068","article-title":"Heuristics for the 0\u20131 multidimensional knapsack problem","volume":"199","author":"Boyer","year":"2009","journal-title":"Eur. J. Oper. Res."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1137\/S0097539700382820","article-title":"A polynomial time approximation scheme for the multiple knapsack problem","volume":"35","author":"Chekuri","year":"2005","journal-title":"SIAM J. Comput."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1392","DOI":"10.1137\/080731207","article-title":"Parameterized Approximation Scheme for the Multiple Knapsack Problem","volume":"39","author":"Jansen","year":"2010","journal-title":"SIAM J. Comput."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/0166-218X(81)90005-6","article-title":"A Bound and Bound algorithm for the zero-one multiple knapsack problem","volume":"3","author":"Martello","year":"1981","journal-title":"Discret. Appl. Math."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"528","DOI":"10.1016\/S0377-2217(98)00120-9","article-title":"An exact algorithm for large multiple knapsack problems","volume":"114","author":"Pisinger","year":"1999","journal-title":"Eur. J. Oper. Res."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1023\/A:1009894503716","article-title":"Approximation algorithms for the multiple knapsack problem with assignment restrictions","volume":"4","author":"Dawande","year":"2000","journal-title":"J. Comb. Optim."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/s10878-005-1414-7","article-title":"A Framework for the Complexity of High-Multiplicity Scheduling Problems","volume":"9","author":"Brauner","year":"2005","journal-title":"J. Comb. Optim."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/2\/60\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:18:06Z","timestamp":1760134686000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/2\/60"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,12]]},"references-count":28,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2022,2]]}},"alternative-id":["a15020060"],"URL":"https:\/\/doi.org\/10.3390\/a15020060","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,2,12]]}}}