系统管理学报
繫統管理學報
계통관이학보
JOURNAL OF SYSTEMS & MANAGEMENT
2010年
5期
584-588
,共5页
钟雪灵%王国庆%程明宝%李晓春
鐘雪靈%王國慶%程明寶%李曉春
종설령%왕국경%정명보%리효춘
单机排序%强制%空闲时间%最大提前完工时间
單機排序%彊製%空閒時間%最大提前完工時間
단궤배서%강제%공한시간%최대제전완공시간
讨论了带强制工期的n个工件在单机上加工,在允许机器空闲的条件下,使得最大提前完工时间最小.由于工件不允许延迟,问题可能会无可行排序.先讨论问题的可行性.如果问题可行,找出一个可行序列作为预排序列,并给出一个算法计算出每个工件尽可能迟的开工时间,而后判断预排序列是否为最优,如果不能直接确定为最优,则给出一个算法在多项式时间内尝试由预排序列开始,通过不断调整工件的次序来获得最优排序.
討論瞭帶彊製工期的n箇工件在單機上加工,在允許機器空閒的條件下,使得最大提前完工時間最小.由于工件不允許延遲,問題可能會無可行排序.先討論問題的可行性.如果問題可行,找齣一箇可行序列作為預排序列,併給齣一箇算法計算齣每箇工件儘可能遲的開工時間,而後判斷預排序列是否為最優,如果不能直接確定為最優,則給齣一箇算法在多項式時間內嘗試由預排序列開始,通過不斷調整工件的次序來穫得最優排序.
토론료대강제공기적n개공건재단궤상가공,재윤허궤기공한적조건하,사득최대제전완공시간최소.유우공건불윤허연지,문제가능회무가행배서.선토론문제적가행성.여과문제가행,조출일개가행서렬작위예배서렬,병급출일개산법계산출매개공건진가능지적개공시간,이후판단예배서렬시부위최우,여과불능직접학정위최우,칙급출일개산법재다항식시간내상시유예배서렬개시,통과불단조정공건적차서래획득최우배서.
