Determining the control parameters for sheet metal press lines is a large scale and complex optimisation problem. These control parameters determine velocities, time constants, and cam values of critical interactions between the equipment. The complexity of this problem is due to the nonlinearities and high dimensionality. Classical optimisation techniques often underperform in solving this kind of problems within a practical timeframe. Therefore, specialised techniques need to be developed for these problems. An existing approach is simulation-based optimisation, which is to use a simulation model to evaluate the trial solutions during the optimisation. In this paper, an efficient simulation-based optimisation algorithm for large scale and complex problems is proposed. The proposed algorithm extends the cooperative coevolutionary algorithm, which optimises subproblems separately. Hence, the optimisation problem must be decomposed into subproblems that can be evaluated separately. To optimise the subproblems, the proposed algorithm allows using embedded deterministic algorithms, next to stochastic genetic algorithms, getting the flexibility of using either type. It also includes a constructive heuristic that creates good initial feasible solutions to expedite the optimisation. The extension enables solving complex, computationally expensive problems efficiently. The proposed algorithm has been applied on an automated sheet metal press line from the automotive industry. The objective is to find control parameters that maximise the line’s production rate. The results show that the proposed algorithm manages to find optimal control parameters efficiently within the practical timeframe. This is a step forward in press line optimisation since to the authors’ knowledge this is the first time a press line has been optimised efficiently in this way.