重庆师范大学学报(自然科学版)
重慶師範大學學報(自然科學版)
중경사범대학학보(자연과학판)
JOURNAL OF CHONGQING NORMAL UNIVERSITY(NATURAL SCIENCE EDITION)
2013年
3期
5-8
,共4页
排序%单台机器%交货期指派%加工时间可控%资源分配
排序%單檯機器%交貨期指派%加工時間可控%資源分配
배서%단태궤기%교화기지파%가공시간가공%자원분배
讨论了带有交货期和工件的加工时间可控的单机排序问题.本文首先根据最优排序的性质确定了最优资源的分配方法,并将问题转化为指派问题,通过构造多项式时间算法确定最优排序.然后,本文将学习效应与加工时间可控问题结合,分别讨论了加工时间是线性资源函数和凸资源函数两种情况,证明了该类问题是多项式时间可解的.最后,讨论了一种特殊情况(学习因子是常数,加工时间是凸资源函数),给出了复杂性为O(nlogn)的算法,通过运行此算法确定最优资源分配量和工件的最优排序.
討論瞭帶有交貨期和工件的加工時間可控的單機排序問題.本文首先根據最優排序的性質確定瞭最優資源的分配方法,併將問題轉化為指派問題,通過構造多項式時間算法確定最優排序.然後,本文將學習效應與加工時間可控問題結閤,分彆討論瞭加工時間是線性資源函數和凸資源函數兩種情況,證明瞭該類問題是多項式時間可解的.最後,討論瞭一種特殊情況(學習因子是常數,加工時間是凸資源函數),給齣瞭複雜性為O(nlogn)的算法,通過運行此算法確定最優資源分配量和工件的最優排序.
토론료대유교화기화공건적가공시간가공적단궤배서문제.본문수선근거최우배서적성질학정료최우자원적분배방법,병장문제전화위지파문제,통과구조다항식시간산법학정최우배서.연후,본문장학습효응여가공시간가공문제결합,분별토론료가공시간시선성자원함수화철자원함수량충정황,증명료해류문제시다항식시간가해적.최후,토론료일충특수정황(학습인자시상수,가공시간시철자원함수),급출료복잡성위O(nlogn)적산법,통과운행차산법학정최우자원분배량화공건적최우배서.