工程数学学报
工程數學學報
공정수학학보
CHINESE JOURNAL OF ENGINEERING MATHEMATICS
2008年
5期
829-842
,共14页
排序%柔性流水作业%同型机%批处理机%复杂性%近似算法
排序%柔性流水作業%同型機%批處理機%複雜性%近似算法
배서%유성류수작업%동형궤%비처리궤%복잡성%근사산법
本文仔细剖析混杂二阶段流水作业问题,其中第一阶段由m台同型机组成,第二阶段由一台批处理机M组成,并以最大完工时间Cmax为极小化目标函数.我们证明了该类问题除一种情况有多项式时间可解外,其余情况为(强)NP-hatd的.文中对所有(强)NP-hard情况均给出了近似算法并作了性能比分析.
本文仔細剖析混雜二階段流水作業問題,其中第一階段由m檯同型機組成,第二階段由一檯批處理機M組成,併以最大完工時間Cmax為極小化目標函數.我們證明瞭該類問題除一種情況有多項式時間可解外,其餘情況為(彊)NP-hatd的.文中對所有(彊)NP-hard情況均給齣瞭近似算法併作瞭性能比分析.
본문자세부석혼잡이계단류수작업문제,기중제일계단유m태동형궤조성,제이계단유일태비처리궤M조성,병이최대완공시간Cmax위겁소화목표함수.아문증명료해류문제제일충정황유다항식시간가해외,기여정황위(강)NP-hatd적.문중대소유(강)NP-hard정황균급출료근사산법병작료성능비분석.
