柔性作业调度的串并行模型对比与求解

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (9): 235-238.

柔性作业调度的串并行模型对比与求解

苏兆锋¹,邱洪泽²

1.鲁东大学管理学院，山东烟台 264025
2.山东大学计算机学院，济南 250061

收稿日期:2007-03-22 修回日期:2007-06-11 出版日期:2008-03-21 发布日期:2008-03-21
通讯作者: 苏兆锋

Symbiotic evolutionary algorithm for parallel job shop scheduling problem

SU Zhao-feng¹,QIU Hong-ze²

1.Management School of Ludong University，Yantai，Shandong 264025，China
2.Computer Science and Technology Academy，Shandong University，Ji’nan 250061，China

Received:2007-03-22 Revised:2007-06-11 Online:2008-03-21 Published:2008-03-21
Contact: SU Zhao-feng

摘要/Abstract

摘要： 作业处理中的柔性使得作业调度更为灵活，作业中操作的执行顺序满足拓扑排序是作业调度的前提。是否允许没有优先关系的操作在不同的机器上同时执行是区分串行和并行调度的条件。文中以共生进化算法求解一个复杂的作业调度模型为例，给出了算法实现串行调度和并行调度的具体区别，并给出了串行和并行调度的结果。结果表明，并行相对于串行对算法效率的提高与柔性大小相关，与作业的规模成反比。

关键词: 柔性, 并行, 作业调度, 共生进化算法

Abstract: Jobs with high production flexibility will lead to much more process plans and enhance the difficult of scheduling problem.The optimality of job shop scheduling depends on the result of process planning.Symbiotic Evolutionary Algorithm（SEA） is a good alternative for dealing with the problem usually.In this paper，a parallel Job Shop Scheduling Problem（JSSP） model is introduced on the basis of serial model.Traditional SEA is adjusted to deal with the parallel JSSP model.A complex job shop scheduling problems is selected as the test-bed problem for symbiotic evolutionary algorithm to deal with the two types JSSP.Compared with serial model，performance of the symbiotic evolutionary algorithm has relations with the type and scale of the parallel JSSP model.

Key words: flexible, parallel, job shop scheduling problem, symbiotic evolutionary algorithm

苏兆锋¹,邱洪泽². 柔性作业调度的串并行模型对比与求解[J]. 计算机工程与应用, 2008, 44(9): 235-238.

SU Zhao-feng¹,QIU Hong-ze². Symbiotic evolutionary algorithm for parallel job shop scheduling problem[J]. Computer Engineering and Applications, 2008, 44(9): 235-238.

[1]	谢锐强，张惠珍. 求解柔性作业车间调度问题的两段式狼群算法[J]. 计算机工程与应用, 2021, 57(7): 251-256.
[2]	李俊丽. Spark平台下类别数据互信息计算的并行化[J]. 计算机工程与应用, 2021, 57(7): 95-100.
[3]	石杰元，袁志勇，廖祥云，赵俭辉. 面向磁悬浮视触觉交互的多速率系统框架[J]. 计算机工程与应用, 2021, 57(5): 197-203.
[4]	唐蕊，焦继业，徐华昊. 面向嵌入式的卷积神经网络硬件加速器设计[J]. 计算机工程与应用, 2021, 57(4): 252-257.
[5]	杨鲁月，张树美，赵俊莉. 基于并行Gan的有遮挡动态表情识别[J]. 计算机工程与应用, 2021, 57(24): 168-178.
[6]	朱梦，闵卫东，张煜，段静雯. 基于HardSoftmax的并行选择核注意力[J]. 计算机工程与应用, 2021, 57(21): 95-101.
[7]	石宇强，田永政，张雨琦，石小秋. 运用含复杂网络结构的多种群遗传算法求解FJSP[J]. 计算机工程与应用, 2021, 57(2): 257-266.
[8]	冯凯，李婧. k元n方体网络的子网络可靠性[J]. 计算机工程与应用, 2021, 57(16): 83-89.
[9]	李健，张大伟，姜晓明，向立云. 并行化洪水演进模拟研究综述[J]. 计算机工程与应用, 2021, 57(13): 1-7.
[10]	孙明，陈昕. 面向卷积神经网络的硬件加速器设计方法[J]. 计算机工程与应用, 2021, 57(13): 77-84.
[11]	陈元文. MapReduce技术在物资调运与配载问题中的应用[J]. 计算机工程与应用, 2021, 57(12): 273-278.
[12]	张晓楠，姜帅，南婧雯. 半柔性覆盖的多配送中心路线优化问题研究[J]. 计算机工程与应用, 2021, 57(10): 225-232.
[13]	杨捷，吴素萍. 点云重建的并行算法[J]. 计算机工程与应用, 2020, 56(6): 213-219.
[14]	秦琴，梁承姬. 自动化码头考虑缓冲区的设备协调调度优化[J]. 计算机工程与应用, 2020, 56(6): 262-270.
[15]	叶颖诗，魏福义，蔡贤资. 基于并行计算的快速Dijkstra算法研究[J]. 计算机工程与应用, 2020, 56(6): 58-65.