Full Text:   <1297>

CLC number: TP278

On-line Access: 2010-09-30

Received: 2009-11-15

Revision Accepted: 2010-06-01

Crosschecked: 2010-09-03

Cited: 2

Clicked: 2710

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE C 2010 Vol.11 No.10 P.767-777

10.1631/jzus.C0910707


Feature-based initial population generation for the optimization of job shop problems


Author(s):  Jing Chen, Shu-you Zhang, Zhan Gao, Li-xin Yang

Affiliation(s):  State Key Lab of Fluid Power Transmission and Control, Zhejiang University, Hangzhou 310027, China, Top Vocational Institute of Information & Technology of Shaoxing, Shaoxing 312000, China

Corresponding email(s):   jingchen.zju@gmail.com

Key Words:  Scheduling feature, Job shop problem (JSP), Scheduling optimization, Scheduling knowledge


Jing Chen, Shu-you Zhang, Zhan Gao, Li-xin Yang. Feature-based initial population generation for the optimization of job shop problems[J]. Journal of Zhejiang University Science C, 2010, 11(10): 767-777.

@article{title="Feature-based initial population generation for the optimization of job shop problems",
author="Jing Chen, Shu-you Zhang, Zhan Gao, Li-xin Yang",
journal="Journal of Zhejiang University Science C",
volume="11",
number="10",
pages="767-777",
year="2010",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.C0910707"
}

%0 Journal Article
%T Feature-based initial population generation for the optimization of job shop problems
%A Jing Chen
%A Shu-you Zhang
%A Zhan Gao
%A Li-xin Yang
%J Journal of Zhejiang University SCIENCE C
%V 11
%N 10
%P 767-777
%@ 1869-1951
%D 2010
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.C0910707

TY - JOUR
T1 - Feature-based initial population generation for the optimization of job shop problems
A1 - Jing Chen
A1 - Shu-you Zhang
A1 - Zhan Gao
A1 - Li-xin Yang
J0 - Journal of Zhejiang University Science C
VL - 11
IS - 10
SP - 767
EP - 777
%@ 1869-1951
Y1 - 2010
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.C0910707


Abstract: 
A suitable initial value of a good (close to the optimal value) scheduling algorithm may greatly speed up the convergence rate. However, the initial population of current scheduling algorithms is randomly determined. Similar scheduling instances in the production process are not reused rationally. For this reason, we propose a method to generate the initial population of job shop problems. The scheduling model includes static and dynamic knowledge to generate the initial population of the genetic algorithm. The knowledge reflects scheduling constraints and priority rules. A scheduling strategy is implemented by matching and combining the two categories of scheduling knowledge, while the experience of dispatchers is externalized to semantic features. Feature similarity based knowledge matching is utilized to acquire the constraints that are in turn used to optimize the scheduling process. Results show that the proposed approach is feasible and effective for the job shop optimization problem.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1]Balas, E., Vazacopoulos, A., 1998. Guided local search with shifting bottleneck for job shop scheduling. Manag. Sci., 44(2):262-275.

[2]Brucker, P., 1995. Scheduling Algorithms. Springer Verlag, Berlin.

[3]Eren, T., 2009. A bicriteria parallel machine scheduling with a learning effect of setup and removal times. Appl. Math. Model., 33(2):1141-1150.

[4]Gao, L., 2003. Shop Scheduling with Genetic Algorithms. Tsinghua University Press, Beijing, China (in Chinese).

[5]Giffler, B., Thomson, G.L., 1960. Algorithms for solving production scheduling problems. Oper. Res., 8(4):487-503.

[6]Gonzalez-Rodriguez, I., Puente, J., Vela, C.R., Varela, R., 2008. Semantics of schedules for the fuzzy job-shop problem. IEEE Trans. Syst. Cybern. Part A: Syst. Hum., 38(3):655-666.

[7]Ida, K., Osawa, A., 2007. Solution of job-shop scheduling problems by an idle time shortening. Electr. Eng. Jpn., 159(2):55-63.

[8]Li, N.X., Chen, Y.W., Yang, K.W., 2008. Multi-objective flexible job shop schedule: design and evaluation by simulation modeling. Appl. Soft Comput., 9(1):362-376.

[9]Pezzella, F., Morganti, G., Ciaschetti, G., 2008. A genetic algorithm for the flexible job-shop scheduling problem. Comput. Oper. Res., 35(10):3202-3212.

[10]Togan, V., Daloglu, A.T., 2008. An improved genetic algorithm with initial population strategy and self-adaptive member grouping. Comput. & Struct., 86(11-12):1204-1218.

[11]Tsai, J.T., Chou, J.H., Liu, T.K., 2006. Tuning the structure and parameters of a neural network by using hybrid Taguchi-genetic algorithm. IEEE Trans. Neur. Networks, 17(1):69-80.

[12]Tsai, J.T., Liu, T.K., Ho, W.H., Chou, J.H., 2008. An improved genetic algorithm for job-shop scheduling problems using Taguchi-based crossover. Int. J. Adv. Manuf. Technol., 38(9-10):987-994.

[13]Watanabe, M., Ida, K., Gen, M., 2005. A genetic algorithm with modified crossover operator and search area adaptation for the job-shop scheduling problem. Comput. Ind. Eng., 48(4):743-752.

[14]Watanabe, M., Ida, K., Gen, M., 2006. Active solution space and search on job-shop scheduling problem. Electr. Eng. Jpn., 154(4):61-67.

[15]Zhang, C.Y., Li, P.G., Guan, Z.L., Rao, Y.Q., 2007. A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem. Comput. Oper. Res., 34(11):3229-3242.

[16]Zhang, C.Y., Guan, Z.L., Liu, Q., Shao, X.Y., Li, P., 2008. New scheduling type applied to solving job-shop scheduling problem. Chin. J. Mech. Eng., 44(10):24-31.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE