The quality of the solutions to a combinatorial optimization problem is usually measured using a mathematical function, named objective function. This function is also used to guide heuristic procedures through the solution space, helping to detect promising search directions (i.e., it helps to compare the quality of different solutions). However, this task becomes very hard when many solutions are evaluated with the same value by the objective function. This fact commonly occurs in either max-min/min-max optimization problems. In those situations, a key strategy relies on the introduction of an alternative objective function. This function helps to determine which solution is more promising when the compared ones achieve the same value of the original objective function. In this paper we study the Cyclic Cutwidth Minimization Problem (CCMP), which is an example of a min-max optimization problem. Particularly, we analyze the influence in the search of using alternative objective functions within local search procedures. Also, we propose two alternative objective functions for the CCMP and compare its performance against a previously introduced one. Finally, we explored the combination of more than one alternative function.