CAJ | 학술논문

提出了单机成组作业调度的改进遗传算法.优化目标为总流程时问的单机成组作业调度问题明显是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.