基于混合遗传算法的分布式车间作业计划调度的算法研究
|
摘要
分布式车间模式作为21世纪企业的先进制造模式，综合了JIT、并行工程、精良制造等多种先进制造模式的哲理，其目的是要以最低成本制造出顾客满意的产品。在这种模式下如何进行组织管理，包括如何组织动态联盟、如何重构车间和单元、如何安排生产计划、如何进行调度都是我们面临的问题。其中车间作业调度与控制技术是实现生产高效率、高柔性和高可靠性的关键，有效实用的调度方法和优化技术的研究与应用已成为先进制造技术实践的基础。本文结合分布式车间生产模式的实际情况，研究了自适应遗传算法和混合遗传算法-模拟退火遗传算法相混合)对该问题的解决策略和过程。详细地阐述了算法的基本结构、编码方式、解码规则、适值函数的选取、自适应变异和交叉算子的设计、染色体可行性的判断流程，最后以数据表和甘特图的方式给出了计算结果。从结果中可以看出遗传算法是解决该问题的行之有效的方法，而混合遗传算法则是解决该问题的更为优良的方法。
As advanced manufacturing mode for the 21th business enterprise, distribution shop mode synthesizes many exellent philosophies of manufacturing pattern such as JIT, parallel engineering project, ecellent manufacturing and so on. Its purpose is making out customer satisfied products with the most low cost. Under distribution shop mode, we are faced with how to organize and manage production, which include how to organize dynamic alliance, how to restructure shop and unit, how to arrange producing planning, and how to proceed scheduling. Among them, job-shop scheduling and control technique is the key to achieve producing high-efficiencyly, high-flexibility, and high-dependability. To study and apply an effective scheduling method and optimizing technique have become practised basic of advanced manufacturing technique. This paper studies how to use self-adapted genetic algorithm and hybrid genetic algorithm (GASA) to solve this problem and its application. The author expatiated on the basic structure, coding manners, decoding rules, fitness function selection, self-adapted mutation and crossover operator, the judging flow of chromosome feasibility of the algorithm, finally , put forward the computing result with pattern of data table and GANTT graph. In this paper, the author come to a conclusion that genetic algorithm is an efficient solution to distribution job-shop problem, while GASA is a more superior method than it.
As advanced manufacturing mode for the 21th business enterprise, distribution shop mode synthesizes many exellent philosophies of manufacturing pattern such as JIT, parallel engineering project, ecellent manufacturing and so on. Its purpose is making out customer satisfied products with the most low cost. Under distribution shop mode, we are faced with how to organize and manage production, which include how to organize dynamic alliance, how to restructure shop and unit, how to arrange producing planning, and how to proceed scheduling. Among them, job-shop scheduling and control technique is the key to achieve producing high-efficiencyly, high-flexibility, and high-dependability. To study and apply an effective scheduling method and optimizing technique have become practised basic of advanced manufacturing technique. This paper studies how to use self-adapted genetic algorithm and hybrid genetic algorithm (GASA) to solve this problem and its application. The author expatiated on the basic structure, coding manners, decoding rules, fitness function selection, self-adapted mutation and crossover operator, the judging flow of chromosome feasibility of the algorithm, finally , put forward the computing result with pattern of data table and GANTT graph. In this paper, the author come to a conclusion that genetic algorithm is an efficient solution to distribution job-shop problem, while GASA is a more superior method than it.
引文
[1]李健，何桢，康敏，JOB SHOP中零件排序的一种启发式算法，天津理工学院学报，1996，Vol．12，No．4，59～64
[2]E.L. Lawler, Optimal sequencing of a single machine subject to precedence constraints, Management Sci. 1973, Vol. 19, 544～546
[3]C.L. Monma, Sequencing to minimize the Maximum job cost, Oper. Res. 1980, Vol. 28, 942～951
[4]T.S. Abdul-razaq, C.N. Ports, Dynamic programming state-space relaxation for single-machine scheduling, Joper. Res. Soc., 1988, Vol. 39, 141～152
[5]Carlier, Scheduling jobs with release dates and tails on identical machines to minimize makespan, European J. Oper. Res., 1987, Vol. 29, 2980～306
[6]J.Grabowski, A new algorithm of solving the flow-shop problem, Operations Research in Progress, Reidel.
[7]Y. Cho, S. Sahni, preemptive scheduling of independent jobs with release and due times on open, flow and job shops, Oper. Res., 1981, Vol. 29, 511～522
[8]E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys, Sequencing and Scheduling: Algorithms and Complexity, Operations Research and Management Science,Vol. 4, Edited by S.C. Graves.
[9]张书亭，杨建军，邬学礼，敏捷制造执行系统的调度策略研究，机械设计与制造工程，2001，Vol．30，No．3，40～42
[10]Montazeri, M. And Van Wassenhove, L. N.(1990) Analysis of scheduling rules for an FMS. International Journal of Production Research 28, 785～802.
[11]Doublgeri, Z., G.D' alessandro and N. Magaletti, A hierarchical knowledge-based scheduling and control for FMSs, Int. J. Computer integrated Manufacturing, 1993, Vol. 6, No. 3, 191～200
[12]Wu, Szu-Yung David and Richard A. Wysk, An application of discrete-event sumulation to on-line control and scheduling in flexible manufacturing, Int. J. Prod. Res., 1989, Vol. 27, No. 9, 1603～1623
[13]Jiang, Chang-Qing, Singh, Madan G., and Hindi, Khalil S., Optimized Routing in flexible manufacturing systems with blocking, IEEE Trans. on Systems,Man, and Cybernetics, 1991, Vol. 21, No. 3, 589～595
[14]Lee, D.Y. and F. Dicesare, Scheduling flexible manufacturing systems using petri nets and heuristic search, IEEE Trans. on Robotics and Automation, 1994, Vol. 10,No. 2, 123～132
[15]Jeffcoat, David E. and Robert L. Bulfin, Simulated annealing for resource-constrained scheduling, European Journal of Operational research, 1993, Vol.70, 43～51
[16]Taillard, E., Some efficient heuristic methods for the flow shop sequencing problem, European Journal of Oper. Res., 1990, 47/1, 65～74
[17]Languna, Manuel, J. Wesley Barnes and Fred Glover, Intelligent scheduling with tabu search: An application to jobs with linear delay penalties and sequence-dependent setup costs and times, Journal of Applied Intelligence, 1993, No. 3, 159～172
[18]尹新，杨自厚，用tabu search方法解带有等待时间惩罚的提前／拖期调度问题，系统工程理论方法应用，1995，Vol．4，No．1，30～35
[19]Balas, E. Machine-Sequencing via Disjunctive Graphs: An Implicit Enumeration Algorithm, Oper. Res., 1969, Vol.17, 941～957
[20]Garcia, Bruno-laurent, Potvin, Jean Yves and Rousseau, Jean-Marc, A parallel Implementation of the tabu search heuristic for vehicle routing problems with time window constraints, Computers Ops. Res., 1994, Vol. 21, No. 9, 1025～1033
[21]Foo Y.S., Y. Takefuji, Integer linear programming neural networks for job-shop scheduling, IEEE Int. Conf. On NNS, 1988, San Diego
[22]高红，熊光楞，决策规则在仿真调度中的应用，控制与决策，1995，10(2)，114～118
[23] A.K. Sen, A. Bagchi and B.K. Sinha, Admissible search for minimum penalty sequencing of jobs with setup times on two machines, in Proc. IJCAI-91, Int. Joint Conf. Artificial Intellig. Sydney, Aug. 1991, 178～183
[24]Glover F., New Approaches for Heuristic Search: A Bilateral Linkage with Artificial Intelligence, European Journal of Oper. Res., 1989, Vol. 39, 119～130
[25]Widmer. M., and Hertz, A., A new heuristic method for the flow shop sequencing problem, European Journal of Oper. Res., 1989, Vol. 41, No. 2, 186～193
[26]Zesheng He, Taeyong Yang, Andy Tiger, An exchange heuristic imbedded with simulated annealing for due-dates job-shop scheduling, 1996, European Journal of Oper. Res., Vol. 91, 99～117
[27]Hisao Ishibuchi, Shinta Misal, Hideo Tanaka, Modified simulated annealing algorithms for the flow shop sequencing problem, 1995, European Journal of Oper.Res., Vol. 81, 388～398
[28]Glover F., Future Paths for Integer Programming and Links to Artificial Intelligence, Computer & Oper. Res., 1986, Vol. 13, No. 5, 533～549
[29]王家钦，生产调度的一种启发式规则，清华大学学报，1995，35(5), 27～32
[30]Vassilis S. Kouikoglou, Yannis A. Phillis, An Exact Discrete-Event Model and Control Policies for Production Lines with Buffers, IEEE Trans. On automatic control,Vol. 36, No. 5, May, 1991
[31]刘瑞华，涂奉生，Fork-Join排队网络的建模与稳定性，控制与决策，9(3)，1994，131～135
[32]Leung, L.C., S.K. Maqnheshwari and W.A. miller, concurrent part assignment and tool allocation in FMS with material handling considerations, Int. J. Prod. Res.,1993, Vol. 31, No.1, 117～138
[33][日]玄光男，程润伟著．遗传算法与工程设计．北京：科学出版社，2000年1月．
[34]王小平、曾立明著。遗传算法—理论、应用于软件实现．西安交通大学出版社，2002年1月
[35]刘勇，康立山等，非数值并行计算(第二册)——遗传算法．北京：科学出版社，1995
[36]许国志．系统科学与工程研究．上海：上海科技教育出版社，2000
[37]周明，孙树栋．遗传算法原理及其应用．北京：国防工业出版社，1999
[38]张东摩，李洪兵．人工智能研究动态与发展趋势．计算机科学，25(2)，1998，5～8
[39]刘建勤．人工生命理论及其应用．北京：冶金工业出版社，1997
[40]赵南元．认知科学与广义进化论．北京：清华大学出版社，1994
[41]张曙．新的模式：独立制造岛和分散网络化生产系统．机电一体化，4(3)，1997，37～40
[42]李岩，吴智铭．遗传算法在柔性动态调度中的应用．上海交通大学学报，35(2)，2001，250～255
[43]李郝林．基于生物遗传算法的FMS生产调度算法．机械工程学报，36(9)，2000，91～97
[44]王凌，郑大钟．一种GASA混合优化策略．控制理论与应用，2001，18(4)
[45]王雪梅，王义和．模拟退火法与遗传算法的结合．计算机学报，20(4)，1997，381～384
[46]王凌，郑大钟．一类GASA混合策略及其收敛性研究．控制与决策，13(6)，1998，672～699
[47]Montazer M, Wassenhove L N V. Analysis of scheduling rules for an FMS [J].Int. Jour. Prod Res, 1990, Vol. 28, No. 4, 785～802
[48]姚新，陈国梁．模拟退火算法及其应用．计算机研究与发展，7(1)，1990，1～6
[49]刘勇，等．非数值并行算法(第一册)—模拟退火算法[M]．北京：科学出版社，1997．
[50]何霆，刘文煌，梁力平等．基于进化算法的一类作业车间调度．计算机继承制造系统．2001年1月第7卷(1)．
[51]顾擎明，曹丽娟．解Job-shop调度问题的自适应遗传方法[J]．控制与决策，1998，13(5)，pp589～592．
[52]王凌．智能优化算法及其应用．北京：清华大学出版社 施普林格出版社，2001：159～166
[53]王凌．车间调度及其遗传算法．北京：清华大学出版社 施普林格出版社，2003：36～42．
[54]钱晓龙，唐立新，刘文新．动态调度的研究方法综述．控制与决策，Vol．16，No．2，141～145
[55]杨红红，吴智铭．基于自适应遗传算法的柔性动态调度研究．中国机械工程．Vol．13，No．21，2002年上半月．1845～1848
[2]E.L. Lawler, Optimal sequencing of a single machine subject to precedence constraints, Management Sci. 1973, Vol. 19, 544～546
[3]C.L. Monma, Sequencing to minimize the Maximum job cost, Oper. Res. 1980, Vol. 28, 942～951
[4]T.S. Abdul-razaq, C.N. Ports, Dynamic programming state-space relaxation for single-machine scheduling, Joper. Res. Soc., 1988, Vol. 39, 141～152
[5]Carlier, Scheduling jobs with release dates and tails on identical machines to minimize makespan, European J. Oper. Res., 1987, Vol. 29, 2980～306
[6]J.Grabowski, A new algorithm of solving the flow-shop problem, Operations Research in Progress, Reidel.
[7]Y. Cho, S. Sahni, preemptive scheduling of independent jobs with release and due times on open, flow and job shops, Oper. Res., 1981, Vol. 29, 511～522
[8]E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys, Sequencing and Scheduling: Algorithms and Complexity, Operations Research and Management Science,Vol. 4, Edited by S.C. Graves.
[9]张书亭，杨建军，邬学礼，敏捷制造执行系统的调度策略研究，机械设计与制造工程，2001，Vol．30，No．3，40～42
[10]Montazeri, M. And Van Wassenhove, L. N.(1990) Analysis of scheduling rules for an FMS. International Journal of Production Research 28, 785～802.
[11]Doublgeri, Z., G.D' alessandro and N. Magaletti, A hierarchical knowledge-based scheduling and control for FMSs, Int. J. Computer integrated Manufacturing, 1993, Vol. 6, No. 3, 191～200
[12]Wu, Szu-Yung David and Richard A. Wysk, An application of discrete-event sumulation to on-line control and scheduling in flexible manufacturing, Int. J. Prod. Res., 1989, Vol. 27, No. 9, 1603～1623
[13]Jiang, Chang-Qing, Singh, Madan G., and Hindi, Khalil S., Optimized Routing in flexible manufacturing systems with blocking, IEEE Trans. on Systems,Man, and Cybernetics, 1991, Vol. 21, No. 3, 589～595
[14]Lee, D.Y. and F. Dicesare, Scheduling flexible manufacturing systems using petri nets and heuristic search, IEEE Trans. on Robotics and Automation, 1994, Vol. 10,No. 2, 123～132
[15]Jeffcoat, David E. and Robert L. Bulfin, Simulated annealing for resource-constrained scheduling, European Journal of Operational research, 1993, Vol.70, 43～51
[16]Taillard, E., Some efficient heuristic methods for the flow shop sequencing problem, European Journal of Oper. Res., 1990, 47/1, 65～74
[17]Languna, Manuel, J. Wesley Barnes and Fred Glover, Intelligent scheduling with tabu search: An application to jobs with linear delay penalties and sequence-dependent setup costs and times, Journal of Applied Intelligence, 1993, No. 3, 159～172
[18]尹新，杨自厚，用tabu search方法解带有等待时间惩罚的提前／拖期调度问题，系统工程理论方法应用，1995，Vol．4，No．1，30～35
[19]Balas, E. Machine-Sequencing via Disjunctive Graphs: An Implicit Enumeration Algorithm, Oper. Res., 1969, Vol.17, 941～957
[20]Garcia, Bruno-laurent, Potvin, Jean Yves and Rousseau, Jean-Marc, A parallel Implementation of the tabu search heuristic for vehicle routing problems with time window constraints, Computers Ops. Res., 1994, Vol. 21, No. 9, 1025～1033
[21]Foo Y.S., Y. Takefuji, Integer linear programming neural networks for job-shop scheduling, IEEE Int. Conf. On NNS, 1988, San Diego
[22]高红，熊光楞，决策规则在仿真调度中的应用，控制与决策，1995，10(2)，114～118
[23] A.K. Sen, A. Bagchi and B.K. Sinha, Admissible search for minimum penalty sequencing of jobs with setup times on two machines, in Proc. IJCAI-91, Int. Joint Conf. Artificial Intellig. Sydney, Aug. 1991, 178～183
[24]Glover F., New Approaches for Heuristic Search: A Bilateral Linkage with Artificial Intelligence, European Journal of Oper. Res., 1989, Vol. 39, 119～130
[25]Widmer. M., and Hertz, A., A new heuristic method for the flow shop sequencing problem, European Journal of Oper. Res., 1989, Vol. 41, No. 2, 186～193
[26]Zesheng He, Taeyong Yang, Andy Tiger, An exchange heuristic imbedded with simulated annealing for due-dates job-shop scheduling, 1996, European Journal of Oper. Res., Vol. 91, 99～117
[27]Hisao Ishibuchi, Shinta Misal, Hideo Tanaka, Modified simulated annealing algorithms for the flow shop sequencing problem, 1995, European Journal of Oper.Res., Vol. 81, 388～398
[28]Glover F., Future Paths for Integer Programming and Links to Artificial Intelligence, Computer & Oper. Res., 1986, Vol. 13, No. 5, 533～549
[29]王家钦，生产调度的一种启发式规则，清华大学学报，1995，35(5), 27～32
[30]Vassilis S. Kouikoglou, Yannis A. Phillis, An Exact Discrete-Event Model and Control Policies for Production Lines with Buffers, IEEE Trans. On automatic control,Vol. 36, No. 5, May, 1991
[31]刘瑞华，涂奉生，Fork-Join排队网络的建模与稳定性，控制与决策，9(3)，1994，131～135
[32]Leung, L.C., S.K. Maqnheshwari and W.A. miller, concurrent part assignment and tool allocation in FMS with material handling considerations, Int. J. Prod. Res.,1993, Vol. 31, No.1, 117～138
[33][日]玄光男，程润伟著．遗传算法与工程设计．北京：科学出版社，2000年1月．
[34]王小平、曾立明著。遗传算法—理论、应用于软件实现．西安交通大学出版社，2002年1月
[35]刘勇，康立山等，非数值并行计算(第二册)——遗传算法．北京：科学出版社，1995
[36]许国志．系统科学与工程研究．上海：上海科技教育出版社，2000
[37]周明，孙树栋．遗传算法原理及其应用．北京：国防工业出版社，1999
[38]张东摩，李洪兵．人工智能研究动态与发展趋势．计算机科学，25(2)，1998，5～8
[39]刘建勤．人工生命理论及其应用．北京：冶金工业出版社，1997
[40]赵南元．认知科学与广义进化论．北京：清华大学出版社，1994
[41]张曙．新的模式：独立制造岛和分散网络化生产系统．机电一体化，4(3)，1997，37～40
[42]李岩，吴智铭．遗传算法在柔性动态调度中的应用．上海交通大学学报，35(2)，2001，250～255
[43]李郝林．基于生物遗传算法的FMS生产调度算法．机械工程学报，36(9)，2000，91～97
[44]王凌，郑大钟．一种GASA混合优化策略．控制理论与应用，2001，18(4)
[45]王雪梅，王义和．模拟退火法与遗传算法的结合．计算机学报，20(4)，1997，381～384
[46]王凌，郑大钟．一类GASA混合策略及其收敛性研究．控制与决策，13(6)，1998，672～699
[47]Montazer M, Wassenhove L N V. Analysis of scheduling rules for an FMS [J].Int. Jour. Prod Res, 1990, Vol. 28, No. 4, 785～802
[48]姚新，陈国梁．模拟退火算法及其应用．计算机研究与发展，7(1)，1990，1～6
[49]刘勇，等．非数值并行算法(第一册)—模拟退火算法[M]．北京：科学出版社，1997．
[50]何霆，刘文煌，梁力平等．基于进化算法的一类作业车间调度．计算机继承制造系统．2001年1月第7卷(1)．
[51]顾擎明，曹丽娟．解Job-shop调度问题的自适应遗传方法[J]．控制与决策，1998，13(5)，pp589～592．
[52]王凌．智能优化算法及其应用．北京：清华大学出版社 施普林格出版社，2001：159～166
[53]王凌．车间调度及其遗传算法．北京：清华大学出版社 施普林格出版社，2003：36～42．
[54]钱晓龙，唐立新，刘文新．动态调度的研究方法综述．控制与决策，Vol．16，No．2，141～145
[55]杨红红，吴智铭．基于自适应遗传算法的柔性动态调度研究．中国机械工程．Vol．13，No．21，2002年上半月．1845～1848
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |