上海第二工业大学学报
上海第二工業大學學報
상해제이공업대학학보
JOURNAL OF SHANGHAI SECOND POLYTECHNIC UNIVERSITY
2009年
1期
12-16
,共5页
排序%误工%算法%复杂性
排序%誤工%算法%複雜性
배서%오공%산법%복잡성
误工排序问题是经典排序论中最基本的问题之一.1968年Moore提出解决这个问题的算法,可以在时间O(nlogn)内得到最优解.误工问题推广到以下情况:或者某些工件必须不误工;或者工件的加工时间与工件的权有反向一致性;或者工什的加工时间与工件的权具有反向一致性,并且某砦工件必须不误工等等.对于这些误工问题及其推广问题提出了多项式时间算法,证明了算法的最优性,并且证明了算法得到的最优解是所有最优解中不误工工件加工时间之和是最小的.
誤工排序問題是經典排序論中最基本的問題之一.1968年Moore提齣解決這箇問題的算法,可以在時間O(nlogn)內得到最優解.誤工問題推廣到以下情況:或者某些工件必鬚不誤工;或者工件的加工時間與工件的權有反嚮一緻性;或者工什的加工時間與工件的權具有反嚮一緻性,併且某砦工件必鬚不誤工等等.對于這些誤工問題及其推廣問題提齣瞭多項式時間算法,證明瞭算法的最優性,併且證明瞭算法得到的最優解是所有最優解中不誤工工件加工時間之和是最小的.
오공배서문제시경전배서론중최기본적문제지일.1968년Moore제출해결저개문제적산법,가이재시간O(nlogn)내득도최우해.오공문제추엄도이하정황:혹자모사공건필수불오공;혹자공건적가공시간여공건적권유반향일치성;혹자공십적가공시간여공건적권구유반향일치성,병차모채공건필수불오공등등.대우저사오공문제급기추엄문제제출료다항식시간산법,증명료산법적최우성,병차증명료산법득도적최우해시소유최우해중불오공공건가공시간지화시최소적.
