一种多智能体联盟协商的跨单元工件调度方法
|
摘要
针对工件在单元制造系统中由单元间转移带来的跨作业单元调度问题,提出一种基于多智能体联盟思想的跨单元工件调度方法(multi-agents coalitions,MAC),考虑跨单元柔性路径的情况,采用多智能体的协商机制,分阶段组建联盟,基于联盟进行协商调度,确保优化性能的同时减少通信量开销.通过实验对算法进行验证,实验结果表明本文所提方法在平均延迟性能方面优于常见的组合调度规则方法.
To solve the problem of the workpiece inter-cell move in inter-cell scheduling for the cellular manufacturing system,an inter-cell scheduling method was proposed based on multiagents coalitions(MAC).Considering the flexible inter-cell processing routes,a distributed negotiation mechanism was adopted to form grading coalitions and to carry out negotiation scheduling,so as to improve the performance of global optimization as well as reduce the communication.Experiments were taken to verify the proposed algorithm.The results show that the proposed algorithm can provide better performance with respect to the mean delay than the widely used combinatorial heuristic rules.
To solve the problem of the workpiece inter-cell move in inter-cell scheduling for the cellular manufacturing system,an inter-cell scheduling method was proposed based on multiagents coalitions(MAC).Considering the flexible inter-cell processing routes,a distributed negotiation mechanism was adopted to form grading coalitions and to carry out negotiation scheduling,so as to improve the performance of global optimization as well as reduce the communication.Experiments were taken to verify the proposed algorithm.The results show that the proposed algorithm can provide better performance with respect to the mean delay than the widely used combinatorial heuristic rules.
引文
[1]King J R,Nakornchai V.Machine-component group formation in group technology:review and extension[J].The International Journal of Production Research,1982,20(2):117-133.
[2]Yang W H,Liao C J.Group scheduling on two cells with intercell movement[J].Computers&Operations Research,1996,23(10):997-1006.
[3]Tavakkoli-Moghaddam R,Javadian N,Khorrami A,et al.Design of a scatter search method for a novel multicriteria group scheduling problem in a cellular manufacturing system[J].Expert Systems with Applications,2010,37(3):2661-2669.
[4]Solimanpur M,Vrat P,Shankar R.A heuristic to minimize makespan of cell scheduling problem[J].International Journal of Production economics,2004,88(3):231-241.
[5]Golmohammadi A,Ghodsi R.Applying an integer electromagnetism-like algorithm to solve the cellular manufacturing scheduling problem with an integrated approach[C]∥Proceedings of International Conference on.Computers&Industrial Engineering.[S.l.]:IEEE,2009:34-39.
[6]Tang J,Wang X,Kaku I,et al.Optimization of parts scheduling in multiple cells considering intercell move using scatter search approach[J].Journal of Intelligent Manufacturing,2009,21(4):525-537.
[7]Elmi A,Solimanpur M,Topaloglu S,et al.A simulated annealing algorithm for the job shop cell scheduling problem with intercellular moves and reentrant parts[J].Computers&Industrial Engineering,2011,61(1):171-178.
[8]Li D,Meng X,Li M,et al.An ACO-based intercell scheduling approach for job shop cells with multiple single processing machines and one batch processing machine[J].Journal of Intelligent Manufacturing,2016,27(2):283-296.
[9]Yu X,Ram B.Bio-inspired scheduling for dynamic job shops with flexible routing and sequence-dependent setups[J].International Journal of Production Research,2006,44(22):4793-4813.
[10]Lin G Y J,Solberg J J.Effectiveness of flexible routing control[J].International Journal of Flexible Manufacturing Systems,1991,3(3):189-211.
[11]Calleja G,Pastor R.A dispatching algorithm for flexible job-shop scheduling with transfer batches:an industrial application[J].Production Planning&Control,2014,25(2):93-109.
[12]Jia S,Hu Z H.Path-relinking Tabu search for the multiobjective flexible job shop scheduling problem[J].Computers&Operations Research,2014,47:11-26.
[13]Rajabinasab A,Mansour S.Dynamic flexible job shop scheduling with alternative process plans:an agentbased approach[J].The International Journal of Advanced Manufacturing Technology,2011,54(9-12):1091-1107.
[14]Ennigrou M,Ghédira K.New local diversification techniques for flexible job shop scheduling problem with a multi-agent approach[J].Autonomous Agents and Multi-Agent Systems,2008,17(2):270-287.
[15]Wang C,Ghenniwa H,Shen W M.Real time distributed shop floor scheduling using an agent-based serviceoriented architecture[J].International Journal of Production Research,2008,46(9):2433-2452.
[16]Shen W M.Genetic algorithms in agent-based manufacturing scheduling systems[J].Integrated Computer-Aided Engineering,2002,9(3):207-217.
[17]Hattori H,Ozono T,Ito T,et al.Coalition formation among agents in complex problems based on a combinatorial auction perspective[M]∥Innovations in Applied Artificial Intelligence.Berlin:Springer Berlin Heidelberg,2004:176-187.
[18]Lau H C,Zhang L.Task allocation via multi-agent coalition formation:Taxonomy,algorithms and complexity[C]∥Proceedings of Tools with Artificial Intelligence,15th IEEE International Conference on.[S.l.]:IEEE,2003:346-350.
[19]Kutanoglu E,Wu S D.Coalitions in coordinated multiagent production scheduling:a computational study[J].Journal of Manufacturing Systems,2007,26(1):12-21.
[20]Shehory O,Kraus S.Methods for task allocation via agent coalition formation[J].Artificial Intelligence,1998,101(1):165-200.
[21]Li D,Wang Y,Xiao G,et al.Dynamic parts scheduling in multiple job shop cells considering intercell moves and flexible routes[J].Computers&Operations Research,2013,40(5):1207-1223.
[2]Yang W H,Liao C J.Group scheduling on two cells with intercell movement[J].Computers&Operations Research,1996,23(10):997-1006.
[3]Tavakkoli-Moghaddam R,Javadian N,Khorrami A,et al.Design of a scatter search method for a novel multicriteria group scheduling problem in a cellular manufacturing system[J].Expert Systems with Applications,2010,37(3):2661-2669.
[4]Solimanpur M,Vrat P,Shankar R.A heuristic to minimize makespan of cell scheduling problem[J].International Journal of Production economics,2004,88(3):231-241.
[5]Golmohammadi A,Ghodsi R.Applying an integer electromagnetism-like algorithm to solve the cellular manufacturing scheduling problem with an integrated approach[C]∥Proceedings of International Conference on.Computers&Industrial Engineering.[S.l.]:IEEE,2009:34-39.
[6]Tang J,Wang X,Kaku I,et al.Optimization of parts scheduling in multiple cells considering intercell move using scatter search approach[J].Journal of Intelligent Manufacturing,2009,21(4):525-537.
[7]Elmi A,Solimanpur M,Topaloglu S,et al.A simulated annealing algorithm for the job shop cell scheduling problem with intercellular moves and reentrant parts[J].Computers&Industrial Engineering,2011,61(1):171-178.
[8]Li D,Meng X,Li M,et al.An ACO-based intercell scheduling approach for job shop cells with multiple single processing machines and one batch processing machine[J].Journal of Intelligent Manufacturing,2016,27(2):283-296.
[9]Yu X,Ram B.Bio-inspired scheduling for dynamic job shops with flexible routing and sequence-dependent setups[J].International Journal of Production Research,2006,44(22):4793-4813.
[10]Lin G Y J,Solberg J J.Effectiveness of flexible routing control[J].International Journal of Flexible Manufacturing Systems,1991,3(3):189-211.
[11]Calleja G,Pastor R.A dispatching algorithm for flexible job-shop scheduling with transfer batches:an industrial application[J].Production Planning&Control,2014,25(2):93-109.
[12]Jia S,Hu Z H.Path-relinking Tabu search for the multiobjective flexible job shop scheduling problem[J].Computers&Operations Research,2014,47:11-26.
[13]Rajabinasab A,Mansour S.Dynamic flexible job shop scheduling with alternative process plans:an agentbased approach[J].The International Journal of Advanced Manufacturing Technology,2011,54(9-12):1091-1107.
[14]Ennigrou M,Ghédira K.New local diversification techniques for flexible job shop scheduling problem with a multi-agent approach[J].Autonomous Agents and Multi-Agent Systems,2008,17(2):270-287.
[15]Wang C,Ghenniwa H,Shen W M.Real time distributed shop floor scheduling using an agent-based serviceoriented architecture[J].International Journal of Production Research,2008,46(9):2433-2452.
[16]Shen W M.Genetic algorithms in agent-based manufacturing scheduling systems[J].Integrated Computer-Aided Engineering,2002,9(3):207-217.
[17]Hattori H,Ozono T,Ito T,et al.Coalition formation among agents in complex problems based on a combinatorial auction perspective[M]∥Innovations in Applied Artificial Intelligence.Berlin:Springer Berlin Heidelberg,2004:176-187.
[18]Lau H C,Zhang L.Task allocation via multi-agent coalition formation:Taxonomy,algorithms and complexity[C]∥Proceedings of Tools with Artificial Intelligence,15th IEEE International Conference on.[S.l.]:IEEE,2003:346-350.
[19]Kutanoglu E,Wu S D.Coalitions in coordinated multiagent production scheduling:a computational study[J].Journal of Manufacturing Systems,2007,26(1):12-21.
[20]Shehory O,Kraus S.Methods for task allocation via agent coalition formation[J].Artificial Intelligence,1998,101(1):165-200.
[21]Li D,Wang Y,Xiao G,et al.Dynamic parts scheduling in multiple job shop cells considering intercell moves and flexible routes[J].Computers&Operations Research,2013,40(5):1207-1223.