# A Hybrid Exact-Local Search Approach for One-Machine Scheduling with Time-Dependent Capacity
## 4 Related Work  
Hard combinatorial optimization problems, such as the one-machine scheduling with time-dependent capacity problem, are approached using numerous solving methods [10; 11]. The two basic categories of such approaches are the exact ones and the heuristic-metaheuristic ones. In the first category, one can identify mathematical programming (i.e., linear programming, integer programming, and others) [12], constraint programming [13], approaches based on SAT (satisfiability) [14] or SMT (satisfiability modulo theory) solvers [15], and, in general, methods that intelligently examine the complete search space while pruning parts of it during their quest for proven optimal solutions [16]. In the second category, the approaches are numerous, including local search methods [17; 18], genetic algorithms [19], genetic programming [20], memetic algorithms [21], differential evolution [22], ant colony optimization [23], particle swarm optimization [24], bees algorithms [25], hyper-heuristics [20], and others. Heuristically Constructed SchedulesIn [6], the authors present the schedule builder algorithm, where jobs are ordered in an arbitrary sequence, and each job is scheduled to start at the earliest possible time. After positioning each job, the capacity of the machine is updated in accordance with the partial schedule. When all jobs are scheduled, the algorithm finishes and returns a feasible schedule. This search space is guaranteed to contain an optimal solution to any problem instance [5]. So, each possible solution can be represented as a sequence of jobs to the schedule builder. Certain metaheuristic algorithms, such as genetic algorithms, may benefit from the idea of representing each possible schedule as a sequence of jobs and searching through the space of all possible permutations. \begin{table}
\begin{tabular}{c c c c c c c c c c c c} \hline \hline \(i\) & **1** & **2** & **3** & **4** & **5** & **6** & **7** & **8** & **9** & **10** & **11** & **12** \\ \hline \(p_{i},d_{i}\) & 4,4 & 4,9 & 2,13 & 3,4 & 4,7 & 3,8 & 2,10 & 3,3 & 2,13 & 3,5 & 3,9 & 5,7 \\ \hline \(S_{i},C_{i},T_{i}\) & 4,8,4 & 8,12,3 & 10,12,0 & 2,5,1 & 6,10,3 & 5,8,0 & 8,10,0 & 0,3,0 & 12,14,1 & 3,6,1 & 6,9,0 & 9,14,7 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: A sample problem instance with 12 jobs. For each job \(i\), the table shows its duration \(p_{i}\) and its due time \(d_{i}\). Additionally, for a certain schedule, the table shows the start time \((S_{i})\), completion time \((C_{i})\), and penalty incurred \((T_{i})\) for each job \(i\). \begin{table}
\begin{tabular}{c c} \hline \hline
**Number of Jobs (n)** & **Maximum Capacity (MC)** \\ \hline
120 & 3, 5, 7, 10 \\
250 & 10, 20, 30 \\
500 & 10, 20, 30 \\
750 & 10, 20, 30, 50 \\
1000 & 10, 20, 30, 50, 100 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Problem instances in the dataset. For each pair of a number of jobs and a maximum capacity, 10 individual problem instances exist. Here, we present in Algorithm 1 a modification to the schedule builder algorithm that introduces lanes, which are levels formed by the capacity of the problem. So, for example, a problem with a maximum capacity of four has four lanes; the first is always available during the time horizon, and the three others, based on the capacity, have periods of availability and unavailability. Lanes help plot schedules, disambiguate solutions with identical costs, and quickly identify jobs that form sequences of consecutive jobs.