Problemas em Scheduling estocástico do tipo flow-shop no-wait pertencentes à classe NP-completo são tratados neste trabalho em duas abordagens distintas. Na primeira, quando as realizações das variáveis aleatórias que descrevem os tempos de processamento das operações ocorrem "a priori", é apresentado um estudo do comportamento de heurísticas através de métodos estatísticos. Na segunda, quando as realizações das variáveis aleatórias ocorrem durante o processamento, é desenvolvido um estudo analítico da relação entre a probabilidade de um Schedule estocástico satisfazer a condição flow-shop no-wait e o intervalo de tempo decorrido entre duas tarefas adjacentes.