This paper describes a case study of real-world simulation-based optimization of an engine manufacturing line. The optimization aims to maximize utilization of machines and at the same time minimize tied-up capital by manipulating 56 unique decision variables. A recently proposed metaheuristic algorithm that has achieved successful results in various problem domains called Cuckoo Search is used to perform the simulation-based optimization. To handle multiple objectives, an extension of the original Cuckoo Search algorithm based on the concept of Pareto optimality is proposed and used in the study. The performance of the algorithm is analyzed in comparison with the benchmark algorithm NSGA-II. Results show that the combinatorial nature of the optimization problem causes difficulties for the Cuckoo Search algorithm, and a further analysis indicates that the algorith might be best suited for contiunuous optimization problems.