Empresas de exploração de petróleo e gás offshore frequentemente precisam lidar com problemas relacionados ao uso eficiente de seus recursos. Neste trabalho, abordamos um problema de programação de navios associado à logística offshore de petróleo e gás – O Problema de Programação de Embarcações do tipo Pipe-Laying support Vessel (PLSVSP). Essas embarcações são especialmente projetadas para realizar conexões de dutos entre poços de petróleo submarinos e plataformas de produção. A conexão de dutos é a última etapa a ser executada para permitir a drenagem do óleo e iniciar a produção em um poço. No PLSVSP, o objetivo é antecipar a conclusão de poços mais produtivos. O problema pode ser visto como uma variante de um problema de programação de lotes com máquinas paralelas idênticas e tempos de configuração não antecipados por família para minimizar o total weighted completion time. Nessa analogia, embarcações são as máquinas, poços são as tarefas e lotes são as viagens executadas por PLSVs, definindo quais poços devem ser conectados a cada saída do porto. Foram desenvolvidas diversas abordagens de otimização para resolver as variantes determinística e estocástica do problema. Para a variante determinística, desenvolvemos métodos híbridos e uma metaheurística capazes de melhorar as soluções desenvolvidas por formulações MIP puras e lidar com o PLSVSP. Para a variante estocástica, foi desenvolvida uma simheurística utilizando simulação de Monte Carlo incorporada, considerando incertezas nas durações das conexões e nas datas de chegada dos oleodutos no porto. Os resultados mostram uma melhora significativa no custo das soluções quando lidam com incertezas em comparação com soluções geradas por um método determinístico. O uso da simulação em uma estrutura metaheurística mostrou-se uma abordagem promissora, capaz de lidar com o problema estocástico, com pouco esforço computacional extra necessário.