# A Hybrid Exact-Local Search Approach for One-Machine Scheduling with Time-Dependent Capacity
## 6 Due Times Rule  
This work contributes to identifying a rule that involves the due times of jobs with equal durations. The rule states that \"Jobs with equal duration should be scheduled in the order of their due times\". In other words, if two jobs have equal durations, they should swap places if the due time of the job that is scheduled later is sooner than the due time of the job that is scheduled sooner. This rule can be used to strengthen mathematical formulations or as a heuristic for reaching better solutions.  
Proof.: Suppose that two jobs, \(i\) and \(j\), with the same duration, are scheduled such that job \(i\) comes first and job \(j\) follows. Additionally, suppose that job \(j\) has an earlier due time than job \(i\), i.e., \(d_{j}<d_{i}\). Let \(t\) and \(t^{\prime}\) be the finish times of jobs \(i\) and \(j\), respectively, and since both jobs have the same duration, \(t<t^{\prime}\) holds. When both jobs have non-negative tardiness values, i.e., \(t-d_{i}\geq 0\) and \(t^{\prime}-d_{j}\geq 0\), swapping the jobs results again in non-negative tardiness values for both jobs. This holds because the tardiness of job \(j\) after the swap will be \(t-d_{j}>t-d_{i}\geq 0\). Moreover, \(t^{\prime}>t\geq d_{i}\), so the tardiness of job \(i\) after the swap will be \(t^{\prime}-d_{i}\geq 0\). So, the total tardiness before the swap is \((t-d_{i})+(t^{\prime}-d_{j})\), which is equal to the total tardiness after the swap, which is \((t-d_{j})+(t^{\prime}-d_{i})\). This situation is depicted in Figure 4a. The top figure shows a possible configuration of two equal-duration jobs that both incur tardiness. It can be easily seen that the total length of the gray bars that represent the tardiness remains the same after swapping jobs \(i\) and \(j\).  
The benefit of positioning equal-duration jobs according to their due times occurs when job \(i\) completes execution before its due time, and job \(j\) incurs some positive value of tardiness. Since job \(i\) has no tardiness, the total tardiness of the initial configuration is \(t^{\prime}-d_{j}\). After the swap, the total tardiness will be \((t-d_{j})+(t^{\prime}-d_{i})\). In order to prove that the total tardiness is no greater after the swap, the following inequality must hold: \((t-d_{j})+(t^{\prime}-d_{i})\leq t^{\prime}-d_{j}\). This inequality leads to the following true proposition: \((t-d_{j})+(t^{\prime}-d_{i})\leq t^{\prime}-d_{j}\implies t-d_{i}\leq 0 \implies t\leq d_{i}\). The last inequality holds since it is the assumption made for this case, i.e., job \(i\) has no tardiness. A visual representation of  
Figure 4: (**a**) Both job \(i\) and job \(j\) have non-negative tardiness values. (**b**) Job \(i\) has no tardiness, but job \(j\) incurs tardiness.  
such a situation is depicted in Figure 4b. The upper part of the figure shows the situation where job \(i\) is scheduled first, while the lower part of the figure shows the situation after swapping the jobs. Again, the gray bars represent the tardiness of the jobs, and it can be seen that the total tardiness is decreased when the jobs swap places.