计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2005年
5期
53-55,59
,共4页
作业车间调度%NP-难%启发式%转换瓶颈
作業車間調度%NP-難%啟髮式%轉換瓶頸
작업차간조도%NP-난%계발식%전환병경
文章讨论了作业车间调度问题转换瓶颈算法的一个缺陷.转换瓶颈算法是解决作业车间调度最小makespan(完工时间)问题的很有效的启发式算法.它是基于反复的解决某些单机调度问题.然而在转换瓶颈算法中用Carlier算法解单机调度问题并不总能得到可行解,文中给出了一个反例证明了有产生不可行解的情况.另外,文章还以简洁的方法证明了转换瓶颈算法若用Schrage算法替代Carlier算法解单机调度问题不会产生不可行解.
文章討論瞭作業車間調度問題轉換瓶頸算法的一箇缺陷.轉換瓶頸算法是解決作業車間調度最小makespan(完工時間)問題的很有效的啟髮式算法.它是基于反複的解決某些單機調度問題.然而在轉換瓶頸算法中用Carlier算法解單機調度問題併不總能得到可行解,文中給齣瞭一箇反例證明瞭有產生不可行解的情況.另外,文章還以簡潔的方法證明瞭轉換瓶頸算法若用Schrage算法替代Carlier算法解單機調度問題不會產生不可行解.
문장토론료작업차간조도문제전환병경산법적일개결함.전환병경산법시해결작업차간조도최소makespan(완공시간)문제적흔유효적계발식산법.타시기우반복적해결모사단궤조도문제.연이재전환병경산법중용Carlier산법해단궤조도문제병불총능득도가행해,문중급출료일개반예증명료유산생불가행해적정황.령외,문장환이간길적방법증명료전환병경산법약용Schrage산법체대Carlier산법해단궤조도문제불회산생불가행해.
