# Scheduling Non-Preemptible Jobs to Minimize Peak Demand
## 3 Algorithms
### An Approximation Algorithm
#### 3.2.3 Continuous Timescales  
The ILP detailed above is polynomial in size for the case of discrete timescales, where each \(I_{j}\) is finite, but not for continuous timescales in which jobs can be scheduled anywhere in the arrival-deadline window (so \(I_{j}\) is infinite). Using a technique similar to the one introduced in [9] for the unit-height machine minimization problem, we show that any continuous instance can be transformed into a corresponding discrete instance such that an optimal solution to the discrete instance provides a solution to the continuous instance that is within a factor of two from optimal. Given a set of continuous jobs \(J\), we first schedule as many jobs as possible, \(J^{\prime}\subset J\), without any overlaps by starting at the first time point and proceeding in this fashion: As soon as no job is being served, schedule the job that will complete the earliest from all remaining jobs. A set of time points \(P\) can be constructed from this initial schedule by adding the start and end times from all the scheduled intervals in \(J^{\prime}\) and by adding the release times and deadlines for each remaining job in \(J\setminus J^{\prime}\). This means that each interval of every remaining job contains at least one element of \(P\) and \(|P|\leq 2n\). If some interval of job \(j\in J\setminus J^{\prime}\) did not contain a point of \(P\), then either it is nested inside a scheduled interval of \(J^{\prime}\) and thus would have been scheduled since it ends sooner, or it is totally separated from any scheduled intervals and thus would also have been scheduled as well. Next, for each remaining job \(j\in J\setminus J^{\prime}\), we discretize its intervals by expanding them to points in \(P\): For each interval, move its left endpoint to the nearest point in \(P\) that lies to the left and its right endpoint to the nearest point in \(P\) that lies to the right. This results in a finite number (at most \(|P|\)) of possible intervals for job \(j\). Consider an optimal solution to the continuous instance. When this solution is transformed to a discrete instance by expanding the intervals as above, the overall height of the solution may increase,as two intervals that did not overlap now overlap. It is easy to see that these intervals must have originally overlapped two consecutive points from \(P\). Thus, the height of the schedule can at most double after interval expansion. This implies that the height of an optimal schedule for the discrete instance is at most twice the optimal height of the continuous instance. Finally, observe that in the discrete instance we only need to look at the height at times \(t\in L\) to determine the overall height of the schedule; this is because we can slide any time \(t\) a little bit to the left until it touches the left endpoint of some interval without changing the overall height of the schedule above \(t\). By our construction,  
\[|L|\leq|P|\leq 2n \tag{4}\]  
The following theorem shows that Algorithm 1 provides a polynomial-time approximation algorithm for PDM (with a continuous timescale). The schedule generated by the RoundLP has a height of at most \(O\big{(}\frac{\log n}{\log\log n}\big{)}\) times the height of the optimal ILP's schedule, with probability at least \(1-O(1/n)\). Proof. : Let \(X_{i,j}\in\{0,1\}\) be the random variable produced by rounding \(x_{i,j}\) in RoundLP. For each \(t\in L\), define the random variables \(Z_{t}\) and \(Y_{t}\) as  
\[Z_{t} =\sum_{i\in\bigcup_{j}I_{j}:t\in i}h_{j}X_{i,j}\] \[Y_{t} =\sum_{i\in\bigcup_{j}I_{j}:t\in i}\frac{h_{j}}{h}X_{i,j},\text { where }h=\max_{j}\{h_{j}\}\]  
Bounding the probability that \(Y_{t}\) exceeds some factor \(\alpha\) times the optimal height (\(H^{\text{opt}}\)) divided by \(h\) results in the same bound for the probability that \(Z_{t}\) exceeds \(\alpha\) times the optimal schedule height:  
\[ \begin{array}{rl}\Pr[Z_{t}>\alpha H^{\text{opt}}]&=\Pr[hY_{t}>\alpha H^{ \text{opt}}]\\ &=\Pr[Y_{t}>\alpha\frac{H^{\text{opt}}}{h}]\end{array}