In this paper, we focus on a scenario in which a company or a set of companies conforming a supply network must deliver a complex product (service) composed of several components (tasks) to be processed on a set of parallel flow-shops with a common deadline. Each flow-shop represents the manufacturing of an independent component of the product, or the set of activities of the service. We assume that the processing times are random variables following a given probability distribution. In this scenario, the product (service) is required to be finished by the deadline with a user-specified probability, and the decision-maker must decide about the starting times of each component/task while minimizing one of the following alternative goals: (a) the maximum completion time; or (b) the accumulated deviations with respect to the deadline. A simheuristic-based methodology is proposed for solving this problem, and a series of computational experiments are performed.