Cloud computing has gained widespread acceptance in both the scientific and commercial community. Mathematical optimization is one of the domains, which benefit from cloud computing by using additional computing power for optimization problems to reduce the calculation time. Of course this is also true for our field of metaheuristic optimization. Metaheuristics provide powerful methods to solve a wide range of optimization problems and may be used as a foundation for a data analysis service. Due to the deficiency of an agreed-upon reference architecture it is quit cumbersome to compare existing solutions regarding different kinds of aspects (e.g. scalability, custom extensions, workflow, etc.). Besides the usual user working with an optimization service we also have those who are responsible for architecting and implementing these systems. The lack of a list of requirements and any formal reference architecture makes it even harder to improve those systems. For that reason we have raised the following questions: i) what are the requirements, ii) what are the commonalities of existing optimization software, and iii) can we deduce a reference architecture for a cloud-based optimization service? This paper presents a comprehensive analysis of current research projects and important requirements in the context of optimization services, which then leads to the definition of a reference architecture and forms the base of any further evaluation. We also present our own hybrid cloud-based optimization service (OaaS), which is built upon the PaaS-approach of Windows Azure. OaaS defines a generic and extensible service which can be adapted to support custom optimization scenarios.