车间作业调度问题的染色体非完整表示方法

摘要/Abstract

摘要： 提出了一种用于解决车间作业调度问题的新的遗传染色体编码方法———非完整编码。其特征是基因数少于工序数。剩余基因采用简单的启发式规则方法进行解码。考证结果表明,非完整表示方法能够在合理的时间内得到临近最优解,通过删除高冗余和很少有实际意义的尾部基因,可以使遗传更有效。

关键词: 车间作业调度, 染色体, 基因, 编码, 遗传算法

Abstract: We present genetic algorithm with an incomplete representation and apply it to the Job-shop scheduling problems.The important characteristic lies in that the number of genes is less than the number of operations.The rest of the schedule is completed by a simple heuristic rule.The results imply that the nearly best solution can be found in a national time interval by incomplete genes presentation.And incomplete genes presentation make the genetic algorithms more efficient by canceling high redundancy at the tail of the chromosome and little significance of rear genes.

Key words: Job-shop scheduling problem, chromosome, genes, representation, genetic algorithm

中图分类号:

徐兵, 于骏一. 车间作业调度问题的染色体非完整表示方法[J]. 吉林大学学报(工学版), 2003, (4): 48-50.

XU Bing, YU Jun-yi. Chromosome with incomplete representation for Job shop scheduling problems[J]. 吉林大学学报(工学版), 2003, (4): 48-50.

参考文献

[1] GAREY M,JOHNSON D,SETHI R.The complexity of flowshop and jobshop scheduling［J］.Mathematics of Operations Research,1976,1:117-129.
[2] DAVIS L.Job-shop scheduling with genetic algorithm[A].Proc.of the 1st Int.Conf.on Genetic Algorithms［C］,Lawrence Erlbaum Associates,1985:136-140.
[3] CHENG R,GEN M.A tutorial survey of job-shop scheduling problems using genetic algorithms-I.Representation［J］.Computer Ind.Eng.,1996,30(4):983-997.
[4] DORNDORF U,PESCH E.Evolution based learning in a job-shop environment［J］.Computers and Operations Research,1995,22:25-40.
[5] BEAN J.Genetic algorithms and random keys for sequencing and optimization［J］.ORSA Journal on Computing,1994,6(2):154-160.
[6] BIERWIRTH C.A generalized permutation approach to job-shop scheduling with genetic algorithms［J］.OR Spektrum,1995,17(2-3):87-92.
[7] KUBOTA A.Study on optimal scheduling for manufacturing system by genetic algorithms［D］.Ashikaga Institute of Technology,Ashikaga,Japan,1995.

相关文章 15

[1]	吴蔚楠,崔乃刚,郭继峰,赵杨杨. 多异构无人机任务规划的分布式一体化求解方法[J]. 吉林大学学报(工学版), 2018, 48(6): 1827-1837.
[2]	焦玉玲, 张鹏, 田广东, 邢小翠, 邹连慧. 基于多种群遗传算法的自动化立体库货位优化[J]. 吉林大学学报(工学版), 2018, 48(5): 1398-1404.
[3]	刘富, 兰旭腾, 侯涛, 康冰, 刘云, 林彩霞. 基于优化k-mer频率的宏基因组聚类方法[J]. 吉林大学学报(工学版), 2018, 48(5): 1593-1599.
[4]	李启良, 曹冠宁, 李璇, 杨志刚, 钟立元. 三厢轿车多参数气动优化[J]. 吉林大学学报(工学版), 2018, 48(3): 670-676.
[5]	赵宏伟, 刘宇琦, 特日根, 陈长征, 臧雪柏. 基于有限序列的压缩新算法[J]. 吉林大学学报(工学版), 2018, 48(3): 882-886.
[6]	王柯, 刘富, 康冰, 霍彤彤, 周求湛. 基于沙蝎定位猎物的仿生震源定位方法[J]. 吉林大学学报(工学版), 2018, 48(2): 633-639.
[7]	孙文, 王庆年, 王军年. 基于横摆力矩控制的电动轮汽车转弯节能控制[J]. 吉林大学学报(工学版), 2018, 48(1): 11-19.
[8]	胡云峰, 王长勇, 于树友, 孙鹏远, 陈虹. 缸内直喷汽油机共轨系统结构参数优化[J]. 吉林大学学报(工学版), 2018, 48(1): 236-244.
[9]	范敏, 韩琪, 王芬, 宿晓岚, 徐浩, 吴松麟. 基于多层次特征表示的场景图像分类算法[J]. 吉林大学学报(工学版), 2017, 47(6): 1909-1917.
[10]	周放, 宋传学, 梁天唯, 肖峰. 采用NSGA-II算法的车载复合电源参数匹配[J]. 吉林大学学报(工学版), 2017, 47(5): 1336-1343.
[11]	王占中, 赵利英, 曹宁博. 基于多层编码遗传算法的危险品运输调度模型[J]. 吉林大学学报(工学版), 2017, 47(3): 751-755.
[12]	韩伟良, 葛建华, 马波, 高洋. 符号干扰多径信道下可达信道容量的预编码方案[J]. 吉林大学学报(工学版), 2017, 47(3): 981-987.
[13]	郑明, 卓慕瑰, 张树功, 周柚, 刘桂霞. 基于混合并行遗传算法和阈值限定法的基因调控网络构建[J]. 吉林大学学报(工学版), 2017, 47(2): 624-631.
[14]	叶方, 苏春霞, 李一兵, 刘君. 信道时延条件下的CoMP系统有限反馈比特分配[J]. 吉林大学学报(工学版), 2017, 47(2): 661-669.
[15]	李晓妮, 陈绵书, 桑爱军, 曲昭伟. 质量可伸缩高性能视频编码中增强层快速算法[J]. 吉林大学学报(工学版), 2017, 47(2): 670-676.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed