窗时排序的计算机搜索算法  

Computer Search Algorithms for Time Window Scheduling

作　　者：魏小兰[1] 沈灏[1] 

机构地区：[1]杭州电子科技大学理学院,浙江杭州310018

出　　处：《杭州电子科技大学学报（自然科学版）》2006年第4期91-94,共4页Journal of Hangzhou Dianzi University：Natural Sciences

基　　金：国家自然科学基金(10371028);浙江省教育厅重点项目(20030622);浙江省教育厅科研项目(20050494)

摘　　要：该文讨论按期完工工件数最大化的窗时排序问题。文章首先提出一个基于EDD序的枚举算法,很大程度降低了纯枚举算法的计算复杂性。然后以改进的枚举法作基础构造了一个启发式算法———遗传算法求解该问题。算法采用0-1编码,基于EDD序规则调整各个工件的排列顺序。该算法在处理大规模的单机排序问题时,能够在较短的时间内得到近似最优解。实例计算证明,该遗传算法近似程度好,可操作性强,可以在实际应用中推广。This paper mainly concerns scheduling problems relate to due windows to maximize non-delay jobs. Algorithms is designed for single machine scheduling to maximize non - delay jobs within due windows. An improved enumerate algorithm based on EDD ruler is proposed and the complexity of algorithm is largely reduced. Based on above result we construct a genetic algorithm. 0- 1 coding is used in the algorithm, and the sequence is adjusted according to the improved enumerate algorithm. The algorithm gives an approximation solution in very short time even if the amount of the work - pieces is very large. Examples show that genetic algorithm works very well.

关 键 词：窗时排序 装箱问题 启发式算法 遗传算法 

分 类 号：O212[理学—概率论与数理统计]