# Graph-Based Modeling in Shop Scheduling Problems: Review and Extensions
## 4 Classifications and Solutions of Scheduling Problems
### Methods to Solve Scheduling Problems
#### 4.2.2 Approximate Methods  
Approximate methods do not necessarily find the optimal solution and may generate different results when solving the problem additional times [96]. Instead, approximate methods find good solutions in practical periods of time (unlike exact methods being time-expensive). Approximate methods are effective particularly in a case of NP-hard problem and large-scales problems [96].  
Approximate methods include constructive heuristics, improvement heuristics, and meta-heuristics. Constructive and improvement heuristics differ in their starting search state (an empty versus an assumed pre-existing solution) while meta-heuristics utilize different high-level strategies to search [97].  
Constructive heuristics form the solution from scratch and literally step by step, such that in each iteration, they choose the best available option [91]. The Nawaz, Enscore, Ham algorithm (NEH) is a constructive heuristic method observed multiple times in our dataset. This method sorts jobs in descending sums of processing times and then generates a job sequence by evaluating that sorted order of jobs through minimizing makespan [98].  
Local search [39; 99; 100; 101] and shifting bottleneck [102; 103] are among Improvement heuristics which were repeatedly applied in our dataset.  
Some of the more frequently occurring meta-heuristics from our dataset include genetic algorithms (GA), ant colony optimization algorithms (ACO), simulated annealing (SA), tabu search (TS), and particle swarm optimization algorithms (PSO).  
Genetic algorithms (GA) imitate the evolutionary \"survival of the fittest\" behavior [89]. All possible solutions are represented as chromosomes, and chromosomes make up generations in which \"survival of the fittest\" is applied to eliminate suboptimal solutions and create a better next generation [89]. Eventually GA should reach a generation with a good or a close-to-optimal solution.  
Ant colony optimization (ACO) method imitates the behavior of ants in their search for food using pheromones [97]. While randomly searching for food, artificial ants representing agents deposit pheromones along their path and subsequent ants choose paths with stronger pheromone concentrations [97], eventually leading to a good or a close-to-optimal solution.  
_Simulated annealing_ (SA) is a relatively simpler and older meta-heuristic. SA imitates the physical process of annealing, the cooling of a solid material and the subsequent arrangement of its particles, and uses the decrease of temperature in order to search for the optimal solution [97].  
_Tabu search_ (TS) extends the local search improvement method by incorporating other concepts to potentially find the close-to-optima such as best improvement (a method to move past local optima), tabu lists (limited memory to avoid cycles), and aspiration criteria (a work-around limited memory potentially locking out optimal solutions) in order to potentially find the close-to-optima [97].  
_Particle swarm optimization_ (PSO) imitates swarm intelligence by representing solutions as particles which then move around the state space toward theoretically better positions, until ideally converging to the global optima [44, 51]. Particles move based on their own local neighborhood and based on the total findings within the swarm, reinforcing the idea of communication [104, 105].  
```
1: Start with a random schedule or use a constructive method to generate a base schedule.
2: Calculate the performance measure
3: While a good solution (ideally, the optimal solution) has not been reached:
4: Perturb the schedule
5: Recalculate the performance measure
```  
**Algorithm 1** Solving a generic scheduling problem by an approximate method