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

doi:10.3969/j.issn.1007-2861.2015.05.008

上海大学学报(自然科学版) ›› 2016, Vol. 22 ›› Issue (6): 793-803.doi: 10.3969/j.issn.1007-2861.2015.05.008

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

彭运芳1, 高雅1, 夏蓓鑫2

1. 上海大学管理学院, 上海 200444;
2. 上海大学机电工程与自动化学院, 上海 200072

收稿日期:2015-05-25 出版日期:2016-12-30 发布日期:2016-12-30
通讯作者: 夏蓓鑫(1984—), 男, 博士, 研究方向为系统调度、系统建模分析. E-mail: bxxia@shu.edu.cn
作者简介:夏蓓鑫(1984—), 男, 博士, 研究方向为系统调度、系统建模分析. E-mail: bxxia@shu.edu.cn
基金资助:
国家自然科学基金资助项目(51405283, 71401098)

Job shop scheduling with uncertainty based on genetic algorithm

PENG Yunfang1, GAO Ya1, XIA Beixin2

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

Received:2015-05-25 Online:2016-12-30 Published:2016-12-30

摘要/Abstract

摘要：

考虑到产品不同的交货期, 研究了不确定条件下的作业车间调度问题, 用三角模糊数表示产品处理时间, 建立了调度问题的模型, 并结合模糊理论设计了一种改进的遗传算法进行求解. 该算法通过整数编码的方法产生初始种群, 结合轮盘赌方法和精英保留策略进行选择操作, 采用基于优先工序交叉(precedence operation crossover, POX)算子和互换变异方法进行交叉和变异操作, 并通过动态调整交叉概率和变异概率的方法来提高算法的性能以及计算效率. 最后, 通过算例和企业实例验证了该模型和算法的有效性.

关键词: 不确定性 , 不同交货期窗口 , 提前/拖期 , 遗传算法, 作业车间调度

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

彭运芳1, 高雅1, 夏蓓鑫2. 不确定条件下基于遗传算法的作业车间调度问题[J]. 上海大学学报(自然科学版), 2016, 22(6): 793-803.

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.

参考文献

[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

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价