This chapter discusses local search algorithms for solving intractable time-dependent scheduling problems. It is the third part of the book and includes four sections. Section 11.1 introduces basic definitions of local search algorithms. Section 11.2 briefly reviews basic types of local search algorithms. Section 11.3 discusses local search algorithms for time-dependent scheduling problems. Section 11.4 provides conclusions and a table.
In Section 11.1, the concept of an optimization problem is introduced. An optimization problem is defined by a set of instances, each defined by a pair (F, f), where F is the set of feasible solutions and f is a criterion function. A solution is optimal if it minimizes the criterion function. A neighborhood function N defines the set of neighbors of a solution. A local minimum is a solution where no neighbor has a lower criterion value. An exact neighborhood function ensures that all local minima are also global minima.
Section 11.1 also discusses general concepts of local search. Local search is a general approach for finding suboptimal solutions to intractable optimization problems. It starts from an initial solution, explores its neighborhood, and iteratively improves the solution. The pseudo-code of a general local search algorithm is provided, including initialization, neighborhood generation, and a stopping condition.
The algorithm's basic assumptions can be modified in various ways. For example, the search may not be conducted in the set of all feasible solutions but in a transformed set E(F). The neighborhood function N is problem-specific and can be defined in various ways. The stopping condition depends on the variant of the local search algorithm used. Some steps in the algorithm may be omitted or simplified.This chapter discusses local search algorithms for solving intractable time-dependent scheduling problems. It is the third part of the book and includes four sections. Section 11.1 introduces basic definitions of local search algorithms. Section 11.2 briefly reviews basic types of local search algorithms. Section 11.3 discusses local search algorithms for time-dependent scheduling problems. Section 11.4 provides conclusions and a table.
In Section 11.1, the concept of an optimization problem is introduced. An optimization problem is defined by a set of instances, each defined by a pair (F, f), where F is the set of feasible solutions and f is a criterion function. A solution is optimal if it minimizes the criterion function. A neighborhood function N defines the set of neighbors of a solution. A local minimum is a solution where no neighbor has a lower criterion value. An exact neighborhood function ensures that all local minima are also global minima.
Section 11.1 also discusses general concepts of local search. Local search is a general approach for finding suboptimal solutions to intractable optimization problems. It starts from an initial solution, explores its neighborhood, and iteratively improves the solution. The pseudo-code of a general local search algorithm is provided, including initialization, neighborhood generation, and a stopping condition.
The algorithm's basic assumptions can be modified in various ways. For example, the search may not be conducted in the set of all feasible solutions but in a transformed set E(F). The neighborhood function N is problem-specific and can be defined in various ways. The stopping condition depends on the variant of the local search algorithm used. Some steps in the algorithm may be omitted or simplified.