In order to develop an offshore maintenance support system, this work presents a model for constrained combinatorial problems: CPSO(plus). This model is a combination of two models, the PSO(plus), which presented good results in problems with constrains, and the CPSO, which is an adaptation of PSO for application in combinatorial problems. The proposed model has been adapted to solve the complex problem of defining the best sequence of offshore activities and allocated staff so as to maximize service provider profitability within three months while respecting all service completion time constraints and specific offshore work constraints. To evaluate the performance of this new model in solving the proposed problem, two CPSO(plus) variants were evaluated against the literature model, CPSO, in six proposed simulation cases. It is concluded from the results of the simulations that the CPSO(plus) model with reduced initialization outperforms other evaluated models with respect to execution time and solutions to given problem.