工业工程与管理
工業工程與管理
공업공정여관리
INDUSTRIAL ENGINEERING AND MANAGEMENT
2011年
3期
68-74
,共7页
时间窗维护%学习效应%虚拟维护%LPT-SPT%P-VNS
時間窗維護%學習效應%虛擬維護%LPT-SPT%P-VNS
시간창유호%학습효응%허의유호%LPT-SPT%P-VNS
解决了考虑多阶段时间窗(Time-winndow)[u,v]周期性维护的情况下,因工件加工存在学习效应,加工时间可变时目标函数为最小makespan的单机调度问题.证明了维护次数θ的上界θUB,首次提出虚拟维护的概念,在此基础上给出了两阶段模型来描述该问题.然后,本文给出了多项式时间复杂度的启发式算法,LPT-SPT算法；以及将初始解群和接受概率等概念引入变领域搜索算法(Variable Neighborhood Search,VNS),提出了改进的VNS算法,基于群的变领域搜索(Populated Variable Neighborhood Search,P-VNS).最后,大量的实例验证了LPT-SPT算法和P-VNS有着较高的时间效率和很好的解精度.
解決瞭攷慮多階段時間窗(Time-winndow)[u,v]週期性維護的情況下,因工件加工存在學習效應,加工時間可變時目標函數為最小makespan的單機調度問題.證明瞭維護次數θ的上界θUB,首次提齣虛擬維護的概唸,在此基礎上給齣瞭兩階段模型來描述該問題.然後,本文給齣瞭多項式時間複雜度的啟髮式算法,LPT-SPT算法；以及將初始解群和接受概率等概唸引入變領域搜索算法(Variable Neighborhood Search,VNS),提齣瞭改進的VNS算法,基于群的變領域搜索(Populated Variable Neighborhood Search,P-VNS).最後,大量的實例驗證瞭LPT-SPT算法和P-VNS有著較高的時間效率和很好的解精度.
해결료고필다계단시간창(Time-winndow)[u,v]주기성유호적정황하,인공건가공존재학습효응,가공시간가변시목표함수위최소makespan적단궤조도문제.증명료유호차수θ적상계θUB,수차제출허의유호적개념,재차기출상급출료량계단모형래묘술해문제.연후,본문급출료다항식시간복잡도적계발식산법,LPT-SPT산법；이급장초시해군화접수개솔등개념인입변영역수색산법(Variable Neighborhood Search,VNS),제출료개진적VNS산법,기우군적변영역수색(Populated Variable Neighborhood Search,P-VNS).최후,대량적실례험증료LPT-SPT산법화P-VNS유착교고적시간효솔화흔호적해정도.
