Busy-time scheduling on heterogeneous machines: algorithms and analysis
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...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/178611 |
| _version_ | 1826111265557184512 |
|---|---|
| author | Liu, Mozhengfu Tang, Xueyan |
| author2 | College of Computing and Data Science |
| author_facet | College of Computing and Data Science Liu, Mozhengfu Tang, Xueyan |
| author_sort | Liu, Mozhengfu |
| collection | NTU |
| description | 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(μ)-competitive algorithm in the online setting (where μ 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. |
| first_indexed | 2024-10-01T02:47:51Z |
| format | Journal Article |
| id | ntu-10356/178611 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T02:47:51Z |
| publishDate | 2024 |
| record_format | dspace |
| spelling | ntu-10356/1786112024-07-01T04:59:52Z Busy-time scheduling on heterogeneous machines: algorithms and analysis Liu, Mozhengfu Tang, Xueyan College of Computing and Data Science School of Computer Science and Engineering Computer and Information Science Busy time Scheduling 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(μ)-competitive algorithm in the online setting (where μ 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. Ministry of Education (MOE) Submitted/Accepted version This work was supported by the Ministry of Education, Singapore, through its Academic Research Fund Tier 2 under Grant MOE-T2EP20121-0005 and its Academic Research Fund Tier 1 under Grant RG112/19 (S). 2024-07-01T02:45:24Z 2024-07-01T02:45:24Z 2022 Journal Article Liu, M. & Tang, X. (2022). Busy-time scheduling on heterogeneous machines: algorithms and analysis. IEEE Transactions On Parallel and Distributed Systems, 33(12), 3942-3958. https://dx.doi.org/10.1109/TPDS.2022.3176665 1045-9219 https://hdl.handle.net/10356/178611 10.1109/TPDS.2022.3176665 2-s2.0-85130802586 12 33 3942 3958 en MOE-T2EP20121-0005 RG112/19 (S) IEEE Transactions on Parallel and Distributed Systems © 2022 IEEE. All rights reserved. This article may be downloaded for personal use only. Any other use requires prior permission of the copyright holder. The Version of Record is available online at http://doi.org/10.1109/TPDS.2022.3176665. application/pdf |
| spellingShingle | Computer and Information Science Busy time Scheduling Liu, Mozhengfu Tang, Xueyan Busy-time scheduling on heterogeneous machines: algorithms and analysis |
| title | Busy-time scheduling on heterogeneous machines: algorithms and analysis |
| title_full | Busy-time scheduling on heterogeneous machines: algorithms and analysis |
| title_fullStr | Busy-time scheduling on heterogeneous machines: algorithms and analysis |
| title_full_unstemmed | Busy-time scheduling on heterogeneous machines: algorithms and analysis |
| title_short | Busy-time scheduling on heterogeneous machines: algorithms and analysis |
| title_sort | busy time scheduling on heterogeneous machines algorithms and analysis |
| topic | Computer and Information Science Busy time Scheduling |
| url | https://hdl.handle.net/10356/178611 |
| work_keys_str_mv | AT liumozhengfu busytimeschedulingonheterogeneousmachinesalgorithmsandanalysis AT tangxueyan busytimeschedulingonheterogeneousmachinesalgorithmsandanalysis |