应用数学学报
應用數學學報
응용수학학보
ACTA MATHEMATICAE APPLICATAE SINICA
2012年
4期
617-625
,共9页
单机最大完工时间排序%可控加工时间%恶化加工时间%0-1非线性整数规划%贪婪算法
單機最大完工時間排序%可控加工時間%噁化加工時間%0-1非線性整數規劃%貪婪算法
단궤최대완공시간배서%가공가공시간%악화가공시간%0-1비선성정수규화%탐람산법
本文研究加工时间可控并随开工时间简单线性增长的单机最大完工时间排序问题.该问题将加工时间可控排序和加工时间恶化排序两类研究连接到一起.通过比较技术证明了该问题存在满足以下性质的最优解:每个工件的加工时间或者完全压缩,或者完全不压缩；加工时间完全压缩的工件的顺序由一个工件参数和控制变量的函数的递增序给出,完全不压缩的工件在完全压缩的工件之后以任意序加工.通过将问题等价转换为0-1非线性整数规划问题,给出了单机排序问题的贪婪算法.
本文研究加工時間可控併隨開工時間簡單線性增長的單機最大完工時間排序問題.該問題將加工時間可控排序和加工時間噁化排序兩類研究連接到一起.通過比較技術證明瞭該問題存在滿足以下性質的最優解:每箇工件的加工時間或者完全壓縮,或者完全不壓縮；加工時間完全壓縮的工件的順序由一箇工件參數和控製變量的函數的遞增序給齣,完全不壓縮的工件在完全壓縮的工件之後以任意序加工.通過將問題等價轉換為0-1非線性整數規劃問題,給齣瞭單機排序問題的貪婪算法.
본문연구가공시간가공병수개공시간간단선성증장적단궤최대완공시간배서문제.해문제장가공시간가공배서화가공시간악화배서량류연구련접도일기.통과비교기술증명료해문제존재만족이하성질적최우해:매개공건적가공시간혹자완전압축,혹자완전불압축；가공시간완전압축적공건적순서유일개공건삼수화공제변량적함수적체증서급출,완전불압축적공건재완전압축적공건지후이임의서가공.통과장문제등개전환위0-1비선성정수규화문제,급출료단궤배서문제적탐람산법.
