摘要
针对以最大完成时间为目标的无等待流水车间调度问题,提出了一种蚁群算法。首先,基于复杂度为O(n)的最大完成时间算法简化了适应值的计算;其次,基于当前最优解和轨迹密度的新解构造方法提高了求解质量;第三,基于快速插入邻域算法的多重插入移动提高了搜索效率;最后,基于典型算例的仿真试验,表明了所得调度算法的可行性和优越性。
An ant-colony heuristic algorithm was proposed for the No-Wait Flow Shop problem （NWFS） with makespan criterion. Firstly, a speed-up method with the computational complexity O（n） was developed to calculate the makespan of a permutation. Secondly, a permutation was constructed according to trail intensities and solution best so far, and a local search based on multi-insert, which performed several inserts simultaneously in a single iteration of algorithm, was employed to improve makespan of the permutation. Finally, computational tests based on the well known benchmark suites in the literature were conducted, and the computational results showed that the presented algorithm was effective in finding optimal or near-optimal solutions.
出处
《计算机集成制造系统》
EI
CSCD
北大核心
2007年第9期1801-1804,1815,共5页
Computer Integrated Manufacturing Systems
基金
国家自然科学基金重大资助项目(90104010)
博士后科学基金资助项目(20070410791)~~
