# Scheduling Non-Preemptible Jobs to Minimize Peak Demand
## 3 Algorithms
### A Greedy Heuristic  
We also consider a greedy approach for PDM that schedules each job to have a start time with the smallest contribution to the peak energy required by the schedule. We consider both an offline and online version of the algorithm. In the online version, each job must be scheduled as soon as it arrives. The online algorithm schedules each job sequentially by finding the first starting time that minimizes the resulting peak demand. The complete algorithm is presented as Algorithm 2, where \(\mathit{height}(\mathcal{S},j,s_{j})\) is defined as the height of schedule \(\mathcal{S}\) with new job \(j\) scheduled to start at \(s_{j}\). The offline heuristic algorithm schedules individual jobs in the same fashion as the online one, but the jobs that have tight execution windows are scheduled first while jobs with more space in their execution windows are scheduled later. The complete algorithm is presented as Algorithm 3 (note that \(w_{j}=\frac{l_{j}}{d_{j}-a_{j}}\in(0,1]\) measures the execution window tightness of job \(j\); values closer to 1 indicate tighter jobs). ``` Step 1 Build schedule, \(\mathcal{S}\), by determining start times as follows: forall jobs, \(j\) (in the order that jobs arrive) \(s=a_{j}\) fortime\(t=a_{j}+1,\ldots,d_{j}-l_{j}+1\) if\(\mathit{height}(\mathcal{S},j,t)<\mathit{height}(\mathcal{S},j,s)\) \(s=t\) endif endfor \(\operatorname{start}_{j}=s\) endforall

## 4 Experimental Results

Simulations were conducted using the _OptimalDP, RoundLP, MinFit-Online_, and _MinFit-Offline_ algorithms. For a baseline comparison, we also compare to an on-demand algorithm, _OnDemand_, that schedules jobs to start on their arrival times. Realistic household power-consuming jobs were created using appliance-specific data from six residences [16]. We identified appliances (e.g., washing machine) likely to have flexible timelines and determined their height, length, and arrival time distributions within a 24 h period. Deadlines were set to be uniformly distributed between the minimum possible deadline (\(a_{j}+l_{j}-1\)) and the arrival time plus four times the average job length of that appliance. The first scenario we considered was a simple scenario meant to compare our algorithms against an optimal solution. Instead of generating jobs as described above, we randomly generated jobs with an arrival time of 0 to simulate a single peak. Figure 3 shows the average results of running _OptimalDP, RoundLP, MinFit-Online, MinFit-Offline_, and _OnDemand_ on 20 iterations of a variable number of jobs, each from this simplified data generation method. _RoundLP, MinFit-Online_, and _MinFit-Offline_ all produced near-optimal solutions at each job set size, in stark contrast to the solutions provided by _OnDemand_. The second scenario we considered was the performance of the _RoundLP, MinFit-Online_, and _MinFit-Offline_ algorithms with a large number of realistically generated jobs. Figure 4 shows the average power demand versus time of day for the _OnDemand_, _RoundLP, MinFit-Online_, and _MinFit-Offline_ algorithms when scheduling 100 instances of 500 jobs over a 24 h period. The peak demands in k Wh were 41.1 for _OnDemand_, 21.0 for _RoundLP_, 21.3 for _MinFit-Offline_, and 25.6 for _MinFit-Online_. Figure 3: Performance of peak demand minimization (PDM) scheduling algorithms in a smaller scenario where the optimal solution can be computed. ## 5 Conclusions

In this work we presented the first approximation algorithm for the PDM problem for scheduling non-preemptible jobs, as well as an optimal dynamic programming algorithm that is fixed-parameter tractable and a heuristic approach that can be adapted to the online version of the problem. The problem occurs naturally in scheduling household power consuming jobs in a smart grid power system. Simulation results indicate that there is substantial opportunity to reduce the peak demand through deferred scheduling vs. on-demand. Avenues for future work include considering renewable energy when scheduling jobs.