Pre-salt oil exploration and production occurs in ultra-deep water regions, with complex conditions of equipament installation and operation. The wells connections, last stage before the production phase, is carried out by high-cost vessels, specially equipped for this purpose, known as PLSVs (Pipe Laying Support Vessels). This dissertation aims to develop a mathematical programming model to assign and schedule a PLSV fleet, in order to maximize the oil production during the planning horizon. For this purpose, a real problem faced by Petrobras was used, which allowed to extend the classic parallel machine approach, adding new constraints to the problem. To make the optimization feasible, a resolution method was created using the activities blocks concept. In order to reduce the resolution complexity, tests were performed using blocks composed by activities of wells close to each other. These strategies were effective, generating solutions with quality up to 21.5 percent higher (in oil production) when compared to the solution built by the problem specialists.