A tabu search tutorial based on a real-world scheduling problem
Tóm tắt
We apply a tabu search method to a scheduling problem of a company producing cables for cars: the task is to determine on what machines and in which order the cable jobs should be produced in order to save production costs. First, the problem is modeled as a combinatorial optimization problem. We then employ a tabu search algorithm as an approach to solve the specific problem of the company, adapt various intensification as well as diversification strategies within the algorithm, and demonstrate how these different implementations improve the results. Moreover, we show how the computational cost in each iteration of the algorithm can be reduced drastically from O(n
3) (naive implementation) to O(n) (smart implementation) by exploiting the specific structure of the problem (n refers to the number of cable orders).
Tài liệu tham khảo
Blum C, Roli A (2003) Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Comput Surv 35: 268–308
Brucker P (2007) Scheduling algorithms, 5th edn. Springer, Berlin
Glover F (1977) Heuristics for integer programming using surrogate constraints. Decis Sci 8: 156–166
Glover F (1989) Tabu search—part I. INFORMS J Comput 1: 190–206
Glover F (1990) Tabu search—part II. INFORMS J Comput 2: 4–32
Glover F, Laguna M (1997) Tabu search. Kluwer, Boston
Tan KC, Burke E, Lee TH (2007) Feature cluster: evolutionary and meta-heuristic scheduling (guest editorial). Eur J Oper Res 177: 1852–2118