在制造业中,处理机由于发生故障或进行维护、保养等原因,导致处理机不可用,产生一些不可用区间,并且工件的实际加工时间与开始加工时间有关。　　本文研究的是带有不可用区间和退化效应的单机无界并行批排序问题。在并行批处理机中,相同一批中的工件其开始加工时间相同,完工时间也相同,并且批一旦开始加工就不可以中断;每一批的加工时间都等于这批工件中加工时间的最大者;同批中的工件完工时间都相同,为这批的完工时间。文中批处理机为无界模型,也就是同批中工件数没有上界。本文分别给出了求解极小化最大费用及极小化总费用的拟多项式时间算法。特别当k固定、目标函数为误工工件数时,该问题为多项式时间可解的。我们还讨论了工件带有不同释放时间时,目标函数为最大完工时间的排序问题，当工件的加工时间分别为pj=aj+bt和pj=bjt时，给出了对应的多项式时间的动态规划算法。　　具体研究的内容概括如下：1．对于工件的加工时间为pj=aj+bt的情况,讨论了带有不可用区间的无界并行批排序问题。　　(1)对于目标函数为最大费用的排序问题,我们给出了一个拟多项式动态规划最优算法。　　(2)对于目标函数为总费用的排序问题,我们给出了一个拟多项式时间的动态规划算法。特别当k固定时,对于目标函数为误工工件数时,该问题为多项式时间可解的。　　(3)研究了工件有不同释放时间的排序问题,其目标函数为最大完工时间。我们给出了求解此问题的多项式时间的动态规划算法。　　2.对于工件的加工时间为pj=bjt、带有不可用区间的无界并行批排序问题,研究了工件带有不同释放时间,目标函数为最大完工时间的问题,给出了一个多项式时间的动态规划算法。