计算机仿真
計算機倣真
계산궤방진
COMPUTER SIMULATION
2010年
4期
308-312
,共5页
优化调度%遗传算法%作业顺序决定的准备时间%总流程时间
優化調度%遺傳算法%作業順序決定的準備時間%總流程時間
우화조도%유전산법%작업순서결정적준비시간%총류정시간
Optimal scheduling%Genetic algorithm%Setup-time by job sequence%Total flow-time
提出了单机成组作业调度的改进遗传算法.优化目标为总流程时问的单机成组作业调度问题明显是NP-hard问题,此问题的多项式求解方法不能求取最优解,而一些启发式算法也只能求出此问题的次优解.为获得单机成组作业最优调度,通过采用整数实值编码,随机采样选择,单点交叉以及变异检查,设计了单机成组作业调度的改进遗传算法.仿真结果表明,算法能够找到此问题的最优解,其性能优于加权最短加工时间(WSPT)启发式算法.改进遗传算法能够灵活解决各种单目标调度及多目标调度问题.
提齣瞭單機成組作業調度的改進遺傳算法.優化目標為總流程時問的單機成組作業調度問題明顯是NP-hard問題,此問題的多項式求解方法不能求取最優解,而一些啟髮式算法也隻能求齣此問題的次優解.為穫得單機成組作業最優調度,通過採用整數實值編碼,隨機採樣選擇,單點交扠以及變異檢查,設計瞭單機成組作業調度的改進遺傳算法.倣真結果錶明,算法能夠找到此問題的最優解,其性能優于加權最短加工時間(WSPT)啟髮式算法.改進遺傳算法能夠靈活解決各種單目標調度及多目標調度問題.
제출료단궤성조작업조도적개진유전산법.우화목표위총류정시문적단궤성조작업조도문제명현시NP-hard문제,차문제적다항식구해방법불능구취최우해,이일사계발식산법야지능구출차문제적차우해.위획득단궤성조작업최우조도,통과채용정수실치편마,수궤채양선택,단점교차이급변이검사,설계료단궤성조작업조도적개진유전산법.방진결과표명,산법능구조도차문제적최우해,기성능우우가권최단가공시간(WSPT)계발식산법.개진유전산법능구령활해결각충단목표조도급다목표조도문제.
The improved genetic algorithm of single machine scheduling with job class setups is proposed.The problem of single machine scheduling with job class setups which optimal target is the total flow-time is obviously the NP-hard problem.Some polynomial solutions to the problem are not the best ones.And also,some heuristic algorithm can only work out the second best solution to this problem.To obtain the optimal single machine scheduling with job class setups,the improved genetic algorithm of single machine scheduling with job class setups is designed by using integer real valued code,stochastic sampling selection,single-point crossover and mutation checking.The simulation result indicates that the improved genetic algorithm not only can obtain the best optimal solution but also is better than the weighted shortest processing time first(WSPT) heuristic algorithm.By adopting the improved genetic algorithn,vgrious kinds of problems of single-goal and multi-goal scheduling can be solved easily.