一类资源负荷均衡问题的优化调度模型及其算法

• 论文 •

一类资源负荷均衡问题的优化调度模型及其算法

曹华军，刘飞，施金良

1.重庆大学制造工程研究所，重庆400030；2.重庆科技学院电子信息工程学院，重庆400050

出版日期:2005-05-15 发布日期:2005-05-25

Optimization scheduling model and its algorithm for a kind of resource workload balancing problems Optimization scheduling model and its algorithm for a kind of resource workload balancing problems Optimization scheduling model and its algorithm for a kind of resource workload balancing problems

CAO Hua-jun, LIU Fei, SHI Jin-liang CAO Hua-jun, LIU Fei, SHI Jin-liang CAO Hua-jun, LIU Fei, SHI Jin-liang

1. Inst. of Manu. Eng., Chongqing Univ., Chongqing400030, China；2. Coll. of Electronics Info. Eng.，Chongqing S & T Univ.,Chongqing400050, China

Online:2005-05-15 Published:2005-05-25

摘要/Abstract

摘要： 针对多个独立任务在多个不完全同等的处理机上处理时，处理机的最大负荷为最小的非抢先调度问题，建立了一类资源负荷均衡问题的优化调度模型。该模型引入0-1方案矩阵和时间负荷矩阵，分别描述了独立任务分配问题和负荷调度问题；针对部分处理机不能处理某一个独立任务的情形，假定其单位处理时间负荷趋于无穷大，从而避免优化调度中出现伪解。采用遗传算法对模型进行了求解。为了提高遗传算法的运算效率，采用整数方案描述和二进制间接编码的方法对方案染色体进行编码。最后，通过一个案例对模型和算法的有效性进行了验证。

关键词: 负荷均衡, 调度模型, 遗传算法

Abstract: A novel optimization scheduling model and its algorithm were developed for a kind of resource workload balancing problems, in which many independent tasks should be scheduled non-preemptively on non-identical multiprocessors to minimize the maximum workload. This model introduced a 0-1 scheme matrix and a workload matrix to describe task assignment and time load scheduling respectively. Under the circumstance that some processors can not process some specific tasks，infinite time load values were assumed to avoid false solutions. Genetic algorithm (GA) was applied to solve the scheduling model. To improve the efficiency of GA, the scheduling scheme chromosome was coded indirectly, in which the decimal digits were used to describe the assignment relationship of task sand processors, and the binary digits were used to code the decimal digits. Finally, a case study was presented to validate the model and its algorithm.

Key words: workload balancing, scheduling model, genetic algorithm

中图分类号:

TP31

曹华军，刘飞，施金良. 一类资源负荷均衡问题的优化调度模型及其算法[J]. .

CAO Hua-jun, LIU Fei, SHI Jin-liang CAO Hua-jun, LIU Fei, SHI Jin-liang CAO Hua-jun, LIU Fei, SHI Jin-liang. Optimization scheduling model and its algorithm for a kind of resource workload balancing problems Optimization scheduling model and its algorithm for a kind of resource workload balancing problems Optimization scheduling model and its algorithm for a kind of resource workload balancing problems[J]. .

[1]	陈年,金涛,王建民. 基于变异反馈的临床路径优化[J]. 计算机集成制造系统, 2021, 27(9): 2556-2564.
[2]	黎英杰,刘建军,陈庆新,毛宁. 多层级装配作业车间等量分批策略与调度算法[J]. 计算机集成制造系统, 2021, 27(8): 2307-2320.
[3]	王文中,张树生,余隋怀,陈登凯. 基于解构·重构思维的潜水器舱室布局优化[J]. 计算机集成制造系统, 2021, 27(7): 2045-2052.
[4]	王勇,周雪,刘永,许茂增. 基于车辆共享的多中心共同配送联盟优化[J]. 计算机集成制造系统, 2021, 27(6): 1820-1832.
[5]	张昊鹏,郭宇,汤鹏洲,黄少华,刘道元,李晗. 基于图像匹配的增强现实装配系统跟踪注册方法[J]. 计算机集成制造系统, 2021, 27(5): 1281-1291.
[6]	胡金昌,刘紫薇,马文凯,吴耀华. 考虑学习效应的单人作业车间多目标调度算法[J]. 计算机集成制造系统, 2021, 27(5): 1361-1370.
[7]	刘俊琦,张则强,王沙沙,曾艳清. 考虑不规则物流交互点的过道布置问题建模与优化[J]. 计算机集成制造系统, 2021, 27(4): 1155-1166.
[8]	裴小兵,李依臻. 新型混合改进遗传算法求解零等待流水车间调度问题[J]. 计算机集成制造系统, 2021, 27(3): 815-827.
[9]	李从东,章志伟,曹策俊,张帆顺. 复杂产品设计变更传播路径的多目标优选[J]. 计算机集成制造系统, 2021, 27(3): 842-856.
[10]	杨小明,徐子奇,金雯,舒帆. 复合拣选策略下堆垛机作业序列优化问题[J]. 计算机集成制造系统, 2021, 27(3): 933-942.
[11]	李丽丽,陈琨,高建民,李辉,冯增行,张建. 采用优化概率神经网络的质量异常识别方法[J]. 计算机集成制造系统, 2021, 27(10): 2813-2821.
[12]	薛玲玲. 作业车间调度的块结构邻域搜索遗传算法[J]. 计算机集成制造系统, 2021, 27(10): 2848-2857.
[13]	罗焕,陈浩杰,宋小欣,张剑. 带有缓存约束的作业车间调度求解方法[J]. 计算机集成制造系统, 2021, 27(10): 2880-2888.
[14]	张韵,钟慧超,张春江,李新宇,丛建臣. 基于机器学习的多策略并行遗传算法[J]. 计算机集成制造系统, 2021, 27(10): 2921-2928.
[15]	狄卫民,王然. 考虑多级设施中断的供应链选址—库存决策模型及优化算法[J]. 计算机集成制造系统, 2021, 27(1): 270-283.