恶化工件具有p-s-d安装时间的非同类机排序(运筹学与控制论)

王要讨论了恶化工件具有D-S-d安装时间的非同类机排序问题。工件的实际加工时间与开工时间有关，安装时间异依赖于所在机器上已加工完的工件的加工时间的简单函数，即D-S-d形式。本又所考虑的问}f如何确定工件在非同类机上的加工顺序使得所有工件的弥完工时间最小。在每台机器上加工的工件数确定的情况下，将该排序问题转化为一个指派问题。由于每台机器上加工的工件数可在*时间内确定，而指派问颗O（n3）时间内解决，故本又证明了所提出的排序问是多项式时间可解的。本又还讨论了该排序问题的两种特殊情形。情形一，工件在不同机器上的恶化和安装系数是相同的，即*，工件j在不同机器上的正常加工时间为aj,不依赖于所在的机器，此时相当于所有工件在同型平行机上加工。情形二，在情形一的基础上又考虑了工件不存在恶化，即*对孩两种情形下的排序问颗，本又由降序算法得到最优序。（注*表示公式，见正文）