主要讨论了恶化工件具有p-s-d安装时间的非同类机排序问题.工件的实际加工时间与开工时间有关,安装时间是依赖于所在机器上已加工完的工件的加工时间的简单函数,即p-s-d形式.本文所考虑的问题是如何确定工件在非同类机上的加工顺序使得所有工件的总完工时间最小.在每台机器上加工的工件数确定的情况下,将该排序问题转化为一个指派问题.由于每台机器上加工的工件数可在O(nm-1)时间内确定,而指派问题能在0(n3)时间内解决,故本文证明了所提出的排序问题是多项式时间可解的.本文还讨论了该排序问题的两种特殊情形.情形一,工件在不同机器上的恶化和安装系数是相同的,即δi=δ,b1=b,工件j在不同机器上的正常加工时间为aj,不依赖于所在的机器,此时相当于所有工件在同型平行机上加工.情形二,在情形一的基础上又考虑了工件不存在恶化,即δi=0.对这两种情形下的排序问题,本文由降序算法得到最优序.