A Graph-based Ant Colony Optimization Approach for Integrated Process Planning and Scheduling

doi:10.1016/j.cjche.2014.05.011

›› 2014, Vol. 22 ›› Issue (7): 748-753.DOI: 10.1016/j.cjche.2014.05.011

• PROCESS SYSTEMS ENGINEERING • Previous Articles Next Articles

A Graph-based Ant Colony Optimization Approach for Integrated Process Planning and Scheduling

Jinfeng Wang, Xiaoliang Fan, Chaowei Zhang, Shuting Wan

School of Power and Mechanical Engineering, North China Electric Power University, Baoding 071003, China

Received:2013-05-25 Revised:2013-11-16 Online:2014-08-23 Published:2014-07-28
Supported by:
Supported by the Fundamental Research Funds for the Central Universities (13MS100), the Hebei Province Research Foundation of Natural Science (E2011502024) and the National Natural Science Foundation of China (51177046).

A Graph-based Ant Colony Optimization Approach for Integrated Process Planning and Scheduling

Jinfeng Wang, Xiaoliang Fan, Chaowei Zhang, Shuting Wan

School of Power and Mechanical Engineering, North China Electric Power University, Baoding 071003, China

通讯作者: Jinfeng Wang
基金资助:
Supported by the Fundamental Research Funds for the Central Universities (13MS100), the Hebei Province Research Foundation of Natural Science (E2011502024) and the National Natural Science Foundation of China (51177046).

Abstract

Abstract: This paper considers an ant colony optimization algorithm based on AND/OR graph for integrated process planning and scheduling (IPPS). Generally, the process planning and scheduling are studied separately. Due to the complexity of manufacturing system, IPPS combining both process planning and scheduling can depict the real situation of a manufacturing system. The IPPS is represented on AND/OR graph consisting of nodes, and undirected and directed arcs. The nodes denote operations of jobs, and undirected/directed arcs denote possible visiting path among the nodes. Ant colony goes through the necessary nodes on the graph fromthe starting node to the end node to obtain the optimal solution with the objective of minimizing makespan. In order to avoid local convergence and lowconvergence, some improved strategy is incorporated in the standard ant colony optimization algorithm. Extensive computational experiments are carried out to study the influence of various parameters on the system performance.

Key words: Process planning, Scheduling, Ant colony optimization, Makespan

摘要： This paper considers an ant colony optimization algorithm based on AND/OR graph for integrated process planning and scheduling (IPPS). Generally, the process planning and scheduling are studied separately. Due to the complexity of manufacturing system, IPPS combining both process planning and scheduling can depict the real situation of a manufacturing system. The IPPS is represented on AND/OR graph consisting of nodes, and undirected and directed arcs. The nodes denote operations of jobs, and undirected/directed arcs denote possible visiting path among the nodes. Ant colony goes through the necessary nodes on the graph fromthe starting node to the end node to obtain the optimal solution with the objective of minimizing makespan. In order to avoid local convergence and lowconvergence, some improved strategy is incorporated in the standard ant colony optimization algorithm. Extensive computational experiments are carried out to study the influence of various parameters on the system performance.

关键词: Process planning, Scheduling, Ant colony optimization, Makespan

Jinfeng Wang, Xiaoliang Fan, Chaowei Zhang, Shuting Wan. A Graph-based Ant Colony Optimization Approach for Integrated Process Planning and Scheduling[J]. , 2014, 22(7): 748-753.

References

[1] R. Shafaei, P. Brunn,Workshop scheduling using practical (inaccurate) data. Part 3: a framework to integrate job releasing, routing and scheduling functions to create a robust predictive schedule, Int. J. Prod. Res. 38 (1) (2000) 85-99.
[2] G. Chryssolouris, S. Chan, W. Cobb, Decision making on the factory floor: an integrated approach to process planning and scheduling, Robot. Comput. Integr. Manuf. 1 (3-4) (1984) 315-319.
[3] G. Chryssolouris, S. Chan, An integrated approach to process planning and scheduling, CIRP Ann. Manuf. Technol. 34 (1) (1985) 413-417.
[4] N. Nasr, A. Elsayed, Job shop scheduling with alternative machines, Int. J. Prod. Res. 28 (9) (1990) 1595-1609.
[5] P. Bandeimarte, M. Calderini, A heuristic bicriterion approach to integrated process plan selection and job shop scheduling, Int. J. Prod. Res. 33 (1) (1995) 161-181.
[6] K.H. Kim, J.Y. Song, K.H. Wang, A negotiation based scheduling for items with flexible process plan, Comput. Ind. Eng. 33 (3-4) (1997) 785-788.
[7] K.H. Kim, P.J. Egbelu, A mathematical model for job shop scheduling with multiple process plan consideration per job, Prod. Plan. Control 9 (3) (1998) 250-259.
[8] C. Saygin, S.E. Kilic, Integrating flexible process plans with scheduling in flexible manufacturing systems, Int. J. Adv. Manuf. Technol. 15 (4) (1999) 265-280.
[9] W. Tan, Integration of process planning and scheduling — a review, J. Intell. Manuf. 11 (1) (2000) 51-63.
[10] H. Lee, S.S. Kim, Integration of process planning and scheduling using simulation based genetic algorithms, Int. J. Adv. Manuf. Technol. 18 (8) (2001) 586-590.
[11] Y.K. Kim, K. Park, J. Ko, A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling, Comput. Oper. Res. 30 (8) (2003) 1151-1171.
[12] R. Kumar, M.K. Tiwari, R. Shankar, Scheduling of flexible manufacturing systems: an ant colony optimization approach, P. I. MECH. ENG. B-J. ENG. 217 (11) (2003) 1443-1453.
[13] W. Tan, B. Khoshnevis, A linearized polynomial mixed integer programming model for the integration of process planning and scheduling, J. Intell. Manuf. 15 (5) (2004) 593-605.
[14] T.N. Wong, C.W. Leung, K.L. Mak, R.Y.K. Fung, An agent-based negotiation approach to integrate process planning and scheduling, Int. J. Prod. Res. 44 (7) (2006) 1331-1351.
[15] L.H. Wang, W.M. Shen, Q. Hao, An overview of distributed process planning and its integration with scheduling, Int. J. Comput. Appl. Technol. 26 (1-2) (2006) 3-14.
[16] W.D. Li, C.A. McMahon, A simulated annealing-based optimization approach for integrated process planning and scheduling, Int. J. Comput. Integr. Manuf. 20 (1) (2007) 80-95.
[17] C. Moon, Y.H. Lee, C.S. Jeong, Y.S. Yun, Integrated process planning and scheduling in a supply chain, Comput. Ind. Eng. 54 (4) (2008) 1048-1061.
[18] X.Y. Shao, X.Y. Li, L. Gao, Ch.Y. Zhang, Integration of process planning and scheduling — a modified genetic algorithm-based approach, Comput. Oper. Res. 36 (6) (2009) 2082-2096.
[19] X.Y. Li, X.Y. Shao, L. Gao, W.R. Qian, An effective hybrid algorithm for integrated process planning and scheduling, Int. J. Prod. Econ. 126 (2) (2010) 289-298.
[20] C.W. Leung, T.N. Wong, K.L. Mak, R.Y.K. Fung, Integrated process planning and scheduling by an agent-based ant colony optimization, Comput. Ind. Eng. 59 (1) (2010) 166-180.
[21] T.N. Wong, S.C.H. Zhang, G. Wang, L.P. Zhang, Integrated process planning and scheduling — multi-agent system with two-stage ant colony optimization algorithm, Int. J. Prod. Res. 50 (21) (2012) 6188-6201.
[22] Y.W. Guo, W.D. Li, A.R. Mileham, G.W. Owen, Applications of particle swarm and optimization in integrated process planning and scheduling, Robot. Comput. Integr. Manuf. 25 (2) (2009) 280-288.
[23] Y.C. Ho, C.L. Moodie, Solving cell formation problems in a manufacturing environment with flexible processing and routing capabilities, Int. J. Prod. Res. 34 (10) (1996) 2901-2923.
[24] M. Dorigo, V. Maniezzo, A. Colorni, The ant system: optimization by a colony of cooperating agents, IEEE Trans. Syst. Man Cybern. Syst. 26 (2) (1996) 29-41.
[25] Y.K. Kim, A set of data for the integration of process planning and job shop scheduling, Available at/ http://syslab.chonnam.ac.kr/links/data-pp&s.doc 2003.

A Graph-based Ant Colony Optimization Approach for Integrated Process Planning and Scheduling

A Graph-based Ant Colony Optimization Approach for Integrated Process Planning and Scheduling

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Kexin Bi, Mingyu Yan, Shuyuan Zhang, Tong Qiu. Three-scale integrated optimization model of furnace simulation, cyclic scheduling, and supply chain of ethylene plants [J]. Chinese Journal of Chemical Engineering, 2022, 44(4): 29-40.
[2]	Di Meng, Cheng Shao, Li Zhu. Dual-radiation-chamber coordinated overall energy efficiency scheduling solution for ethylene cracking process regarding multi-parameter setting and multi-flow allocation [J]. Chinese Journal of Chemical Engineering, 2021, 34(6): 180-197.
[3]	Kunkun Peng, Quanke Pan, Biao Zhang. An improved artificial bee colony algorithm for steelmaking-refining-continuous casting scheduling problem [J]. Chin.J.Chem.Eng., 2018, 26(8): 1727-1735.
[4]	Xiaoyong Gao, Dexian Huang, Yongheng Jiang, Tao Chen. A decision tree based decomposition method for oil refinery scheduling [J]. Chin.J.Chem.Eng., 2018, 26(8): 1605-1612.
[5]	Bin Shi, Xinrui Qian, Shanshan Sun, Liexiang Yan. Rule-based scheduling of multi-stage multi-product batch plants with parallel units [J]. , 2017, 25(8): 1022-1036.
[6]	Peng Jiang, Wenli Du. Multi-objective modeling and optimization for scheduling of cracking furnace systems [J]. , 2017, 25(8): 992-999.
[7]	Lei Shi, Yongheng Jiang, Ling Wang, Dexian Huang. A continuous-time formulation for refinery production scheduling problems involving operational transitions in mode switching [J]. , 2016, 24(8): 1020-1031.
[8]	Jin Lang, Jiao Zhao. Modeling and optimization for oil well production scheduling [J]. , 2016, 24(10): 1423-1430.
[9]	Wuthichai Wongthatsanekorn, Busaba Phruksaphanrat. Genetic algorithm for short-term scheduling of make-and-pack batch production process [J]. , 2015, 23(9): 1475-1483.
[10]	Lei Shi, Yongheng Jiang, Ling Wang, Dexian Huang. A novel two-stage Lagrangian decomposition approach for refinery production scheduling with operational transitions in mode switching [J]. Chin.J.Chem.Eng., 2015, 23(11): 1793-1800.
[11]	Xiaoyu Nian, Zhenlei Wang, Feng Qian. Strategy of changing cracking furnace feedstock based on improved group search optimization [J]. Chin.J.Chem.Eng., 2015, 23(1): 181-191.
[12]	Shuo Lin, Fangjun Luan, Zhonghua Han, Xisheng Lü, Xiaofeng Zhou, Wei Liu. Genetic Algorithm Based on Duality Principle for Bilevel Programming Problem in Steel-making Production [J]. , 2014, 22(7): 742-747.
[13]	DENG Guanlong, XU Zhenhao, GU Xingsheng. A Discrete Artificial Bee Colony Algorithm for Minimizing the Total Flow Time in the Blocking Flow Shop Scheduling^* [J]. Chin.J.Chem.Eng., 2012, 20(6): 1067-1073.
[14]	BAI Liang, JIANG Yongheng, HUANG Dexian, LIU Xianguang. A Novel Scheduling Strategy for Crude Oil Blending [J]. , 2010, 18(5): 777-786.
[15]	LUO Chunpeng, RONG Gang. A Strategy for the Integration of Production Planning and Scheduling in Refineries under Uncertainty [J]. , 2009, 17(1): 113-127.