A methods and systems for addressing parallel scheduling problem where a directed acyclic graph (dag) modeling t tasks and their dependencies needs to be executed on n unreliable workers. The methods and systems determine how workers get assigned to tasks (possibly in parallel and redundantly) throughout execution, so as to minimize expected completion time. Disclosed is a polynomial time method for the problem restricted to the case when dag width is at most a constant and the number of workers is also at most a constant.