一种基于协同进化的流水线向<i>Seru</i>系统转化方法

吴旭辉; 杜劭峰; 郝慧慧; 于洋; 殷勇; 李冬妮

doi:10.16383/j.aas.2018.c160642

一种基于协同进化的流水线向Seru系统转化方法

doi: 10.16383/j.aas.2018.c160642

吴旭辉^1,,
杜劭峰^2,,
郝慧慧²,
于洋^3,,
殷勇^4,,
李冬妮^1, ,

1.
北京理工大学计算机学院智能信息技术北京市重点实验室北京 100081 中国
2.
特种车辆及其传动系统智能制造国家重点实验室包头 014000 中国
3.
东北大学流程工业综合自动化国家重点实验室沈阳 110819 中国
4.
同志社大学大学院商学研究科京都日本

基金项目:

特种车辆及其传动系统智能制造国家重点实验室开放课题 GZ2016KF003

国家自然科学基金 71401014

详细信息

作者简介:
吴旭辉北京理工大学计算机学院硕士研究生.主要研究方向为演化计算和生产调度.E-mail:harry_wxh@163.com

杜劭峰特种车辆及其传动系统智能制造国家重点实验室主任.主要研究方向为数字化与智能制造

郝慧慧特种车辆及其传动系统智能制造国家重点实验室成员.主要研究方向为数字化仿真技术

于洋东北大学信息科学与工程学院副教授.主要研究方向为工业工程, 绿色物流.E-mail:yuyang@ise.neu.edu.cn

殷勇同志社大学大学院商学研究科教授.主要研究方向为Seru制造与工业4.0.E-mail:yyin@mail.doshisha.ac.jp

通讯作者:
李冬妮北京理工大学计算机学院副教授.主要研究方向为智能优化, 企业计算, 物流管理.本文通信作者.E-mail:ldn@bit.edu.cn

计量
- 文章访问数: 2364
- HTML全文浏览量: 446
- PDF下载量: 476
- 被引次数: 0
出版历程
- 收稿日期: 2016-09-08
- 录用日期: 2017-07-12
- 刊出日期: 2018-06-20

A Line-seru Conversion Approach by Means of Cooperative Coevolution

WU Xu-Hui^1
,,
DU Shao-Feng^2
,,
HAO Hui-Hui²,
YU Yang^3
,,
YIN Yong^4
,,
LI Dong-Ni^{1
, ,}

1.
Beijing Laboratory of Intelligent Information Technology, School of Computer Science, Beijing Institute of Technology, Beijing 100081, China
2.
State Key Laboratory of Smart Manufacturing for Special Vehicles and Transmission System, Baotou 014000, China
3.
Institute of Systems Engineering, State Key Laboratory of Synthetic Automation for Process Industries, Northeastern University, Shenyang 110819, China
4.
Graduate School of Business, Doshisha University, Kyoto, Japan

Funds:

State Key Laboratory of Smart Manufacturing for Special Vehicles and Transmission Systems GZ2016KF003

National Natural Science Foundation of China 71401014

More Information

Author Bio:
Master student at the School of Computer Science, Beijing Institute of Technology. His research interest covers evolutionary computation and production scheduling

Directory of State Key Laboratory of Smart Manufacturing for Special Vehicles and Transmission System. His research interest covers digitization and smart manufacturing

Member of State Key Laboratory of Smart Manufacturing for Special Vehicles and Transmission System. Her main research interest is digital simulation

Associate professor at the School of Information Science and Engineering, Northeastern University. His research interest covers green logistics and industrial engineering

Professor at the Graduate School of Business, Doshisha University. His research interest covers production and Industry 4.0

Corresponding author: LI Dong-Ni Associate professor at the School of Computer Science, Beijing Institute of Technology. Her research interest covers intelligent optimization, enterprise computation, and logistics management. Corresponding author of this paper

摘要

摘要: Seru生产系统是一种被广泛应用于电子制造产业的新型生产模式，但由于流水线向Seru系统转化问题（Line-seru conversion）包含有Seru构建与Seru调度两个相互耦合的子问题，现有算法难以在同时兼顾解的质量与计算效率的情况下对问题进行求解.因此，本文针对流水线向Seru系统转化问题的特点，提出了一种协同进化算法，即在进化算法中加入了协同机制，将Seru构建与Seru调度子问题作为两个子种群利用该机制进行协同进化，从而弥补了现有算法的不足.并且，本文还针对问题特点设计了个体基因编码方式，从而使规划获得的Seru生产系统具有更优的生产性能及均衡性能.实验表明，采用加入了协同机制的进化算法比传统解决流水线向Seru系统转化问题的方法具有更好的性能，本文所提的方法在最小化产品流通时间和劳动时间有较好的性能表现，并且具有较高的计算效率.
- 协同进化 /
- 流水线 /
- Seru系统 /
- 转化
Abstract: Line-seru conversion is an innovative assembly system applied widely in the electronics industry. However, extant algorithms can hardly come into play in solving the line-seru conversion problem. The reason lies in that the line-seru conversion problem consists of two interacting subproblems, i.e., seru formation and seru loading, so it is difficult to obtain high quality solutions with affordable computation efficiency. Thus, an evolutionary algorithm with a cooperation mechanism is proposed in this paper. With the cooperation mechanism, the two subproblems can cooperatively evolved as two subpopulations simultaneously so as to address the aforementioned problem. Moreover, the coding of chromosomes representing scheduling result is modified to satisfy the specific requirement of the conversion and acquire solutions with enhanced performance and balancing ability. Computational result shows a better performance of the proposed method in minimizing total throughput time, total labor hours and computational costs.
- Cooperative coevolution /
- assembly line /
- seru system /
- conversion
注释:

1) 本文责任编委宋士吉

HTML全文

图 1 Seru构建编码示例1

Fig. 1 Example 1 of coding for seru formation

下载: 全尺寸图片幻灯片

图 2 Seru构建编码示例2

Fig. 2 Example 2 of coding for seru formation

下载: 全尺寸图片幻灯片

图 3 Seru调度编码示例1

Fig. 3 Example 1 of coding for seru loading

下载: 全尺寸图片幻灯片

图 4 Seru调度编码示例2

Fig. 4 Example 2 of coding for seru loading

下载: 全尺寸图片幻灯片

图 5 交换前编码示例

Fig. 5 Example of coding before exchange

下载: 全尺寸图片幻灯片

图 6 交换后编码示例

Fig. 6 Example of coding after exchange

下载: 全尺寸图片幻灯片

图 7 协同进化图

Fig. 7 Diagram of cooperative coevolution

下载: 全尺寸图片幻灯片

图 8 工人数量为5时, MOCC与未加入协同算法的非支配集间的比较

Fig. 8 The non-dominated solutions of MOCC and the one without cooperation strategy with 5 workers

下载: 全尺寸图片幻灯片

图 9 工人数量为5时, MOCC与NSGA-Ⅱ算法的非支配集间的比较

Fig. 9 The non-dominated solutions of MOCC and NSGA-Ⅱ with 5 workers

下载: 全尺寸图片幻灯片

图 10 工人数量为5时, MOCC与加入局部搜索的NSGA-Ⅱ算法的非支配集间的比较

Fig. 10 The non-dominated solutions of MOCC and NSGA-Ⅱ combining local search with 5 workers

下载: 全尺寸图片幻灯片

表 1 算例产生的参数表

Table 1 Parameters of test problems

算例产生参数	取值
产品类型	5
批次大小	$\sim$ U[10, 110]
$\varepsilon$${}_{i}$	$\sim$ N[0.2, 0.05]
SL${}_{n}$	2.2
SCP${}_{n}$	1.0
$T{}_{n}$	1.8
$\eta$${}_{i}$	10

下载: 导出CSV

表 2 与未使用协同策略的性能对比

Table 2 Comparison proposed approach and the one without cooperation strategy

$W$	${R}$	Proposed algorithm				MOE				${\rm Gap}_{{\rm RNI}\_AV}$(%)	${\rm Gap}_{D\_AV}$(%)
$W$	${R}$	$Av$ RNI	Min RNI	$Av$ $D_{av}$	$Av$ $D_{\max}$	$Av$ RNI	Min RNI	$Av$ $D_{av}$	$Av$ $D_{\max}$	${\rm Gap}_{{\rm RNI}\_AV}$(%)	${\rm Gap}_{D\_AV}$(%)
5	20	0.66	0.50	0.04	0.09	0.42	0.35	0.13	0.37	57.14	256.83
10	43	0.50	0.33	0.12	0.68	0.45	0.35	0.16	0.81	10.00	36.63
15	62	0.51	0.32	0.03	0.22	0.40	0.45	0.06	0.48	27.50	117.42
20	57	0.65	0.47	0.02	0.13	0.41	0.35	0.05	0.36	56.89	169.32
25	31	0.64	0.54	0.11	0.26	0.52	0.44	0.16	0.21	22.96	49.06
30	39	0.69	0.56	0.09	0.28	0.41	0.46	0.18	0.32	45.57	87.23
Average										36.68	119.42
注: $W$表示工人数量, $R$表示参考集中解的数量

下载: 导出CSV

表 3 与NSGA-Ⅱ方法的性能对比

Table 3 Comparison of proposed approach and NSGA-Ⅱ

${W}$	${R}$	Proposed algorithm				NSGA-Ⅱ				${\rm Gap}_{{\rm RNI}\_AV}$(%)	${\rm Gap}_{D\_AV}$(%)	${{\rm Gap}_{\rm STDEV}}$
${W}$	${R}$	$Av$ RNI	$Av$ $D_{av}$	$Av$ $D_{\max}$	STDEV TTPT	$Av$ RNI	$Av$ $D_{av}$	$Av$ $D_{\max}$	STDEV TTPT	${\rm Gap}_{{\rm RNI}\_AV}$(%)	${\rm Gap}_{D\_AV}$(%)	${{\rm Gap}_{\rm STDEV}}$
5	20	0.66	0.04	0.09	134.91	0.37	0.14	0.40	390.95	78.38	281.42	189.79
10	43	0.45	0.12	0.68	330.33	0.35	0.14	0.69	1 101.28	25.71	20.61	233.39
15	62	0.40	0.03	0.22	552.93	0.27	0.06	0.45	2 518.01	48.71	142.42	355.39
20	57	0.65	0.02	0.13	1 672.87	0.23	0.06	0.38	5 443.23	176.02	263.64	225.38
25	31	0.64	0.11	0.26	1 551.91	0.49	0.18	0.31	7 613.63	31.52	73.58	390.60
30	39	0.69	0.09	0.28	1 286.32	0.41	0.19	0.27	6 156.87	66.68	97.87	378.64
Average										71.17	146.59	295.53

下载: 导出CSV

表 4 与加入local search的NSGA-Ⅱ方法的性能对比

Table 4 Comparison of proposed approach and NSGA-Ⅱ combining local search

${W}$	${R}$	Proposed algorithm				NSGA-Ⅱ combining local search				${\rm Gap}_{{\rm RNI}\_AV}$(%)	${\rm Gap}_{D\_AV}$(%)	${{\rm Gap}_{\rm STDEV}}$
${W}$	${R}$	$Av$ RNI	$Av$ $D_{av}$	$Av$ $D_{\max}$	STDEV TTPT	$Av$ RNI	$Av$ $D_{av}$	$Av$ $D_{\max}$	STDEV TTPT	${\rm Gap}_{{\rm RNI}\_AV}$(%)	${\rm Gap}_{D\_AV}$(%)	${{\rm Gap}_{\rm STDEV}}$
5	20	0.66	0.04	0.09	134.91	0.40	0.13	0.42	377.08	65.00	262.84	179.51
10	43	0.45	0.12	0.68	330.33	0.39	0.15	0.68	1 010.48	15.68	26.75	205.90
15	62	0.40	0.03	0.22	552.93	0.26	0.07	0.52	3 122.81	53.92	159.85	464.78
20	57	0.65	0.02	0.13	1 672.87	0.29	0.06	0.39	5 275.38	122.79	263.64	215.35
25	31	0.64	0.11	0.26	1 551.91	0.51	0.17	0.26	6 962.83	26.35	64.15	348.66
30	39	0.69	0.09	0.28	1 286.32	0.47	0.16	0.34	6 261.26	47.44	74.47	386.76
Average										55.20	141.95	300.16

下载: 导出CSV

A1 工人i的多能工系数

A1 Worker i's coefficient of influencing level of doing multiple assembly task

工人	1	2	3	4	5
$\varepsilon{}_{i}$	0.18	0.19	0.2	0.21	0.2
工人	6	7	8	9	10
$\varepsilon{}_{i}$	0.2	0.2	0.22	0.19	0.19
工人	11	12	13	14	15
$\varepsilon{}_{i}$	0.18	0.23	0.24	0.22	0.16
工人	16	17	18	19	20
$\varepsilon{}_{i}$	0.24	0.18	0.18	0.21	0.18

下载: 导出CSV

A2 工人对不同类型产品熟练度数据的分布

A2 The data distribution of worker's level of skill for each product type

产品类型
1	2	3	4	5
N(1, 0.05)	N(1.05, 0.05)	N(1.1, 0.05)	N(1.15, 0.05)	N(1.2, 0.05)

下载: 导出CSV

A3 工人对不同产品的熟练度

A3 The data of worker's level of skill

工人/产品	1	2	3	4	5
1	0.92	0.96	1.04	1.09	1.20
2	0.95	0.97	1.09	1.12	1.18
3	0.99	1.01	1.05	1.09	1.21
4	1.03	1.07	1.09	1.12	1.25
5	0.96	1.02	1.05	1.10	1.18
6	1.01	1.10	1.10	1.15	1.23
7	1.04	1.07	1.09	1.17	1.24
8	0.98	1.02	1.10	1.11	1.20
9	0.97	1.03	1.12	1.19	1.26
10	0.98	1.06	1.13	1.18	1.28
11	0.95	1.04	1.03	1.14	1.19
12	0.98	1.07	1.07	1.15	1.15
13	0.99	0.95	1.11	1.17	1.10
14	1.01	1.10	1.05	1.13	1.18
15	1.04	1.10	1.05	1.15	1.11
16	0.99	0.97	1.08	1.11	1.22
17	1.04	1.01	1.11	1.15	1.24
18	0.93	1.06	1.07	1.13	1.14
19	0.96	0.98	1.12	1.14	1.21
20	1.08	1.04	1.09	1.11	1.13

下载: 导出CSV

A4 30批产品的信息数据

A4 The data of 30 batches

批次编号	产品类型	批次大小
1	3	46
2	5	68
3	3	45
4	4	19
5	1	36
6	4	45
7	1	62
8	2	30
9	2	60
10	3	67
11	2	9
12	4	24
13	3	38
14	4	32
15	5	52
16	5	48
17	1	68
18	4	71
19	2	46
20	5	25
21	1	26
22	3	52
23	4	46
24	5	44
25	2	32
26	3	75
27	1	33
28	4	103
29	2	74
30	3	53

下载: 导出CSV

参考文献(35)

[1]	盛朝迅, 黄汉权.中美制造业成本比较及对策建议.宏观经济管理, 2016, (9):85-88 http://www.doc88.com/p-7095650929234.html
[2]	Stecke K E, Yin Y, Kaku I. Seru production: an extension of just-in-time approach for volatile business environments. Analytical Approaches to Strategic Decision-Making: Interdisciplinary Considerations, IGI Global, 2014. 45-58 http://www.researchgate.net/publication/293118003_Seru_production_An_extension_of_just-in-time_approach_for_volatile_business_environments
[3]	Isa K, Tsuru T. Cell production and workplace innovation in Japan:toward a new model for Japanese manufacturing? Industrial Relations:A Journal of Economy and Society, 2002, 41(4):548-578 doi: 10.1111/irel.2002.41.issue-4
[4]	Manupati V K, Vemkata Deepthi T, Ramakotaiah K, Rao S S. Reconfiguration of networked seru production systems in an Indian perspective. In: Proceedings of the 2015 IEEE International Conference on Industrial Engineering and Operations Management. Dubai, United Arab Emirates: IEEE, 2015. 1-7 http://ieeexplore.ieee.org/document/7093755/
[5]	Yin Y, Kaku I, Stecke K E. The evolution of seru production systems throughout Canon. Operations Management Education Review, Scotland, UK: Neilson Journals Publishing, 2008. 27-40
[6]	Stecke K E, Yin Y, Kaku I, Murase Y. Seru:the organizational extension of JIT for a super-talent factory. International Journal of Strategic Decision Sciences, 2012, 3(1):106-119 doi: 10.4018/IJSDS
[7]	De Treville S, Ketokivi M, Singhal V R. Competitive manufacturing in a high-cost environment. Journal of Operations Management, 2017, 49-51:1-88 DOI: 10.1016/j.jom.2017.02.001
[8]	刘晨光, 廉洁, 李文娟, 殷勇.日本式单元化生产——生产方式在日本的最新发展形态.管理评论, 2010, 22(5):93-103 https://www.wenkuxiazai.com/doc/f79c3c2db4daa58da0114ac4-2.html
[9]	Yin Y, Stecke K E, Swink M, Kaku I. Lessons from seru production on manufacturing competitively in a high cost environment. Journal of Operations Management, 2017, 49-51:67-76 doi: 10.1016/j.jom.2017.01.003
[10]	Liu C G, Li W J, Lian J, Yin Y. Reconfiguration of assembly systems:from conveyor assembly line to serus. Journal of Manufacturing Systems, 2012, 31(3):312-325 doi: 10.1016/j.jmsy.2012.02.003
[11]	Liu C G, Stecke K E, Lian J, Yin Y. An implementation framework for seru production. International Transactions in Operational Research, 2014, 21(1):1-19 doi: 10.1111/itor.2014.21.issue-1
[12]	Liu C G, Yang J, Lian J, Li W J, Evans S, Yin Y. Sustainable performance oriented operational decision-making of single machine systems with deterministic product arrival time. Journal of Cleaner Production, 2014, 85:318-330 doi: 10.1016/j.jclepro.2014.07.025
[13]	Liu C G, Lian J, Yin Y, Li W J. Seru Seisa——an innovation of the production management mode in Japan. Asian Journal of Technology Innovation, 2010, 18(2):89-113 doi: 10.1080/19761597.2010.9668694
[14]	Liu C G, Dang F, Li W J, Evans S, Yin Y. Production planning of multi-stage multi-option seru production systems with sustainable measures. Journal of Cleaner Production, 2015, 105:285-299 doi: 10.1016/j.jclepro.2014.03.033
[15]	Zhang X L, Liu C G, Li W J, Evans S, Yin Y. Effects of key enabling technologies for seru production on sustainable performance. Omega, 2017, 66:290-307 doi: 10.1016/j.omega.2016.01.013
[16]	Luo L, Zhang Z, Yin Y. Seru loading with worker-operation assignment in single period. In: Proceedings of the 2016 IEEE International Conference on Industrial Engineering and Engineering Management. Bali, Indonesia: IEEE, 2016. 1055-1058 http://ieeexplore.ieee.org/abstract/document/7798039/
[17]	Yu Y, Tang J F, Sun W, Yin Y, Kaku I. Reducing worker (s) by converting assembly line into a pure cell system. International Journal of Production Economics, 2013, 145(2):799-806 doi: 10.1016/j.ijpe.2013.06.009
[18]	Liu C G, Yang N, Li W J, Lian J, Evans S, Yin Y. Training and assignment of multi-skilled workers for implementing seru production systems. The International Journal of Advanced Manufacturing Technology, 2013, 69(5-8):937-959 doi: 10.1007/s00170-013-5027-5
[19]	Yu Y, Tang J, Sun W, Yin Y, Kaku I. Combining local search into non-dominated sorting for multi-objective line-cell conversion problem. International Journal of Computer Integrated Manufacturing, 2013, 26(4):316-326 doi: 10.1080/0951192X.2012.717717
[20]	Yu Y, Gong J, Tang J F, Yin Y, Kaku I. How to carry out assembly line-cell conversion? A discussion based on factor analysis of system performance improvements. International Journal of Production Research, 2012, 50(18):5259-5280 doi: 10.1080/00207543.2012.693642
[21]	Yu Y, Tang J, Gong J, Yin Y, Kaku I. Mathematical analysis and solutions for multi-objective line-cell conversion problem. European Journal of Operational Research, 2014, 236(2):774-786 doi: 10.1016/j.ejor.2014.01.029
[22]	Kaku I, Gong J, Tang J F, Yin Y. A mathematical model for converting conveyor assembly line to cellular manufacturing. Industrial Engineering & Management Systems, 2008, 7(2):160-170 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.598.431
[23]	Dimopoulos C, Zalzala A M S. Investigating the use of genetic programming for a classic one-machine scheduling problem. Advances in Engineering Software, 2001, 32(6):489-498 doi: 10.1016/S0965-9978(00)00109-5
[24]	Nguyen S, Zhang M, Johnston M, Tan K C. Automatic programming via iterated local search for dynamic job shop scheduling. IEEE Transactions on Cybernetics, 2015, 45(1):1-14 doi: 10.1109/TCYB.2014.2317488
[25]	贾凌云, 李冬妮, 田云娜.基于混合蛙跳和遗传规划的跨单元调度方法.自动化学报, 2014, 40(5):936-948 http://www.aas.net.cn/CN/abstract/abstract18668.shtml Jia Ling-Yun, Li Dong-Ni, Tian Yun-Na. An intercell scheduling approach using shuffled frog leaping algorithm and genetic programming. Acta Automatica Sinica, 2014, 40(5):936-948 http://www.aas.net.cn/CN/abstract/abstract18668.shtml
[26]	田云娜, 李冬妮, 刘兆赫, 郑丹.一种基于动态决策块的超启发式跨单元调度方法.自动化学报, 2016, 42(4):524-534 http://www.aas.net.cn/CN/abstract/abstract18840.shtml Tian Yun-Na, Li Dong-Ni, Liu Zhao-He, Zheng Dan. A Hyper-heuristic Approach with Dynamic Decision Blocks for Inter-cell Scheduling. Acta Automatica Sinica, 2016, 42(4):524-534 http://www.aas.net.cn/CN/abstract/abstract18840.shtml
[27]	Cheng T C E. Integration of priority dispatching and due-date assignment in a job shop. International Journal of Systems Science, 2007, 19(9):1813-1825 http://cn.bing.com/academic/profile?id=daae2bd14967aaa4cc1c9c14fd21adf7&encoded=0&v=paper_preview&mkt=zh-cn
[28]	Baker Kenneth R. Sequencing rules and due-date assignments in a job shop. Management Science, 1984, 30(9):1093-1104 doi: 10.1287/mnsc.30.9.1093
[29]	Miyazaki S. Combined scheduling system for reducing job tardiness in a job shop. International Journal of Production Research, 1981, 19(2):201-211 doi: 10.1080/00207548108956642
[30]	Cochran J K, Horng S M, Fowler J W. A multi-population genetic algorithm to solve multi-objective scheduling problems for parallel machines. Computers & Operations Research, 2003, 30(7):1087-1102 http://cn.bing.com/academic/profile?id=2cced13cbd126cf7cb7cf1df655f4886&encoded=0&v=paper_preview&mkt=zh-cn
[31]	Goh C K, Tan K C. A Competitive-cooperative coevolutionary paradigm for dynamic multiobjective optimization. IEEE Transactions on Evolutionary Computation, 2009, 13(1):103-127 doi: 10.1109/TEVC.2008.920671
[32]	Tan K C, Lee T H, Khor E F. Evolutionary algorithms with dynamic population size and local exploration for multiobjective optimization. IEEE Transactions on Evolutionary Computation, 2001, 5(6):565-588 doi: 10.1109/4235.974840
[33]	Ulungu E L, Teghem J, Ost C. Efficiency of interactive multi-objective simulated annealing through a case study. Journal of the Operational Research Society, 1998, 49(10):1044-1050 doi: 10.1057/palgrave.jors.2600569
[34]	Czyzżk P, Jaszkiewicz A. Pareto simulated annealing——a metaheuristic technique for multiple-objective combinatorial optimization. Journal of Multi-Criteria Decision Analysis, 1998, 7(1):34-47 doi: 10.1002/(SICI)1099-1360(199801)7:1<34::AID-MCDA161>3.0.CO;2-6
[35]	Wang X D, Hirsch C, Kang S, Lacor C. Multi-objective optimization of turbomachinery using improved NSGA-Ⅱ and approximation model. Computer Methods in Applied Mechanics and Engineering, 2011, 200(9-12):883-895 doi: 10.1016/j.cma.2010.11.014