# A Hybrid Exact-Local Search Approach for One-Machine Scheduling with Time-Dependent Capacity
## 7 Formulation and Implementation  
A formulation of the problem that will be used to construct initial solutions to the problem is presented below. Then, the formulation is slightly modified and used for solving problems involving subsets of tasks in an effort to attain better schedules overall. Let \(\mathbb{J}\) be the set of jobs. Let \(P_{j}\) be the duration of each job \(j\in\mathbb{J}\). Let \(D_{j}\) be the due date of each job \(j\in\mathbb{J}\). Let \(T\) be the number of time points. Note that the value of \(T\) is not given explicitly by the problem, but such a value can be computed by aggregating the duration of all jobs. Let \(Cap(t)\) be the capacity of the machine at each time point \(t\in 0\ldots T-1\). We define integer decision variables \(s_{j}\in 0\ldots T-1-P_{j}\) that denote the start time of each job \(j\in\mathbb{J}\). Likewise, we define integer decision variables \(f_{j}\in P_{j}\ldots T-1\) that denote the finish time of each job \(j\in\mathbb{J}\). We also define integer decision variables \(z_{j}\geq 0\) which denote the tardiness of each job \(j\in\mathbb{J}\). Finally, we define binary decision variables \(x_{\mu}\) and \(y_{\mu}\). Each one of the former variables assumes the value \(1\) if job \(j\) starts its execution at time point \(t\), or else it assumes the value \(0\). Likewise, each \(y_{\mu}\) variable marks the time point at which job \(j\) finishes. \[\begin{split}\begin{split}\begin{aligned} &\begin  
assume the value \(t\). For all other time points besides \(t\), the right sides of the former and the latter equations become 0 and \(M\), respectively. Equation (6) enforces that only one among all of the \(x_{jt}\) variables of each job \(j\) will assume the value 1. Equation (7) dictates the following association rule: for each job \(j\), when \(x_{jt}\) becomes 1 or 0, the corresponding \(y\) variable of \(j\) with the time offset \(P_{j}\), which is \(y_{jt+P_{j}}\), will also be 1 or 0, respectively. Equation (8) guarantees that for each time point, the capacity of the machine will not be violated. The values that the left side of the equation assumes are the numbers of active jobs at each time point \(t\). The first double summation counts the jobs that have started no later than \(t\), while the second double summation counts the jobs that have also finished no later than \(t\). Their difference is obviously the number of active jobs. Constraint Programming FormulationThe IBM ILOG constraint programming (CP) solver seems to be a good choice for solving scheduling problems involving jobs that occupy intervals of time and consume some types of resources that have time-varying availability [27]. The one-machine scheduling problem can be easily formulated in the IBM ILOG CP solver using one fixed-size interval variable per job (\(j\)) and the constraint always_in, which restricts all of them to assume values that collectively never exceed the maximum available capacity over time. This is possible by using a pulse cumulative function expression that represents the contribution of our fixed interval variables over time. Each job execution requires one capacity unit, which is occupied when the job starts, retained through its execution, and released when the job finishes. In our case, the variable usage aggregates all pulse requirements by all jobs. The objective function uses a set of integer variables z[job.id] that are stored in a dictionary that has the identifier of each job as keys. Each z[job.id] variable assumes the value of the job's tardiness (i.e., the non-negative difference of the job's due time (job.due_time) and its finish time (end_of(j[job.id])). An additional constraint is added that corresponds to the due times rule mentioned in Section 6. Jobs are grouped by duration, and a list ordered by due times is prepared for each group. Then, for all jobs in the list, the constraint enforces that the order of the jobs must be respected.