吉林大学学报(工学版) ›› 2003, Vol. ›› Issue (4): 48-50.

Previous Articles     Next Articles

Chromosome with incomplete representation for Job shop scheduling problems

XU Bing, YU Jun-yi   

  1. College of Mechanical Science and Engineering, Jilin University, Changchun 130025, China
  • Received:2002-12-16

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

CLC Number: 

  • TB
[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.
[1] WU Wei-nan,CUI Nai-gang,GUO Ji-feng,ZHAO Yang-yang. Distributed integrated method for mission planning of heterogeneous unmanned aerial vehicles [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(6): 1827-1837.
[2] JIAO Yu-ling, ZHANG Peng, TIAN Guang-dong, XING Xiao-cui, ZOU Lian-hui. Slotting optimization of automated warehouse based on multi-population GA [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1398-1404.
[3] LI Qi-liang, CAO Guan-ning, LI Xuan, YANG Zhi-gang, ZHONG Li-yuan. Multi-parameters aerodynamic optimization of sedan [J]. 吉林大学学报(工学版), 2018, 48(3): 670-676.
[4] SUN Wen, WANG Qing-nian, WANG Jun-nian. Yaw-moment control of motorized vehicle for energy conservation during cornering [J]. 吉林大学学报(工学版), 2018, 48(1): 11-19.
[5] HU Yun-feng, WANG Chang-yong, YU Shu-you, SUN Peng-yuan, CHEN Hong. Structure parameters optimization of common rail system for gasoline direct injection engine [J]. 吉林大学学报(工学版), 2018, 48(1): 236-244.
[6] WAN Ping, WU Chao-zhong, LIN Ying-zi, MA Xiao-feng. Driving anger detection based on multivariate time series features of driving behavior [J]. 吉林大学学报(工学版), 2017, 47(5): 1426-1435.
[7] WANG Zhan-zhong, ZHAO Li-ying, CAO Ning-bo. Hazardous material transportation scheduling model based on mutilayer coding genetic algorithm [J]. 吉林大学学报(工学版), 2017, 47(3): 751-755.
[8] ZHENG Ming, ZHUO Mu-gui, ZHANG Shu-gong, ZHOU You, LIU Gui-xia. Reconstruction for gene regulatory network based on hybrid parallel genetic algorithm and threshold value method [J]. 吉林大学学报(工学版), 2017, 47(2): 624-631.
[9] ZHAO Yun-peng, YU Tian-lai, JIAO Yu-bo, GONG Ya-feng, SONG Gang. Damage identification method and factor evaluation for irregular-shaped bridge [J]. 吉林大学学报(工学版), 2016, 46(6): 1858-1866.
[10] CHEN Jin, LI Song-lin, SUN Zhen-ye, CHEN Gang. Integrated design of aerodynamic and structural performance for wind turbine dedicated airfoil [J]. 吉林大学学报(工学版), 2016, 46(6): 1940-1945.
[11] YIN Ming, ZHAN Yin-wei, PEI Hai-long. Co-sparse analysis operator learning for image fusion [J]. 吉林大学学报(工学版), 2016, 46(6): 2052-2058.
[12] WEI Li-ying, LI Ming-jun. Bus priority signal timing model considering the influence of traffic guidance [J]. 吉林大学学报(工学版), 2016, 46(3): 777-784.
[13] GUO Yu-quan, LI Xiong-fei, LIU Xin. Heuristic genetic algorithm associated with spectral analysis uncovering multi-scale community of complex networks [J]. 吉林大学学报(工学版), 2015, 45(5): 1592-1600.
[14] LI Di-fei, TIAN Di, HU Xiong-wei. Standard literature language model based on deep learning [J]. 吉林大学学报(工学版), 2015, 45(2): 596-599.
[15] LIU Lei, YANG Dong. Multi-objective genetic optimization algorithm for SLA-aware service composition problem [J]. 吉林大学学报(工学版), 2015, 45(1): 267-273.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!