A local neighborhood is the set of candidate solutions reachable from a current solution through permitted local moves. Search algorithms inspect this nearby set rather than the entire solution space. In tabu search, the neighborhood changes dynamically as memory and exploration rules guide which candidates remain available. section 6.2
The permitted move determines the neighborhood. For assembly-line balancing, represent a solution as a task permutation and define neighbors by exchanging any pair of tasks. With six tasks, this produces C(6,2) = 15 possible neighbors before precedence and cycle-time feasibility are considered. section 6.6
A practical neighborhood-search iteration proceeds as follows:
- Generate neighboring solutions from the current task sequence. section 6.6
- Discard moves prohibited by the tabu structure, while allowing aspiration to reconsider a tabu move that improves the best-known solution. section 6.2
- Evaluate feasible candidates using the chosen objective, such as smoothing index, while respecting precedence and cycle-time constraints. section 6.6
Six-task assembly line
Starting with [1 2 3 4 5 6], exchange two task positions to create candidate sequences. Evaluate each assignment without exceeding a four-minute cycle time or violating precedence. Select the best permitted candidate, update the tabu list, and repeat; the resulting workloads and smoothing index quantify the balance. section 6.6
Algorithm 6.2 Tabu search
Input: an initial feasible solution
Output: optimal solution
Begin
While termination criteria not met do
Choose the best: s’∈N(s) ← N(s)-T(s)+A(s)
Memorize s’ if it improves the best known solution
s←s’
Update Tab list T(S) and Aspiration criterion A(s)
Use the algorithm listing to trace how neighborhood candidates, tabu restrictions, aspiration, memory updates, and termination fit together. section 6.2
