中文

Journal of Shanghai University >

2016 , Vol. 22 >Issue 6: 793 - 803

DOI: https://doi.org/10.3969/j.issn.1007-2861.2015.05.008

Job shop scheduling with uncertainty based on genetic algorithm

Expand
  • 1. School of Management, Shanghai University, Shanghai 200444, China;
    2. School of Mechatronics Engineering and Automation, Shanghai University, Shanghai 200072, China

Received date: 2015-05-25

  Online published: 2016-12-30

Fold

Abstract

A mathematical model representing uncertain processing time by triangular fuzzy number was built to deal with the job shop scheduling problem with different due date windows. An improved genetic algorithm was developed to solve the problem. The algorithm generated initial population using an integer coding method combined with a roulette method and the elitist strategy in the selection operator. Precedence operation crossover (POX) and swap mutation methods were used in crossover and mutation operators. Meanwhile, crossover and mutation probabilities were dynamically adjusted to improve the algorithm’s performance. An example was given to verify validity of the model and algorithm.

Key words： genetic algorithm;  different due date window;  earliness/tardiness;  uncertainty; job shop scheduling

Cite this article

PENG Yunfang1, GAO Ya1, XIA Beixin2 . Job shop scheduling with uncertainty based on genetic algorithm[J]. Journal of Shanghai University, 2016 , 22(6) : 793 -803 . DOI: 10.3969/j.issn.1007-2861.2015.05.008

References

[1] 李平, 顾幸生. 不确定条件下不同交货期窗口的Job Shop调度[J]. 管理科学学报, 2004, 7(2): 22-26.
[2] Pistikopoulos E N. Uncertainty in process design and operations [J]. Computers & Chemical Engineering, 1995, 19: 553-563.
[3] 杨宏安, 王周锋, 吕阳阳, 等. 工序加工时间不确定条件下作业车间调度问题的区间数求解方法[J]. 计算机集成制造系统, 2014, 20(9): 2231-2240.
[4] Lei D. Population-based neighborhood search for job shop scheduling with interval processing time [J]. Computers & Industrial Engineering, 2011, 61(4): 1200-1208.
[5] Azadeh A, Negahban A, Moghaddam M. A hybrid computer simulation-artificial neural network algorithm for optimization of dispatching rule selection in stochastic job shop scheduling problems [J]. International Journal of Production Research, 2012, 50(2): 551-566.
[6] Hu Y, Yin M, Li X. A novel objective function for job-shop scheduling problem with fuzzy processing time and fuzzy due date using differential evolution algorithm [J]. The International Journal of Advanced Manufacturing Technology, 2011, 56(9): 1125-1138.
[7] 李俊青, 潘全科. 求解模糊作业车间调度问题的混合优化算法[J]. 机械工程学报, 2013, 49(23): 142-149.
[8] 杨建斌, 孙树栋, 牛刚刚, 等. 自适应遗传算法求解模糊作业车间调度问题[J]. 机械科学与技术, 2013, 32(1): 16-21.
[9] 曹俊, 朱如鹏. 一种改善遗传算法早熟现象的方法[J]. 上海大学学报(自然科学版), 2003, 9(3): 229-231.
[10] 张凯燕, 莫云辉, 邓召义, 等. 改进遗传算法的行星齿轮传动多目标模糊物元可靠性优化[J]. 上海大学学报（自然科学版）, 2007, 13(1): 22-27.
[11] Sakawa M, Kubota R. Fuzzy programming for multi objective job shop scheduling with fuzzy processing time and fuzzy due date through genetic algorithms [J]. European Journal of Operational Research, 2000, 120(2): 393-407.

[12] Heilpern S. The expected value of a fuzzy number [J]. Fuzzy Sets and Systems, 1992, 47(1): 81-86.
[13] 张超勇, 饶运清, 刘向军, 等. 基于POX 交叉的遗传算法求解Job-Shop 调度问题[J]. 中国机械工程, 2005, 15(23): 2149-2153.
[14] 耿兆强, 邹益仁. 基于遗传算法的作业车间模糊调度问题的研究[J]. 计算机集成制造系统, 2002, 8(8): 616-620.
[15] Sakawa M, Mori T. An efficient genetic algorithm for job-shop scheduling problems with fuzzy processing time and fuzzy duedate [J]. Computers & Industrial Engineering, 1999, 36(2): 325-341.
[16] Palacios J J, Puente J, Vela C R, et al. Benchmarks for fuzzy job shop problems [J]. Information Sciences, 2016, 329: 736-752.

Options
Outlines

/

〈 〉