上海大学学报(自然科学版)
上海大學學報(自然科學版)
상해대학학보(자연과학판)
JOURNAL OF SHANGHAI UNIVERSITY (NATURAL SCIENCE EDITION)
2009年
4期
380-387
,共8页
排序%流水作业%同型机%批处理机
排序%流水作業%同型機%批處理機
배서%류수작업%동형궤%비처리궤
讨论一类二阶段流水作业问题,其中第一阶段由m台同型机组成,第二阶段为I台批处理机,目标函数是最小化各工件完工时间之和.工件在同型机和批处理机上分别有相同加工时间的情况下,给出了计算量为O(n3)的最优算法.相应工件在同型机上有相同加工时间,但在批处理机上具有任意加工时间的情况下,指出其强NP-hard后给出了近似算法,并作了性能比分析.
討論一類二階段流水作業問題,其中第一階段由m檯同型機組成,第二階段為I檯批處理機,目標函數是最小化各工件完工時間之和.工件在同型機和批處理機上分彆有相同加工時間的情況下,給齣瞭計算量為O(n3)的最優算法.相應工件在同型機上有相同加工時間,但在批處理機上具有任意加工時間的情況下,指齣其彊NP-hard後給齣瞭近似算法,併作瞭性能比分析.
토론일류이계단류수작업문제,기중제일계단유m태동형궤조성,제이계단위I태비처리궤,목표함수시최소화각공건완공시간지화.공건재동형궤화비처리궤상분별유상동가공시간적정황하,급출료계산량위O(n3)적최우산법.상응공건재동형궤상유상동가공시간,단재비처리궤상구유임의가공시간적정황하,지출기강NP-hard후급출료근사산법,병작료성능비분석.