复杂并行机调度问题基于分解的优化算法 | |
郝井华 ; 刘民 ; 刘屹洲 ; 吴澄 ; 张瑞 ; HAO Jing-hua ; LIU Min ; LIU Yi-zhou ; WU Cheng ; ZHANG Rui | |
2010-06-09 ; 2010-06-09 | |
关键词 | 并行机 调度 进化规划 特殊工艺约束 优化 parallel machine scheduling evolutionary programming eligibility constraint optimization TS10 |
其他题名 | Decomposition-based Optimization Algorithm for Complex Parallel Machine Scheduling Problems |
中文摘要 | 针对纺织生产过程中广泛存在的带特殊工艺约束的大规模并行机调度问题,提出了一种基于分解的优化算法。首先将原调度问题分解为机台选择和工件排序两个子问题,然后针对机台选择子问题提出一种进化规划算法,并采用一种具有多项式时间复杂度的最优算法求解工件排序子问题,以得到问题特征信息(即每台机器对应拖期工件数的最小值),该问题特征信息用以指导进化规划算法的迭代过程。不同规模并行机调度问题的数值计算结果及实际制造企业应用效果表明,本文提出的算法是有效的。; A decomposition-based optimization algorithm is presented for solving larger scale parallel machine scheduling problems with the objective of minimizing the total number of tardy jobs and machine eligibility restriction in textile manufacturing process.Firstly,the whole scheduling problem is decomposed into two sub-problems: the machine selection problem and the job sequencing problem.Then,an evolutionary programming algorithm is proposed to solve the machine selection problem,and a polynomial optimization algorithm is adopted to solve the job sequencing problem in order that the problem characteristic information(the minimal value of the total number of tardy jobs on each machine),which is used to guide the search process of evolutionary programming,can be obtained.Numerical computational results of different scale parallel machine scheduling problems and practical application effects show that the proposed algorihm is effective.; 国家973重点基础研究计划资助项目(2002CB312200); 国家自然科学基金资助项目(60004010,60274045,60443009) |
语种 | 中文 ; 中文 |
内容类型 | 期刊论文 |
源URL | [http://hdl.handle.net/123456789/57478] |
专题 | 清华大学 |
推荐引用方式 GB/T 7714 | 郝井华,刘民,刘屹洲,等. 复杂并行机调度问题基于分解的优化算法[J],2010, 2010. |
APA | 郝井华.,刘民.,刘屹洲.,吴澄.,张瑞.,...&ZHANG Rui.(2010).复杂并行机调度问题基于分解的优化算法.. |
MLA | 郝井华,et al."复杂并行机调度问题基于分解的优化算法".(2010). |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论