Busy-Time Scheduling on Heterogeneous Machines: Algorithms and Analysis
- 23 May 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 33 (12) , 3942-3958
Abstract
We study a generalized busy-time scheduling model on heterogeneous machines. The input to the model includes a set of jobs and a set of machine types. Each job has a size and a time interval during which it should be processed. Each job is to be placed on a machine for execution. Different types of machines have distinct capacities and cost rates. The total size of the jobs running on a machine must always be kept within the machine's capacity, giving rise to placement restrictions for jobs of various sizes among the machine types. Each machine used is charged according to the time duration in which it is busy, i.e., it is processing jobs. The objective is to schedule the jobs into machines to minimize the total cost of all the machines used. We develop an $O(1)$ -approximation algorithm in the offline setting and an $O(\mu)$ -competitive algorithm in the online setting (where $\mu$ is the max/min job length ratio), both of which are asymptotically optimal. This article significantly improves the analysis of the algorithms over our preliminary work.
Keywords
Funding Information
- Ministry of Education - Singapore (MOE-T2EP20121-0005)
- Academic Research Fund (RG112/19 (S))
This publication has 19 references indexed in Scilit:
- Competitiveness of Dynamic Bin Packing for Online Cloud Server AllocationIEEE/ACM Transactions on Networking, 2016
- Clairvoyant Dynamic Bin Packing for Job Scheduling with Minimum Server Usage Time2016
- Dynamic Bin Packing for On-Demand Cloud Resource AllocationIEEE Transactions on Parallel and Distributed Systems, 2015
- Optimizing busy time on parallel machinesTheoretical Computer Science, 2015
- Real-time scheduling to minimize machine busy timesJournal of Scheduling, 2014
- Online optimization of busy time on parallel machinesTheoretical Computer Science, 2014
- Minimizing total busy time in parallel scheduling with application to optical networksTheoretical Computer Science, 2010
- Energy-efficient algorithmsCommunications of the ACM, 2010
- Approximation Algorithms for Wavelength Assignment2005
- Line System Design and a Generalized Coloring Problem2003