不确定条件下基于遗传算法的作业车间调度问题

doi:10.3969/j.issn.1007-2861.2015.05.008

Abstract

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

PENG Yunfang1, GAO Ya1, XIA Beixin2. Job shop scheduling with uncertainty based on genetic algorithm[J]. Journal of Shanghai University（Natural Science Edition）, 2016, 22(6): 793-803.

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.

Job shop scheduling with uncertainty based on genetic algorithm

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 7

Recommended Articles

Metrics

Comments

[1]	Mingkun LI, Gaoshuai BAI, Xinying JIANG. A modeling and solution method for cash transportation vehicle routing from the perspective of workload balancing [J]. Journal of Shanghai University（Natural Science Edition）, 2019, 25(5): 836-850.
[2]	KONG Weijian, WANG Yongfang, TONG Zilei, ZHANG Hongguang. Modeling and algorithm implementation of dietary nutrition optimization for diabetic patients [J]. Journal of Shanghai University（Natural Science Edition）, 2018, 24(4): 583-591.
[3]	LIU Dongjun, XU Meihua, GONG Luming, XIA Chenjun. Feature fusion for front vehicle detection and implementation [J]. Journal of Shanghai University（Natural Science Edition）, 2017, 23(6): 893-.
[4]	WEI Xin-hua,GUO Jia-hong. Optimization of Pumping Station with Simulated Annealing and Genetic Algorithm [J]. Journal of Shanghai University（Natural Science Edition）, 2009, 15(1): 32-36.
[5]	SHENG Jie;YANG Xue-xia;SUN Jiang-tao . Design of UWB Antenna Using Genetic Algorithm Optimization [J]. Journal of Shanghai University（Natural Science Edition）, 2008, 14(4): 346-348 .
[6]	WU Pin;LI Jian-dun;LIU Quan-sheng;LI Song-bei. Grid Resource Selection Strategy Based on an Adaptive Parallel Genetic Algorithm [J]. Journal of Shanghai University（Natural Science Edition）, 2007, 13(5): 629-633 .
[7]	ZHANG Kai yan;MO Yun hui;DENG Zhaoyi;et al . Multi object Fuzzy Reliability Optimization of Planar Gear Transmission Based on Improved Genetic Algorithm [J]. Journal of Shanghai University（Natural Science Edition）, 2007, 13(1): 22-27 .