随着经济的快速增长，很多产品的运作生产，往往需要不同的工艺流程。文章考虑了带有时间惩罚的有向串并联图最小任务分配问题和带有时间惩罚的有向串并联图最小跨度任务分配问题，根据有向串并联任务优先图结构构建有向串并联分配图。在此基础上，文章应用时间复杂性更小的特殊结构最短路算法以及收缩方法，分别设计了两个时间复杂性为O（nm2k2）的多项式算法来解决带时间惩罚的有向串并联图任务分配问题，其中n为任务数量，m为处理器数量，k是时间段限制数量。