Assigning and Scheduling Generalized Malleable Jobs Under Subadditive or Submodular Processing Speeds

References

• Ahn H-S, Lewis ME (2013) Flexible server allocation and customer routing policies for two parallel queues when service rates are not additive. Oper. Res. 61(2):344–358.Link, Google Scholar
• Amdahl GM (1967) Validity of the single processor approach to achieving large scale computing capabilities. AFIPS’67 Proc. April 18–20 1967 Spring Joint Comput. Conf. (Association for Computing Machinery, New York), 483–485.Google Scholar
• Bach F (2013) Learning with submodular functions: A convex optimization perspective. Foundations Trends Machine Learn. 6(2–3):145–373.Crossref, Google Scholar
• Bampis E, Dogeas K, Kononov A, Lucarelli G, Pascual F (2020) Scheduling malleable jobs under topological constraints. 2020 IEEE Internat. Parallel Distributed Processing Sympos. IPDPS (IEEE, Piscataway, NJ), 316–325.Google Scholar
• Bartolini E, Dell’Amico M, Iori M (2017) Scheduling cleaning activities on trains by minimizing idle times. J. Scheduling 20(5):493–506.Crossref, Google Scholar
• Bernard P-E, Gautier T, Trystram D (1999) Large scale simulation of parallel molecular dynamics. Proc. 13th Internat. Parallel Processing Sympos. 10th Sympos. Parallel Distributed Processing IPPS/SPDP 1999 (IEEE, Piscataway, NJ), 638–644.Google Scholar
• Blazewicz J, Cheng TCE, Machowiak M, Oguz C (2011) Berth and quay crane allocation: A moldable task scheduling model. J. Oper. Res. Soc. 62(7):1189–1197.Crossref, Google Scholar
• Bleuse R, Hunold S, Kedad-Sidhoum S, Monna F, Mounié G, Trystram D (2017) Scheduling independent moldable tasks on multi-cores with GPUs. IEEE Trans. Parallel Distributed Systems 28(9):2689–2702.Crossref, Google Scholar
• Bondareva ON (1963) Some applications of linear programming methods to the theory of cooperative games. Problemy Kibernetiki 10:119–139.Google Scholar
• Borba L, Ritt M (2014) A heuristic and a branch-and-bound algorithm for the assembly line worker assignment and balancing problem. Comput. Oper. Res. 45:87–96.Crossref, Google Scholar
• Candogan O, Ozdaglar A, Parrilo PA (2015) Iterative auction design for tree valuations. Oper. Res. 63(4):751–771.Link, Google Scholar
• Correa J, Marchetti-Spaccamela A, Matuschke J, Stougie L, Svensson O, Verdugo V, Verschae J (2015) Strong LP formulations for scheduling splittable jobs on unrelated machines. Math. Program. 154(1):305–328.Crossref, Google Scholar
• Dolgui A, Kovalev S, Kovalyov MY, Malyutin S, Soukhal A (2018) Optimal workforce assignment to operations of a paced assembly line. Eur. J. Oper. Res. 264(1):200–211.Crossref, Google Scholar
• Dongarra JJ, Duff IS, Sorensen DC, Van der Vorst HA (1998) Numerical Linear Algebra for High-Performance Computers (SIAM, Philadelphia).Crossref, Google Scholar
• Du J, Leung JY-T (1989) Complexity of scheduling parallel task systems. SIAM J. Discrete Math. 2(4):473–487.Crossref, Google Scholar
• Feige U (2009) On maximizing welfare when utility functions are subadditive. SIAM J. Comput. 39(1):122–142.Crossref, Google Scholar
• Fotakis D, Matuschke J, Papadigenopoulos O (2023) Malleable scheduling beyond identical machines. J. Scheduling 26:425–442.Crossref, Google Scholar
• Fotakis D, Matuschke J, Papadigenopoulos O (2024) A constant-factor approximation for generalized malleable scheduling under M♮-concave processing speeds. Math. Program., ePub ahead of print January 29, https://doi.org/10.1007/s10107-023-02054-z.Crossref, Google Scholar
• Fujiwara I, Tanaka M, Taura K, Torisawa K (2018) Effectiveness of moldable and malleable scheduling in deep learning tasks. 2018 IEEE 24th Internat. Conf. Parallel Distributed Systems ICPADS (IEEE, Piscataway, NJ), 389–398.Google Scholar
• Hochbaum DS, Shmoys DB (1987) Using dual approximation algorithms for scheduling problems theoretical and practical results. J. ACM 34(1):144–162.Crossref, Google Scholar
• Imai A, Chen HC, Nishimura E, Papadimitriou S (2008) The simultaneous berth and quay crane allocation problem. Transportation Res. Part E Logist. Transportation Rev. 44(5):900–920.Crossref, Google Scholar
• Iwata S (2008) Submodular function minimization. Math. Program. 112(1):45–64.Crossref, Google Scholar
• Jansen K, Land F (2018) Scheduling monotone moldable jobs in linear time. 2018 IEEE Internat. Parallel Distributed Processing Sympos. IPDPS (IEEE, Piscataway, NJ), 172–181.Google Scholar
• Jansen K, Porkolab L (2002) Linear-time approximation schemes for scheduling malleable parallel tasks. Algorithmica 32(3):507–520.Crossref, Google Scholar
• Jansen K, Thöle R (2010) Approximation algorithms for scheduling parallel jobs. SIAM J. Comput. 39(8):3571–3615.Crossref, Google Scholar
• Lee J, Mirrokni VS, Nagarajan V, Sviridenko M (2009) Non-monotone submodular maximization under matroid and knapsack constraints. Proc. Forty-First Annu. ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 323–332.Google Scholar
• Lenstra JK, Shmoys DB, Tardos É (1990) Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46:259–271.Crossref, Google Scholar
• Levi DS, Chen X, Bramel J (2014) The Logic of Logistics: Theory, Algorithms, and Applications for Logistics Management (Springer, New York).Crossref, Google Scholar
• Mounié G, Rapine C, Trystram D (1999) Efficient approximation algorithms for scheduling malleable tasks. Proc. Eleventh Annu. ACM Sympos. Parallel Algorithms Architectures (Association for Computing Machinery, New York), 23–32.Google Scholar
• Mounié G, Rapine C, Trystram D (2007) A 32-approximation algorithm for scheduling independent monotonic malleable tasks. SIAM J. Comput. 37(2):401–412.Crossref, Google Scholar
• Mourtos I, Vatikiotis S, Zois G (2021) Scheduling jobs on unrelated machines with job splitting and setup resource constraints for weaving in textile manufacturing. IFIP Internat. Conf. Adv. Production Management Systems (Springer, Cham, Switzerland), 424–434.Google Scholar
• Murota K (2003) Discrete Convex Analysis, SIAM Monographs on Discrete Mathematics and Applications, vol. 10 (SIAM, Philadelphia).Crossref, Google Scholar
• Nakade K, Nishiwaki R (2008) Optimal allocation of heterogeneous workers in a u-shaped production line. Comput. Indust. Engrg. 54(3):432–440.Crossref, Google Scholar
• Nguyen N-Q, Yalaoui F, Amodeo L, Chehade H, Toggenburger P (2018) Electrical vehicle charging coordination algorithms framework. Kahraman C, Kayakutlu G, eds. Energy Management—Collective and Computational Intelligence with Theory and Applications (Springer, Cham, Switzerland), 357–373.Crossref, Google Scholar
• Schrijver A (2003) Combinatorial Optimization—Polyhedra and Efficiency (Springer Berlin, Heidelberg, Germany).Google Scholar
• Serafini P (1996) Scheduling jobs on several machines with the job splitting property. Oper. Res. 44(4):617–628.Link, Google Scholar
• Shmoys DB, Tardos É (1993) An approximation algorithm for the generalized assignment problem. Math. Program. 62(1):461–474.Crossref, Google Scholar
• Turek J, Wolf JL, Yu PS (1992) Approximate algorithms scheduling parallelizable tasks. Proc. Fourth Annu. ACM Sympos. Parallel Algorithms Architectures (Association for Computing Machinery, New York), 323–332.Google Scholar
• van der Ster S (2010) The allocation of scarce resources in disaster relief. Master’s thesis, VU Amsterdam, Amsterdam.Google Scholar
• Vondrak J (2008) Optimal approximation for the submodular welfare problem in the value oracle model. Proc. Fortieth Annu. ACM Sympos. Theory Comput. STOC ‘08 (Association for Computing Machinery, New York), 67–74.Google Scholar
• Walter M, Zimmermann J (2016) Minimizing average project team size given multi-skilled workers with heterogeneous skill levels. Comput. Oper. Res. 70:163–179.Crossref, Google Scholar
• Wu X, Loiseau P (2015) Algorithms for scheduling deadline-sensitive malleable tasks. 2015 53rd Annu. Allerton Conf. Commun. Control Comput. Allerton (IEEE, Piscataway, NJ), 530–537.Google Scholar