Scheduling Non-Preemptible Jobs to Minimize Peak Demand
This paper examines an important problem in smart grid energy scheduling; peaks in power demand are proportionally more expensive to generate and provision for. The issue is exacerbated in local microgrids that do not benefit from the aggregate smoothing experienced by large grids. Demand-side sched...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2017-10-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/10/4/122 |
| _version_ | 1828378185317744640 |
|---|---|
| author | Sean Yaw Brendan Mumey |
| author_facet | Sean Yaw Brendan Mumey |
| author_sort | Sean Yaw |
| collection | DOAJ |
| description | This paper examines an important problem in smart grid energy scheduling; peaks in power demand are proportionally more expensive to generate and provision for. The issue is exacerbated in local microgrids that do not benefit from the aggregate smoothing experienced by large grids. Demand-side scheduling can reduce these peaks by taking advantage of the fact that there is often flexibility in job start times. We focus attention on the case where the jobs are non-preemptible, meaning once started, they run to completion. The associated optimization problem is called the peak demand minimization problem, and has been previously shown to be NP-hard. Our results include an optimal fixed-parameter tractable algorithm, a polynomial-time approximation algorithm, as well as an effective heuristic that can also be used in an online setting of the problem. Simulation results show that these methods can reduce peak demand by up to 50% versus on-demand scheduling for household power jobs. |
| first_indexed | 2024-04-14T08:23:06Z |
| format | Article |
| id | doaj.art-54a83a6acf824ce0b709dd5e73654c26 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-04-14T08:23:06Z |
| publishDate | 2017-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-54a83a6acf824ce0b709dd5e73654c262022-12-22T02:04:10ZengMDPI AGAlgorithms1999-48932017-10-0110412210.3390/a10040122a10040122Scheduling Non-Preemptible Jobs to Minimize Peak DemandSean Yaw0Brendan Mumey1Los Alamos National Laboratoy, Los Alamos, NM 87545, USAGianforte School of Computing, Montana State University, Bozeman, MT 59717,USAThis paper examines an important problem in smart grid energy scheduling; peaks in power demand are proportionally more expensive to generate and provision for. The issue is exacerbated in local microgrids that do not benefit from the aggregate smoothing experienced by large grids. Demand-side scheduling can reduce these peaks by taking advantage of the fact that there is often flexibility in job start times. We focus attention on the case where the jobs are non-preemptible, meaning once started, they run to completion. The associated optimization problem is called the peak demand minimization problem, and has been previously shown to be NP-hard. Our results include an optimal fixed-parameter tractable algorithm, a polynomial-time approximation algorithm, as well as an effective heuristic that can also be used in an online setting of the problem. Simulation results show that these methods can reduce peak demand by up to 50% versus on-demand scheduling for household power jobs.https://www.mdpi.com/1999-4893/10/4/122peak demand minimizationjob schedulingapproximation algorithmssmart grid |
| spellingShingle | Sean Yaw Brendan Mumey Scheduling Non-Preemptible Jobs to Minimize Peak Demand Algorithms peak demand minimization job scheduling approximation algorithms smart grid |
| title | Scheduling Non-Preemptible Jobs to Minimize Peak Demand |
| title_full | Scheduling Non-Preemptible Jobs to Minimize Peak Demand |
| title_fullStr | Scheduling Non-Preemptible Jobs to Minimize Peak Demand |
| title_full_unstemmed | Scheduling Non-Preemptible Jobs to Minimize Peak Demand |
| title_short | Scheduling Non-Preemptible Jobs to Minimize Peak Demand |
| title_sort | scheduling non preemptible jobs to minimize peak demand |
| topic | peak demand minimization job scheduling approximation algorithms smart grid |
| url | https://www.mdpi.com/1999-4893/10/4/122 |
| work_keys_str_mv | AT seanyaw schedulingnonpreemptiblejobstominimizepeakdemand AT brendanmumey schedulingnonpreemptiblejobstominimizepeakdemand |