New scheduling type applied to solving job-shop scheduling problem

被引：2

作者：

Zhang, Chaoyong ^{[1
]}

Guan, Zailin ^{[1
]}

Liu, Qiong ^{[1
]}

Shao, Xinyu ^{[1
]}

Li, Peigen ^{[1
]}

机构：

[1] State Key Laboratory of Digital Manufacturing Equipment and Technology, Huazhong Univ. of Sci. and Technol.

来源：

Jixie Gongcheng Xuebao/Chinese Journal of Mechanical Engineering | 2008年 / 44卷 / 10期

关键词：

Due-dates scheduling; Earliness/Tardiness scheduling problem; Genetic algorithm; Job-shop scheduling;

D O I：

10.3901/JME.2008.10.024

中图分类号：

学科分类号：

摘要：

An improved genetic algorithm (GA) is presented for the job-shop scheduling problem, and the chromosome representation of the problem is based on the operation-based representation. In view of the limitation of the traditional types of scheduling, a new type of scheduling-full active schedule (FAS) and the schedule generation procedure based on the operation-based representation are presented. In order to avoid premature convergence of the conventional GA, the precedence operation crossover (POX) and approach of the generation alteration model are proposed for the improved GA. The improved GA is applied to solving the classical scheduling, due-dates scheduling and E/T scheduling problems, and the effectiveness of the active schedule, semi-active schedule and full active schedule decoding procedures for optimization algorithm is studied.

引用

页码：24 / 31

页数：7

共 14 条

[1]

Garey M.R., Johnson D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness, (1979)

[2]

Wang L., Shop Scheduling with Genetic Algorithms, (2003)

[3]

Holand J.H., Adaptation in Natural and Artificial Systems, (1975)

[4]

Gen M., Tsujimura Y., Kubota E., Solving job-shop scheduling problems using genetic algorithm, Proc. of the 16th Int. Conf. on Computer and Industrial Engineering, pp. 576-579, (1994)

[5]

Cheng R., Gen M., Tsujimura Y., A tutorial survey of job-shop scheduling problems using genetic algorithms-I. Representation, Computers and Industrial Engineering, 30, 4, pp. 983-997, (1996)

[6]

Bierwirth C., A generalized permutation approach to job shop scheduling with genetic algorithms, OR Spektrum, 17, pp. 87-92, (1995)

[7]

Baker K.R., Introduction to Sequencing and Scheduling, (1974)

[8]

Pinedo M., Scheduling Theory, Algorithms, and System, (2002)

[9]

Zhang C., Rao Y., Li P., Et al., An improved genetic algorithm for the Job shop scheduling Problem, China Mechanical Engineering, 15, 23, pp. 2149-2153, (2004)

[10]

Cheng R., Gen M., Tsujimura Y., A tutorial survey of job shop scheduling problems using genetic algorithms, part II: Hybrid genetic search strategies, Computers and Industrial Engineering, 36, pp. 343-364, (1999)

← 1 2 →