运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2013年
4期
56-62
,共7页
序列错位%截止日期%总延误时间%实际加工时间
序列錯位%截止日期%總延誤時間%實際加工時間
서렬착위%절지일기%총연오시간%실제가공시간
sequence disruption%deadline%total lateness%actual processing time
考虑了错位限制下的含有退化工件的重新排序问题,即工件的实际加工时间看作是工件开工时间的线性函数.重新排序就是在原始工件已经按照某种规则使目标函数达到最优时有—新工件集到达,新工件的安排使得原始工件重新排序进而产生错位.研究了最大序列错位和总序列错位限制下的退化工件最小化总延误时间问题,其最优排序的结构性质是使得原始工件集和新工件集中的工件是按加工率αj非减的序列排列,基于此通过分阶段排序和动态规划方法给出了两个问题的多项式时间的最优算法.
攷慮瞭錯位限製下的含有退化工件的重新排序問題,即工件的實際加工時間看作是工件開工時間的線性函數.重新排序就是在原始工件已經按照某種規則使目標函數達到最優時有—新工件集到達,新工件的安排使得原始工件重新排序進而產生錯位.研究瞭最大序列錯位和總序列錯位限製下的退化工件最小化總延誤時間問題,其最優排序的結構性質是使得原始工件集和新工件集中的工件是按加工率αj非減的序列排列,基于此通過分階段排序和動態規劃方法給齣瞭兩箇問題的多項式時間的最優算法.
고필료착위한제하적함유퇴화공건적중신배서문제,즉공건적실제가공시간간작시공건개공시간적선성함수.중신배서취시재원시공건이경안조모충규칙사목표함수체도최우시유—신공건집도체,신공건적안배사득원시공건중신배서진이산생착위.연구료최대서렬착위화총서렬착위한제하적퇴화공건최소화총연오시간문제,기최우배서적결구성질시사득원시공건집화신공건집중적공건시안가공솔αj비감적서렬배렬,기우차통과분계단배서화동태규화방법급출료량개문제적다항식시간적최우산법.