柔性流水作业排序问题的贪心算法求解

J4 ›› 2009, Vol. 27 ›› Issue (06): 585-.

柔性流水作业排序问题的贪心算法求解

李晓峰¹|赵海¹|杜洪军²|刘小勇^3

1东北大学信息科学与工程学院, 沈阳 110004；2中国移动通信集团吉林有限公司业务支撑中心|长春 130021；
3北京邮电大学人文学院|北京 100876

出版日期:2009-11-20 发布日期:2009-12-18
通讯作者: 李晓峰（1962— ），男，沈阳人，东北大学博士研究生，主要从事金融计算机安全研究 E-mail:xfli@chinaums.com
作者简介:李晓峰（1962— ）|男|沈阳人|东北大学博士研究生|主要从事金融计算机安全研究|(Tel)86-13818086663(E-mail)xfli@chinaums.com；赵海（1959— ）|男|沈阳人|东北大学教授|博士生导师|主要从事计算机网络通信研究|(Tel)86-13904045486(E-mail)zhaoh@mail.neu.edu.cn。
基金资助:
国家863计划基金资助项目(2002AA145050)；教育部高等学校科技创新工程基金资助项目(708026)

Greedy Algorithm Solution of Flexible Flow Shop Scheduling Problem

LI Xiao-feng¹, ZHAO Hai¹, DU Hong-jun²,LIU Xiao-yong^3

1College of Information Science and Engineering, Northeast University, Shenyang 110004,China；2Business Supporting Center,China Mobile Group Jilin |Company Limited| Changchun 130021,China；3School of Humanities,Law and Economics,Beijing University of Posts and Telecommunications,Beijing 100876,China

Online:2009-11-20 Published:2009-12-18

摘要/Abstract

摘要：

柔性流水作业排序问题是一类复杂的车间作业调度问题。针对通常情况下调度问题求解困难的问题，给出了求解柔性流水作业排序问题近似解的贪心算法，并对其性能进行了分析测试。结果表明，虽然该贪心算法求出的近似解与最优解相比有一定误差，但由于其时间复杂度较小，因此对求解车间作业调度问题仍有一定的现实意义。

关键词: 柔性流水作业, 车间作业调度, 贪心算法

Abstract:

Flexible flow shop scheduling problem is a complex job shop scheduling problem. And the problem has polynomial difficulty. Most of the other cases the problem has NP difficulty. In order to solve the problem, a greedy algorithm to solve flexible flow shop scheduling is given, and the capability of the algorithm is evaluated. Even the approximate result solved by the greedy algorithm has a certain error with the optimal result; however, it has small time complexity, so it still makes sense to the job shop scheduling problem solving.

Key words: flexible flow shop, job shop scheduling, dreedy algorithm

中图分类号:

TP391

李晓峰|赵海|杜洪军|刘小勇. 柔性流水作业排序问题的贪心算法求解[J]. J4, 2009, 27(06): 585-.

LI Xiao-feng, ZHAO Hai, DU Hong-jun,LIU Xiao-yong. Greedy Algorithm Solution of Flexible Flow Shop Scheduling Problem[J]. J4, 2009, 27(06): 585-.

[1]	刘威, 路来君, 徐昊, 曹延波. 基于云计算的G⁴ICCS系统结构设计[J]. J4, 2013, 31(2): 187-190.
[2]	张惠琳, 孙承志, 刘铭. 云计算构架下的区域物流公共信息平台建设[J]. J4, 2013, 31(2): 215-218.
[3]	王征, 熊永忠, 张佳琳. 微观管理过程仿真与人工心理应用研究[J]. J4, 2012, 30(6): 585-590.
[4]	胡阳明, 周大可, 鹿乐, 杨欣. 基于形变模型的三维人脸快速重建改进算法[J]. J4, 2012, 30(6): 605-609.
[5]	田澍, 段锦, 祝勇, 黄存令. 基于十字模板匹配的靶场目标检测方法[J]. J4, 2012, 30(6): 655-659.
[6]	李雷. 基于电信行业小波神经网络模型的应用[J]. J4, 2012, 30(6): 599-604.
[7]	姜占才, 杨林. 语音模糊特征提取及码本训练算法[J]. J4, 2012, 30(3): 279-284.
[8]	龙波, 柳继. 局域网中P2P即时通讯工具的设计与实现[J]. J4, 2012, 30(3): 315-320.
[9]	李蕴奇. 基于可变形物体的碰撞检测算法[J]. J4, 2012, 30(3): 321-326.
[10]	李蕴奇. 彩色图像增强的改进算法[J]. J4, 2012, 30(1): 83-87.
[11]	贺新颖, 王剑钢, 杨旭. 用于社区医院的无线心电监护系统设计[J]. J4, 2011, 29(6): 535-541.
[12]	唐庭阁, 杨欣, 周大可, 姜斌. 基于形态学边缘保持的自适应超分辨率重建[J]. J4, 2011, 29(5): 444-450.
[13]	刘颖, 秦贵和. 基于iOS远程控制应用的设计与实现[J]. J4, 2011, 29(5): 451-456.
[14]	姚劲勃, 余宜诚, 于卓尔, 李惠民. 基于PCA降维协同过滤算法的改进[J]. J4, 2011, 29(5): 494-497.
[15]	阚君满. 基于改进哈夫曼编码的全文索引结构压缩算法[J]. J4, 2011, 29(5): 473-476.