上海第二工业大学学报
上海第二工業大學學報
상해제이공업대학학보
JOURNAL OF SHANGHAI SECOND POLYTECHNIC UNIVERSITY
2008年
1期
25-28
,共4页
排序%最优性%算法
排序%最優性%算法
배서%최우성%산법
经典排序论中使误工工件的个数为最少的单台机器排序问题,简称为误工问题,是排序论中最基本的问题之一.著名的Moore-Hodgson算法可以在时间O(n log,n)内得到误工问题的最优解.Pinedo在1995年对于Moore-Hodgson算法的最优性给出一个证明.虽然这个证明不严格,许多关键的地方交待不清,但是Hnedo证明的过程表明Moore-Hodgson算法得到解是所有最优解中不误工工件的总的加工时间最短的.这是一个很本质的性质,是其他所有的证明中没有提及的.本文补充和完善了Pinedo的证明.此外,对于推广的误工问题,例如,某些工件必须不误工的排序问题,或者工件的就绪时间不相同、但是与交货期有"一致性"关系的排序问题,或者工件的加工时间与工件的权有反向"一致性"关系的排序问题等,是否也有类似的性质?这是非常有意义的进一步研究方向.
經典排序論中使誤工工件的箇數為最少的單檯機器排序問題,簡稱為誤工問題,是排序論中最基本的問題之一.著名的Moore-Hodgson算法可以在時間O(n log,n)內得到誤工問題的最優解.Pinedo在1995年對于Moore-Hodgson算法的最優性給齣一箇證明.雖然這箇證明不嚴格,許多關鍵的地方交待不清,但是Hnedo證明的過程錶明Moore-Hodgson算法得到解是所有最優解中不誤工工件的總的加工時間最短的.這是一箇很本質的性質,是其他所有的證明中沒有提及的.本文補充和完善瞭Pinedo的證明.此外,對于推廣的誤工問題,例如,某些工件必鬚不誤工的排序問題,或者工件的就緒時間不相同、但是與交貨期有"一緻性"關繫的排序問題,或者工件的加工時間與工件的權有反嚮"一緻性"關繫的排序問題等,是否也有類似的性質?這是非常有意義的進一步研究方嚮.
경전배서론중사오공공건적개수위최소적단태궤기배서문제,간칭위오공문제,시배서론중최기본적문제지일.저명적Moore-Hodgson산법가이재시간O(n log,n)내득도오공문제적최우해.Pinedo재1995년대우Moore-Hodgson산법적최우성급출일개증명.수연저개증명불엄격,허다관건적지방교대불청,단시Hnedo증명적과정표명Moore-Hodgson산법득도해시소유최우해중불오공공건적총적가공시간최단적.저시일개흔본질적성질,시기타소유적증명중몰유제급적.본문보충화완선료Pinedo적증명.차외,대우추엄적오공문제,례여,모사공건필수불오공적배서문제,혹자공건적취서시간불상동、단시여교화기유"일치성"관계적배서문제,혹자공건적가공시간여공건적권유반향"일치성"관계적배서문제등,시부야유유사적성질?저시비상유의의적진일보연구방향.
