Scheduling Parallel-Task Jobs Subject to Packing and Placement Constraints

DOI10.1287/OPRE.2021.2198MaRDI QIDQ5060512zbMATH OpenOpenAlexFDO

Authors M. Shafiee, Javad Ghaderi

Publication date 10 January 2023

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.00518

zbMATH Keywords

approximation algorithmsdata-parallel computingdatacentersscheduling algorithms

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Abstract: Motivated by modern parallel computing applications, we consider the problem of scheduling parallel-task jobs with heterogeneous resource requirements in a cluster of machines. Each job consists of a set of tasks that can be processed in parallel, however, the job is considered completed only when all its tasks finish their processing, which we refer to as "synchronization" constraint. Further, assignment of tasks to machines is subject to "placement" constraints, i.e., each task can be processed only on a subset of machines, and processing times can also be machine dependent. Once a task is scheduled on a machine, it requires a certain amount of resource from that machine for the duration of its processing. A machine can process ("pack") multiple tasks at the same time, however the cumulative resource requirement of the tasks should not exceed the machine's capacity. Our objective is to minimize the weighted average of the jobs' completion times. The problem, subject to synchronization, packing and placement constraints, is NP-hard, and prior theoretical results only concern much simpler models. For the case that migration of tasks among the placement-feasible machines is allowed, we propose a preemptive algorithm with an approximation ratio of $(6+epsilon)$. In the special case that only one machine can process each task, we design an algorithm with improved approximation ratio of $4$. Finally, in the case that migrations (and preemptions) are not allowed, we design an algorithm with an approximation ratio of $24$. Our algorithms use a combination of linear program relaxation and greedy packing techniques. We present extensive simulation results, using a real traffic trace, that demonstrate that our algorithms yield significant gains over the prior approaches.

Recommendations

• Multiprocessor scheduling with machine allotment and parallelism constraints
• On-line scheduling of parallel jobs in heterogeneous multiple clusters
• Scheduling parallel jobs on heterogeneous platforms
• Resource constrained scheduling on multiple machines
• Scheduling distributed clusters of parallel machines : primal-dual and LP-based approximation algorithms

Cites work

• A (2+ε)-approximation algorithm for the generalized preemptive open shop problem with minsum objective
• Approximation algorithms for scheduling unrelated parallel machines
• Approximation Bounds for a General Class of Precedence Constrained Parallel Machine Scheduling Problems
• Better approximation guarantees for job-shop scheduling
• Bounds for Multiprocessor Scheduling with Resource Constraints
• Convex quadratic and semidefinite programming relaxations in scheduling
• Coordinated scheduling of customer orders for quick response
• scientific article; zbMATH DE number 1187165 (Why is no real title available?)
• Improved bounds for scheduling conflicting jobs with minsum criteria
• Inapproximability of hypergraph vertex cover and applications to scheduling problems
• Minimizing the sum of weighted completion times in a concurrent open shop
• On Representatives of Subsets
• Order Scheduling Models: Hardness and Algorithms
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• Preemptive Weighted Completion Time Scheduling of Parallel Jobs
• Resource constrained scheduling on multiple machines
• Scheduling orders for multiple product types to minimize total weighted completion time
• Scheduling subject to resource constraints: Classification and complexity
• Scheduling to minimize total weighted completion time via time-indexed linear programming relaxations
• Scheduling Unrelated Machines by Randomized Rounding
• Supply Chain Scheduling: Conflict and Cooperation in Assembly Systems

Cited in

(4)

• Algorithms for hierarchical and semi-partitioned parallel scheduling
• Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width
• The preemptive resource allocation problem
• On cluster resource allocation for multiple parallel task graphs

Describes a project that uses

Uses Software

• MapReduce
• Apache Spark

This page was built for publication: Scheduling Parallel-Task Jobs Subject to Packing and Placement Constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5060512)