
Handling Heterogeneous Machines in Malleable Scheduling Parallelization is an important and widespread technique to speed up the completion of time-critical tasks, not only in high-speed computing, but also in operations planning in production and logistics. A fundamental model in this context is that of malleable jobs, each of which can be assigned to a subset of machine for parallel processing. In “Assigning and Scheduling Generalized Malleable Jobs Under Submodular or Subadditive Processing Speeds,” Fotakis, Matuschke, and Papadigenopoulos go beyond the by now well-understood identical-machine setting in malleable scheduling and develop algorithmic approaches for scheduling malleable jobs under various discrete concavity assumptions on the joint processing speeds of the assigned (possibly very heterogeneous) machines. They show that under these assumptions, the task of finding a schedule of small makespan can be reduced to that of finding an assignment with small maximum machine load. For this latter problem, numerous efficient approximation algorithms are derived and their practical performance explored in a computational experiments. These results indicate that the computational challenges posed by parallelization in heterogeneous environments can indeed be overcome, enabling the optimization of heavily parallelized schedules in the aforementioned applications.
FOS: Computer and information sciences, Technology, QUAY CRANE ALLOCATION, Operations Research, Discrete Mathematics (cs.DM), makespan minimization, ASSIGNMENT, Social Sciences, BERTH, Business & Economics, 0102 Applied Mathematics, (fractional) subadditivity, MACHINES, approximation algorithms, 0802 Computation Theory and Mathematics, Science & Technology, Operations Research & Management Science, WORKERS, malleable scheduling, Management, submodularity, APPROXIMATION ALGORITHMS, 1503 Business and Management, 3507 Strategy, management and organisational behaviour, matroids, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Technology, QUAY CRANE ALLOCATION, Operations Research, Discrete Mathematics (cs.DM), makespan minimization, ASSIGNMENT, Social Sciences, BERTH, Business & Economics, 0102 Applied Mathematics, (fractional) subadditivity, MACHINES, approximation algorithms, 0802 Computation Theory and Mathematics, Science & Technology, Operations Research & Management Science, WORKERS, malleable scheduling, Management, submodularity, APPROXIMATION ALGORITHMS, 1503 Business and Management, 3507 Strategy, management and organisational behaviour, matroids, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
