沈阳师范大学学报（自然科学版）
瀋暘師範大學學報（自然科學版）
침양사범대학학보（자연과학판）
JOURNAL OF SHENYANG NORMAL UNIVERSITY(NATURAL SCIENCE)
2012年
1期
7-11
,共5页
排序%工期窗口%线性退化%机器维护
排序%工期窗口%線性退化%機器維護
배서%공기창구%선성퇴화%궤기유호
排序问题是一类重要的组合最优化问题,它的深刻的实际背景和广阔的应用前景,引起了广泛的关注.排序问题的一大特点是模型繁多,适用于某一模型的算法,只要将模型的条件稍加变化,该算法就可能不适用.在经典排序问题中,通常假设工件的加工时间是不变的,然而,在许多实际问题中,工件的加工时间受到加工机器设备、工件本身、加工顺序等许多因素的影响而未必是恒定的.文章提出一类新型的排序问题——带有工期窗口和维护时间的线性退化工件的单机排序问题,目标是寻找:1)最优维护的开始时间；2)工期窗口的位置和大小；3)工件的最优排序使得提前完工、误工、工期窗口开始时间和窗口宽度的总费用最小.文章最后给出了这个问题的最优算法,其时间复杂性是O(n2 logn).
排序問題是一類重要的組閤最優化問題,它的深刻的實際揹景和廣闊的應用前景,引起瞭廣汎的關註.排序問題的一大特點是模型繁多,適用于某一模型的算法,隻要將模型的條件稍加變化,該算法就可能不適用.在經典排序問題中,通常假設工件的加工時間是不變的,然而,在許多實際問題中,工件的加工時間受到加工機器設備、工件本身、加工順序等許多因素的影響而未必是恆定的.文章提齣一類新型的排序問題——帶有工期窗口和維護時間的線性退化工件的單機排序問題,目標是尋找:1)最優維護的開始時間；2)工期窗口的位置和大小；3)工件的最優排序使得提前完工、誤工、工期窗口開始時間和窗口寬度的總費用最小.文章最後給齣瞭這箇問題的最優算法,其時間複雜性是O(n2 logn).
배서문제시일류중요적조합최우화문제,타적심각적실제배경화엄활적응용전경,인기료엄범적관주.배서문제적일대특점시모형번다,괄용우모일모형적산법,지요장모형적조건초가변화,해산법취가능불괄용.재경전배서문제중,통상가설공건적가공시간시불변적,연이,재허다실제문제중,공건적가공시간수도가공궤기설비、공건본신、가공순서등허다인소적영향이미필시항정적.문장제출일류신형적배서문제——대유공기창구화유호시간적선성퇴화공건적단궤배서문제,목표시심조:1)최우유호적개시시간；2)공기창구적위치화대소；3)공건적최우배서사득제전완공、오공、공기창구개시시간화창구관도적총비용최소.문장최후급출료저개문제적최우산법,기시간복잡성시O(n2 logn).
